Est-ce que

Notons le degré de sortie minimal dans G , et par δ - ( G ) le degré de sortie minimal .$\delta^+(G)$$G$$\delta^-(G)$

Dans une question connexe , j'ai mentionné l'extension de Ghouila-Houri du théorème de Dirac sur les cycles hamiltoniens , qui suggère que si alors G est hamiltonien.$\delta^+(G),\delta^-(G) \geq \frac{n}{2}$

Dans son commentaire, Saeed a commenté une extension différente qui semble plus forte, sauf qu'elle nécessite que le graphique soit fortement connecté.

La forte connectivité s'est avérée redondante pour le théorème de Ghouila-Houri environ 30 ans après sa première publication, et je me demandais si cela vaut également pour l'extension présentée par Saeed.

La question est donc:

1. Qui a prouvé (peut-on trouver la référence) que implique que G est hamiltonien, étant donné que G est fortement connecté?$\delta^+(G)+\delta^-(G) \geq n$$G$$G$

2. La forte connectivité est-elle également redondante ici, c'est-à-dire que implique une forte connectivité?$\delta^+(G)+\delta^-(G) \geq n$

(Notez que bien que le graphique doive évidemment être fortement connecté pour qu'il soit hamiltonien, je demande si cette condition est impliquée par les conditions de degré).

La variation que j'ai suggérée était en fait une variation légèrement différente du théorème de Woodal . Je l'ai peut-être vu dans le livre de Bang-Jensen et Gutin . Au moment où j'ai écrit un commentaire, je n'ai pas vérifié l'exactitude du livre. Donc, pour être sûr d'avoir écrit, le graphique doit être fortement connecté. BTW, cette déclaration tient parce que peut être interprétée comme un cas spécial du théorème de Woodal. En outre, ne nécessite pas fortement de connectivité.

Voici le théorème 6.4.6 du livre de Bang-Jensen et Gutin :

Soit un digraphe d'ordre n ≥ 2 . Si δ + ( x ) + δ - ( y ) ≥ n pour toutes les paires de sommets x et y tels qu'il n'y ait pas d'arc de x à y , alors D est hamiltonien.$D$$n\ge 2$$\delta^+(x)+\delta^-(y) \ge n$$x$$y$$x$$y$$D$

Cela signifie que la réponse à la deuxième partie de votre question est également Oui.

$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$

P.S1: Bien sûr, le théorème susmentionné est valable pour les digraphes simples. c'est-à-dire des graphes sans boucle ni bords parallèles.

P.S2: Je n'ai pas de bon outil Tex en ce moment. L'image n'est donc pas bonne.

La réponse à votre deuxième question est affirmative:

$\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$

Il s'agit d'une extension de la réponse @Mobius pour montrer une affirmation plus forte:

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

Preuve:

$(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$

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

$\blacksquare$