Czy

11

Oznacz przez minimalny stopień wyjściowy w G , a przez δ - ( G ) minimalny stopień wyjściowy.δ+(G)Gδ(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.δ+(G),δ(G)n2

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:

  1. Kto udowodnił (czy ktoś może znaleźć odniesienie), że oznacza, że G jest hamiltonianem, biorąc pod uwagę, że G jest silnie związany?δ+(G)+δ(G)nGG

  2. Czy również silna łączność jest tutaj zbędna, tj. Czy oznacza silną łączność?δ+(G)+δ(G)n


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

RB
źródło

Odpowiedzi:

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 n 2 . Jeśli δ + ( x ) + δ - ( Y ) n dla pary wierzchołków x i y takie, że nie ma łuk od X do Y , wówczas D ma Hamiltona.Dn2δ+(x)+δ(y)nxyxyD

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

nnk<na,b,ce,dk2eddbbeece,ddb24=51=n1n

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:

δ+(G)+δ(G)nG

Gδ+(G)+δ(G)<nGSSTTSSδ+(G)δ+(S)|S|1δ(G)|T|1

δ+(G)+δ(G)|S|+|T|2n2 .
pierożek Mobiusa
źródło
1
n1
@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
δ+δ+=n1
4

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

δ++δn1u,vV,d(u,v)2

Dowód:

(u,v)E

A={xV:(u,x)E},B={yV:(y,v)E}

(u,v)EABV{u,v}|AB|n2

n1δ++δ|A|+|B|=|AB|+|AB|n2+|AB|

|AB|1wV:(u,w),(w,v)Ed(u,v)=2

RB
źródło