Czy

11

Oznacz przez minimalny stopień wyjściowy w , a przez minimalny stopień wyjściowy. $\delta^+(G)$ $G$ $\delta^-(G)$

W powiązanym pytaniu wspomniałem o rozszerzeniu Ghouili-Houri twierdzenia Diraca o cyklach hamiltonowskich , co sugeruje, że jeśli to G oznacza hamiltonian. $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$

W swoim komentarzu Saeed skomentował inne rozszerzenie, które wydaje się silniejsze, ale wymaga silnego połączenia wykresu.

Silna łączność okazała się zbędna w przypadku twierdzenia Ghouila-Houri około 30 lat po jego pierwszej publikacji i zastanawiałem się, czy to samo dotyczy rozszerzenia Saeed.

Pytanie brzmi:

Kto udowodnił (czy ktoś może znaleźć odniesienie), że oznacza, że jest hamiltonianem, biorąc pod uwagę, że jest silnie związany? $\delta^+(G)+\delta^-(G) \geq n$ $G$ $G$

Czy również silna łączność jest tutaj zbędna, tj. Czy oznacza silną łączność? $\delta^+(G)+\delta^-(G) \geq n$

(Zauważ, że chociaż wykres musi być silnie powiązany, aby był Hamiltonianem, pytam, czy warunek ten wynika z warunków stopnia).

reference-request graph-theory

— RB
źródło

8

Wariant, który zasugerowałem, był w rzeczywistości nieco inną odmianą twierdzenia Woodala . Być może widziałem to w książce Bang-Jensen i Gutina . W momencie pisania komentarza nie sprawdziłem poprawności książki. Aby mieć pewność, że napisałem, wykres powinien być ściśle powiązany. BTW, twierdzenie to obowiązuje, ponieważ może być interpretowane jako szczególny przypadek twierdzenia Woodala. Ponadto nie wymaga silnych wymagań dotyczących łączności.

Takie jest twierdzenie 6.4.6 z książki Bang-Jensen i Gutina :

Niech będzie wykresem rzędu . Jeśli dla pary wierzchołków i takie, że nie ma łuk od do , wówczas ma Hamiltona. $D$ $n\ge 2$ $\delta^+(x)+\delta^-(y) \ge n$ $x$ $y$ $x$ $y$ $D$

Oznacza to, że odpowiedź na drugą część twojego pytania brzmi: tak.

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

wprowadź opis zdjęcia tutaj

P.S1: Jasne, że wspomniane twierdzenie dotyczy prostych digrafów. tj. digrafy bez pętli lub równoległych krawędzi.

P.S2: Obecnie nie mam dobrego narzędzia Tex. Obraz nie jest dobry.

— Saeed
źródło

3

Gdy jest tylko dwóch autorów, lepiej jest nazywać ich „Pierwszym i Drugim”, a nie „Pierwszym i in.”, Aby otrzymać uznanie, na które zasługują. I in. („i inne”) należy stosować tylko wtedy, gdy pełna lista autorów jest wystarczająco długa, aby jej odtworzenie było niewygodne.

— David Richerby

7

Odpowiedź na twoje drugie pytanie jest twierdząca:

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

— pierożek Mobiusa
źródło

1

\geq n - 1

$\ge n-1$

@GeoffreyIrving Tak, wydaje się, że tak.

— mobius dumpling

To sprawia, że zastanawiam się, czy n-1 wystarczy dla Hamiltonicity.

— RB

@RB, Nie, to nie wystarczy.

— Saeed,

1

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

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

4

To rozszerzenie odpowiedzi @Mobius, aby pokazać silniejsze roszczenie:

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

Dowód:

$(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
źródło