El teorema de Dirac para los grafos bipartitos

Question

El teorema de Dirac de que cualquier gráfico $G$ en $n\geq 3$ vértices con grado mínimo $\delta(G)n/2$ contiene un ciclo de Hamilton es uno de los resultados clásicos de la teoría de grafos.

¿Existe una versión análoga que correlacione el grado mínimo de los vértices de un grafo bipartito para garantizar un ciclo hamiltoniano ( o alternativamente un emparejamiento perfecto)?

Answer 1

Sí, lo hay.

Tenemos el siguiente teorema de Bondy (1969):

Dejemos que $G = (X,Y,E)$ sea un grafo bipartito simple con $|X|=|Y|=n\ge 2$ . Que los vértices de $X$ et $Y$ ser indexados con grados crecientes (es decir, $X = \{x_1, \dots, x_n\}$ con $\deg(x_1) \le \deg(x_2) \le \dots \le \deg(x_n)$ et $Y = \{y_1, \dots, y_n\}$ con $\deg(y_1) \le \deg(y_2) \le \dots \le \deg(y_n)$ ). Si $$\deg(x_j) \le j, \deg(y_k) \le k \implies \deg(x_j) + \deg(y_k) \ge n+1$$ entonces $G$ tiene un ciclo hamiltoniano.

Esto es mucho más complicado que el teorema de Dirac, pero como corolario más débil, tenemos:

Dejemos que $G = (X,Y,E)$ sea un grafo bipartito simple con $|X|=|Y|=n\ge 2$ . Si $\delta(G) \ge \frac{n+1}{2}$ entonces $G$ tiene un ciclo hamiltoniano.

Sólo un grado mínimo $\frac n2$ no sería suficiente, ya que entonces $G$ podrían ser dos copias disjuntas de $K_{n/2, n/2}$ .

Obtengo el teorema de Bondy del capítulo 10 de la obra de Berge Gráficos e hipergráficos que es mi recurso para los teoremas de la condición del ciclo hamiltoniano.