Teorema lui Fleischner

Teorema lui Fleischner  este o afirmație din teoria grafurilor care oferă o condiție suficientă pentru ca un graf să conțină un ciclu hamiltonian : dacă graficul este un graf conectat cu 2 vârfuri , atunci pătratul grafului hamiltonian. Numit după Herbert Fleischner , care a publicat demonstrarea teoremei în 1974 .

Definiții și enunț

Un grafic nedirecționat G este hamiltonian dacă conține un ciclu care trece prin fiecare vârf exact o dată. Un grafic este conectat cu 2 vârfuri dacă nu conține vârfuri articulate, adică vârfuri a căror eliminare face ca graful rămas să fie deconectat. Nu fiecare graf conectat cu 2 vârfuri este hamiltonian. Contraexemplele includ graficul Petersen și graficul bipartit complet K 2,3 .

Un pătrat al unui grafic G  este un grafic G 2 care are același set de vârfuri ca și graficul G și în care două vârfuri sunt adiacente dacă și numai dacă distanța dintre ele în G este de cel mult două. Teorema lui Fleischer afirmă că pătratul unui graf finit cu trei sau mai multe vârfuri trebuie să fie întotdeauna hamiltonian. În mod echivalent, vârfurile oricărui graf G conectat cu 2 vârfuri pot fi aranjate într-o ordine ciclică, astfel încât vârfurile adiacente din această ordine în G să fie de cel mult două una de cealaltă.

Extensii

În teorema lui Fleischner, se poate constrânge un ciclu hamiltonian să includă trei muchii alese care trec prin două vârfuri alese [1] [2] .

Pe lângă faptul că conține un ciclu hamiltonian, pătratul unui graf G conectat cu 2 vârfuri trebuie să fie, de asemenea, legat de hamiltonian (adică are o cale hamiltoniană care începe și se termină la oricare două vârfuri alese) și 1-Hamiltonian (adică dacă eliminați orice vârf, graficul rămas va conține și un ciclu hamiltonian) [3] [4] . Graficul trebuie să fie, de asemenea, vârf panciclic , ceea ce înseamnă că pentru orice vârf v și orice număr întreg k cu 3 ≤ k ≤ | V ( G )| există un ciclu de lungime k care conține v [5] .

Dacă graficul G nu este conectat la 2 vârfuri, pătratul său poate avea sau nu un ciclu hamiltonian, iar determinarea dacă graficul are un astfel de ciclu este o problemă NP-complet [6] [7] .

Un graf infinit nu poate avea un ciclu hamiltonian, deoarece orice ciclu este finit, dar Carsten Thomassen a demonstrat că, în cazul în care G este un graf infinit local finit legat de vârfuri-2 cu un singur capăt, atunci G 2 are în mod necesar un cale Hamiltoniană dublu infinită [ 8] . Mai general, dacă G este local finit, legat de 2 vârfuri și are orice număr de capete, atunci G2 are un ciclu hamiltonian. Într -un spațiu topologic compact , format prin tratarea unui grafic ca un complex simplist și adăugarea unui punct suplimentar la infinit pentru fiecare capăt al graficului, un ciclu hamiltonian este definit ca un subspațiu care este homeomorf cu cercul euclidian și acoperă toate vârfurile [9] ] [10] .

Istorie

Dovada teoremei a fost anunțată de Herbert Fliashner în 1971 și publicată în 1974, rezolvând astfel conjectura Nash-Williams din 1966 , care a fost, de asemenea, declarată independent de L.W. Bynik și Plummer [11] . În recenzia sa asupra articolului lui Fleischner, Nash-Williams scrie că a rezolvat „o problemă binecunoscută care a zădărnicit ingeniozitatea altor teoreticieni ai graficilor de câțiva ani” [12] .

Dovada originală a lui Fleischer a fost dificilă. Vaclav Chvatal , în lucrarea sa, în care a introdus noțiunea de rigiditate a unui graf , a remarcat că pătratul unui graf legat de vârf - k este în mod necesar k -rigid. El a presupus că grafurile 2-rigide sunt hamiltoniene, ceea ce ar duce la o altă demonstrație a teoremei lui Fleischer [13] [7] . Ulterior au fost găsite contraexemple pentru această presupunere [14] , dar posibilitatea ca o limită de rigiditate finită să implice Hamiltonianitatea a rămas o problemă deschisă importantă în teoria grafurilor. O demonstrație mai simplă atât a teoremei lui Fleischner, cât și a extinderii acesteia de către Chartrand, Hobbs, Young și Kapuur [3] a fost dată de Riha [15] [7] [4] , iar o altă demonstrație simplificată a teoremei a fost dată de Georgakopoulus [16] [ 4 ] ] [10] .

Note

  1. ↑ Fleischner 1976 , p. 125–149.
  2. ↑ Müttel, Rautenbach, 2012 .
  3. ↑ 1 2 Chartrand, Hobbs, Jung, Kapoor, 1974 .
  4. ↑ 1 2 3 Chartrand, Lesniak, Zhang, 2010 .
  5. ↑ Hobbs ( Hobbs (1976 )), răspuns la ipoteza lui Bondy ( Bondy, 1971 ).
  6. ↑ Underground, 1978 .
  7. ↑ 1 2 3 Bondy, 1995 .
  8. ↑ Thomassen (1978) .
  9. ↑ Georgakopoulos, 2009b .
  10. ↑ 12 Diesel , 2012 .
  11. ↑ Fleischner (1974 ). Pentru ipotezele anterioare, a se vedea Fleischner și Chartrand, Lesniak și Zhang ( Chatrand, Lesniak, Zhang (2010 )).
  12. ↑ MR : 0332573 .
  13. ↑ Chvatal, 1973 .
  14. ↑ Bauer, Broersma, Veldman, 2000 .
  15. ↑ Shiha, 1991 .
  16. ↑ Georgakopoulos, 2009a .

Literatură