subgrafo birregular inducido de un grafo bipartito birregular

Question

No estoy muy familiarizado con los teoremas y resultados clásicos que son bien conocidos por los expertos en teoría de grafos, espero que no te importe si mi pregunta es demasiado ingenua.

Dado un grafo bipartito birregular $G=(V,E)$ , donde $V=V_1 \bigcup V_2$ y $V_1 \bigcap V_2=\emptyset$ . Supongamos que $\text{deg}(u)=m, \forall u\in V_1$ y $\text{deg}(v)=n, \forall v\in V_2$ . Entonces sostiene que $m|V_1|=n|V_2|$ .

La pregunta es: supongamos que existe un número entero $k < m$ tal que $k|V_1|=n L$ donde $L < |V_2|$ es un número entero, ¿podemos encontrar siempre un subgrafo birregular inducido eligiendo cuidadosamente $L$ vértices en $|V_2|$ y todos los vértices en $V_1$ ?

La condición anterior es en realidad la condición suficiente si existe un grafo birregular, con $k$ y $n$ siendo los grados de los vértices.

Gracias por su ayuda.

Answer 1

Es fácil tratar este problema en términos de cubiertas de $V_1$ . Es decir, para cada vértice $v_2\in V_2$ un conjunto $N(v_2)$ de sus vecinos es un subconjunto de $V_1$ de tamaño $n$ . Cada vértice $v_1\in V_1$ está cubierto por una familia $\mathcal U=\{N(v):v_2\in V_2\}$ exactamente $m$ tiempos. Dado $k<m$ tal que $kn$ es divisible por $r=|V_1|$ queremos encontrar una subfamilia $\mathcal V$ de un determinado $n$ -cubierta uniforme $\mathcal U$ que cubre cada vértice de $V_1$ exactamente $k$ tiempos. Esto no siempre es posible. Por ejemplo, recientemente Andriy Yurchyshyn , resolviendo otro problema, para $r\in\{6,10,14,18\}$ construyó una familia $\mathcal U$ de subconjuntos de un conjunto $[r]=\{1,\dots,r\}$ de tamaño $n=r/2$ cada uno, de manera que cada elemento $v_1\in [r]$ está cubierto exactamente $m=\tfrac 14 {r \choose r/2}$ tiempos y $\mathcal U$ no contiene ninguna subfamilia $\mathcal V$ que cubre cada elemento $v_1\in [r]$ exactamente $k=1$ tiempos. La familia $\mathcal U$ para $r=6$ es

124 235 346 451 562 613 123 345 561 246

Las siguientes subfamilias de $\mathcal U$ también producen contraejemplos:

124 235 346 451 562 613

y

123 345 561 246