Bedeutet

11

Bezeichne mit den minimalen In-Grad in und mit den minimalen In-Grad. $\delta^+(G)$ $G$ $\delta^-(G)$

In einer verwandten Frage habe ich die Ghouila-Houri-Erweiterung des Dirac-Theorems über Hamilton-Zyklen erwähnt , was darauf hindeutet, dass wenn dann ist G Hamiltonian. $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$

In seinem Kommentar hat Saeed eine andere Erweiterung kommentiert, die stärker zu sein scheint, außer dass das Diagramm stark verbunden sein muss.

Die starke Konnektivität erwies sich für das Ghouila-Houri-Theorem etwa 30 Jahre nach seiner Erstveröffentlichung als überflüssig , und ich fragte mich, ob dies auch für die von Saeed vorgestellte Erweiterung gilt.

Die Frage ist also:

Wer bewies (kann jemand die Referenz finden) , dass bedeutet - Hamilton - Operator ist, da ist stark verbunden? $\delta^+(G)+\delta^-(G) \geq n$ $G$ $G$

Ist die starke Konnektivität auch hier redundant, dh impliziert eine starke Konnektivität? $\delta^+(G)+\delta^-(G) \geq n$

(Beachten Sie, dass der Graph offensichtlich stark verbunden sein muss, damit er Hamilton ist, aber ich frage, ob diese Bedingung durch die Gradbedingungen impliziert wird).

reference-request graph-theory RB
quelle

8

Die Variation, die ich vorgeschlagen habe, war tatsächlich eine etwas andere Variation des Woodal- Theorems. Vielleicht habe ich es im Buch von Bang-Jensen und Gutin gesehen . Zu dem Zeitpunkt, als ich einen Kommentar schrieb, habe ich das Buch nicht auf Richtigkeit überprüft. Um sicherzugehen, dass ich das Diagramm geschrieben habe, sollte es stark verbunden sein. Übrigens gilt diese Aussage, weil sie als Sonderfall des Woodal-Theorems interpretiert werden kann. Darüber hinaus benötigt keine starke Konnektivität erforderlich.

Dies ist der Satz 6.4.6 aus Bang-Jensens und Gutins Buch:

Sei ein Digraph der Ordnung . Wenn für alle Scheitelpunktpaare und so dass es keinen Bogen von nach , dann ist hamiltonisch. $D$ $n\ge 2$ $\delta^+(x)+\delta^-(y) \ge n$ $x$ $y$ $x$ $y$ $D$

Das heißt, die Antwort auf den zweiten Teil Ihrer Frage lautet ebenfalls Ja.

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

Geben Sie hier die Bildbeschreibung ein

P.S1: Sicher, der oben genannte Satz gilt für einfache Digraphen. dh Digraphen ohne Schleife oder parallele Kanten.

P.S2: Ich habe momentan kein gutes Tex-Tool. Das Bild ist also nicht gut.

Saeed
quelle

3

Wenn es nur zwei Autoren gibt, ist es besser, sie als "Erste und Zweite" zu bezeichnen, als als "Erste et al.", Damit sie die Anerkennung erhalten, die sie verdienen. Et al. ("und andere") sollten nur verwendet werden, wenn die vollständige Autorenliste lang genug ist, um sie zu reproduzieren.

David Richerby

7

Die Antwort auf Ihre zweite Frage ist positiv:

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

Mobius Knödel
quelle

1

\geq n - 1

$\ge n-1$

@GeoffreyIrving Ja, es scheint so.

Mobius Knödel

Ich frage mich, ob n-1 für Hamiltonicity ausreicht.

RB

@RB, Nein, das reicht nicht.

Saeed

1

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

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

4

Dies ist eine Erweiterung der @ Mobius-Antwort, um einen stärkeren Anspruch zu zeigen:

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

Beweis:

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

Bedeutet

Antworten: