Fleischnerova věta

Fleischnerova věta  je tvrzení v teorii grafů , které dává dostatečnou podmínku pro to, aby graf obsahoval hamiltonovský cyklus : pokud je graf 2 -vrcholově spojený graf , pak druhá mocnina hamiltonovského grafu. Pojmenováno po Herbertu Fleischnerovi , který v roce 1974 publikoval důkaz této věty .

Definice a prohlášení

Neorientovaný graf G je hamiltonovský, pokud obsahuje cyklus , který prochází každým vrcholem právě jednou. Graf je 2-vrcholově spojený, pokud neobsahuje artikulující vrcholy, tedy vrcholy, jejichž odstranění způsobí rozpojení zbývajícího grafu. Ne každý 2-vrcholový graf je hamiltonovský. Protipříklady zahrnují Petersenův graf a úplný bipartitní graf K2,3 .

Čtverec grafu G  je graf G 2 , který má stejnou množinu vrcholů jako graf G a ve kterém dva vrcholy sousedí právě tehdy, když je vzdálenost mezi nimi v G nejvýše dva. Fleischerova věta říká, že druhá mocnina konečného vertex-2-spojeného grafu se třemi nebo více vrcholy musí být vždy hamiltonovská. Ekvivalentně mohou být vrcholy libovolného 2-vrcholově spojeného grafu G uspořádány v cyklickém pořadí tak, že sousední vrcholy v tomto pořadí v G jsou od sebe nanejvýš dva.

Rozšíření

Ve Fleischnerově větě lze omezit hamiltonovský cyklus tak, aby zahrnoval tři vybrané hrany procházející dvěma vybranými vrcholy [1] [2] .

Kromě toho, že obsahuje hamiltonovský cyklus, čtverec 2-vrcholově spojeného grafu G musí být také hamiltonovský (což znamená, že má hamiltonovskou cestu začínající a končící v libovolných dvou vybraných vrcholech) a 1-hamiltonovský (to znamená, že pokud odstraníte jakýkoli vrchol, zbývající graf bude obsahovat také hamiltonovský cyklus) [3] [4] . Graf musí být také vertex - pancyklický , což znamená, že pro jakýkoli vrchol v a jakékoli celé číslo k s 3 ≤ k ≤ | V ( G )| existuje cyklus délky k obsahující v [5] .

Pokud graf G není 2-vrcholově propojený, jeho čtverec může, ale nemusí mít hamiltonovský cyklus a určení, zda graf takový cyklus má, je NP-úplný problém [6] [7] .

Nekonečný graf nemůže mít hamiltonovský cyklus, protože každý cyklus je konečný, ale Carsten Thomassen dokázal, že v případě, kdy G je nekonečný lokálně konečný graf s vrcholem-2-spojeným jedním koncem, pak G 2 nutně má dvojnásobně nekonečná hamiltonovská cesta [8] . Obecněji, jestliže G je lokálně konečný, 2-vrcholově spojený a má libovolný počet konců, pak G 2 má Hamiltonův cyklus. V kompaktním topologickém prostoru , vytvořeném zpracováním grafu jako jednoduchého komplexu a přidáním bodu navíc v nekonečnu pro každý konec grafu, je hamiltonovský cyklus definován jako podprostor, který je homeomorfní k euklidovskému kruhu a pokrývá všechny vrcholy [9 ] [10] .

Historie

Důkaz teorému byl oznámen Herbertem Fliashnerem v roce 1971 a publikován v roce 1974, čímž se vyřešil Nash-Williamsův dohad z roku 1966 , který také nezávisle prohlásil L.W. Bynik a Plummer [11] . Nash-Williams ve své recenzi Fleischnerova článku píše, že vyřešil „známý problém, který několik let mařil vynalézavost ostatních teoretiků grafů“ [12] .

Fleischerův původní důkaz byl obtížný. Václav Chvátal ve své práci, ve které zavedl pojem tuhosti grafu , poznamenal, že druhá mocnina vrcholově - k -spojeného grafu je nutně k -rigidní. Předpokládal, že 2-rigidní grafy jsou hamiltonovské, což by vedlo k dalšímu důkazu Fleischerovy věty [13] [7] . Protipříklady k této domněnce byly později nalezeny [14] , ale možnost, že by konečná hranice tuhosti mohla implikovat hamiltonianitu, zůstala důležitým otevřeným problémem v teorii grafů. Jednodušší důkaz jak Fleischnerovy věty, tak jejího rozšíření o Chartranda, Hobbse, Younga a Kapuura [3] podal Riha [15] [7] [4] , další zjednodušený důkaz věty podal Georgakopoulus [16] [ 4]] [10] .

Poznámky

  1. ↑ Fleischner 1976 , str. 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 )), reakce na Bondyho hypotézu ( Bondy, 1971 ).
  6. ↑ Underground, 1978 .
  7. ↑ 1 2 3 Bondy, 1995 .
  8. ↑ Thomassen (1978) .
  9. ↑ Georgakopoulos, 2009b .
  10. ↑ 12. Diestel , 2012 .
  11. ↑ Fleischner (1974 ). Dřívější hypotézy viz Fleischner a Chartrand, Lesniak a Zhang ( Chartrand, Lesniak, Zhang (2010 )).
  12. ↑ MR : 0332573 .
  13. ↑ Chvátal, 1973 .
  14. ↑ Bauer, Broersma, Veldman, 2000 .
  15. ↑ Shiha, 1991 .
  16. ↑ Georgakopoulos, 2009a .

Literatura