¿

11

Denote por el grado mínimo de salida en , y por el grado mínimo de entrada. $\delta^+(G)$ $G$ $\delta^-(G)$

En una pregunta relacionada , mencioné la extensión de Ghouila-Houri del teorema de Dirac sobre los ciclos hamiltonianos , que sugiere que si entonces G es hamiltoniano. $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$

En su comentario, Saeed ha comentado una extensión diferente que parece más fuerte, excepto que requiere que el gráfico esté fuertemente conectado.

La sólida conectividad se demostró redundante para el teorema de Ghouila-Houri unos 30 años después de su primera publicación, y me preguntaba si lo mismo vale para la extensión que presentó Saeed.

Entonces la pregunta es:

¿Quién demostró (alguien puede encontrar la referencia) que implica que es hamiltoniano, dado que está fuertemente conectado? $\delta^+(G)+\delta^-(G) \geq n$ $G$ $G$

¿La conectividad fuerte también es redundante aquí, es decir, implica una conectividad fuerte? $\delta^+(G)+\delta^-(G) \geq n$

(Tenga en cuenta que si bien el gráfico obviamente tiene que estar fuertemente conectado para que sea hamiltoniano, estoy preguntando si esta condición está implícita en las condiciones de grado).

reference-request graph-theory RB
fuente

8

La variación que sugerí era en realidad una variación ligeramente diferente del teorema de Woodal . Quizás lo vi en el libro de Bang-Jensen y Gutin . En el momento en que escribí un comentario, no revisé la corrección del libro. Entonces, para estar seguro, escribí que el gráfico debe estar fuertemente conectado. Por cierto, esa afirmación se cumple porque puede interpretarse como un caso especial del teorema de Woodal. Además, no necesita un fuerte requisito de conectividad.

Este es el teorema 6.4.6 del libro de Bang-Jensen y Gutin :

Sea un dígrafo de orden . Si para todos los pares de vértices y de tal manera que no hay arco desde a , a continuación, es hamiltoniano. $D$ $n\ge 2$ $\delta^+(x)+\delta^-(y) \ge n$ $x$ $y$ $x$ $y$ $D$

Eso significa que la respuesta a la segunda parte de su pregunta también es Sí.

$n$ $n$ $k<n$ $a,b,c$ $e,d$ $k_2$ $e$ $d$ $d$ $b$ $b$ $e$ $e$ $c$ $e,d$ $d$ $b$ $2$ $4=5-1 = n-1$ $n$

ingrese la descripción de la imagen aquí

P.S1: Claro, el teorema mencionado anteriormente es válido para los dígrafos simples. es decir, dígrafos sin bucle o bordes paralelos.

P.S2: No tengo una buena herramienta Tex en este momento. Entonces la imagen no es buena.

Saeed
fuente

3

Cuando solo hay dos autores, es mejor referirse a ellos como "Primero y Segundo", en lugar de "Primero y otros", para que reciban el crédito que merecen. Et al. ("y otros") solo deben usarse cuando la lista completa de autores es lo suficientemente larga como para reproducirla sería incómoda.

David Richerby

7

La respuesta a su segunda pregunta es afirmativa:

$\delta^+(G)+\delta^-(G) \ge n$ $G$

$G$ $\delta^+(G)+\delta^-(G) < n$ $G$ $S$ $S$ $T$ $T$ $S$ $S$ $\delta^+(G) \le \delta^+(S) \le |S|-1$ $\delta^-(G) \le |T|-1$

δ^{+} (G) + δ^{-} (G) \leq | S | + | T | - 2 \leq n - 2 .

$\delta^+(G)+\delta^-(G) \le |S|+|T|-2 \le n-2 \ .$

bola de masa de mobius
fuente

1

\geq n - 1

$\ge n-1$

@GeoffreyIrving Sí, parece que sí.

mobius dumpling

Esto me hace preguntarme si n-1 es suficiente para Hamiltonicity.

RB

@RB, no, no es suficiente.

Saeed

1

δ^{-} + δ^{+} = n - 1

$\delta^-+\delta^+ = n-1$

4

Esta es una extensión de la respuesta @Mobius para mostrar una afirmación más sólida:

$\delta^+ + \delta^- \geq n-1$ $\forall u,v\in V, d(u,v)\leq 2$

Prueba:

$(u,v)\in E$

$A=\{x\in V: (u,x)\in E\}, B=\{y\in V: (y,v)\in E\}$

$(u,v)\not \in E$ $A \cup B \subseteq V\setminus \{u,v\}$ $|A\cup B|\leq n-2$

n - 1 \leq δ^{+} + δ^{-} \leq | A | + | B | = | A \cup B | + | A \cap B | \leq n - 2 + | A \cap B |

$n-1 \leq \delta^+ + \delta^- \leq |A|+|B| = |A\cup B| + |A\cap B| \leq n-2 + |A\cap B|$

$|A\cap B| \geq 1$ $\exists w\in V:(u,w),(w,v)\in E$ $d(u,v)=2$

$\blacksquare$

RB
fuente

¿

Respuestas: