Hrabě z Herschelu

V teorii grafů  je Herschelův graf bipartitní neorientovaný graf s 11 vrcholy a 18 hranami, nejmenší nehamiltonovský polyhedrální graf. Graf je pojmenován po britském astronomovi A. S. Herschel , který napsal ranou práci o hře Ikosian od Williama Rowana Hamiltona  – Herschelův graf dává nejmenší konvexní mnohostěn , pro který hra nemá řešení. Herschelův článek však popisuje řešení pro hru „Ikosian“ pouze pro čtyřstěn a dvacetistěn a nepopisuje Herschelův graf [1] .

Vlastnosti

Herschelův graf je rovinný  – lze jej kreslit v rovině bez křížení hran. Je také spojen s vrcholem 3 —  odstraněním libovolných dvou vrcholů zůstane podgraf připojený. Proto podle Steinitzovy věty Goldnerův graf - Harari je polyedrický graf  - existuje konvexní mnohostěn ( enneahedron ), jehož kostrou je Herschelův graf [2] . Herschelův graf je také bipartitní  – jeho vrcholy lze rozdělit do dvou podmnožin po pěti a šesti vrcholech tak, že každá hrana má koncové body v obou sadách (červená a modrá podmnožina na obrázku).

Jako každý jiný bipartitní graf je Herschelův graf dokonalý  – chromatické číslo libovolného vygenerovaného podgrafu se rovná velikosti největší kliky tohoto podgrafu. Graf má chromatický index 4, obvod 4, poloměr 3 a průměr 4.

Hamiltonian

Jelikož je graf bipartitní a má lichý počet vrcholů, neobsahuje Hamiltonovský cyklus (cyklus hran, který prochází každým vrcholem právě jednou). V každém bipartitním grafu musí každý cyklus střídavě procházet oběma sadami vrcholů, a proto musí obsahovat stejný počet vrcholů obou typů a mít sudou délku. Cyklus procházející každým z jedenácti vrcholů tedy nemůže existovat. Graf je minimální nehamiltonovský polyedrický graf, bez ohledu na to, jak se měří velikost grafu – počtem vrcholů, hran nebo ploch [3] . Existuje další polyedrický graf s 11 vrcholy, který nemá hamiltonovské cykly (konkrétně Goldner-Harariho graf [4] ), ale neexistuje žádný graf s menším (nebo stejným) počtem hran [2] .

Všechny vrcholy Herschelova grafu, s výjimkou tří, mají třetí stupeň. Tateova domněnka [5] uvádí, že polyhedrální graf, ve kterém má jakýkoli vrchol třetí stupeň , musí být hamiltonovský, ale je vyvrácen Tuttovým protipříkladem, Tuttovým mnohem větším grafem [6] . Aktualizace Tuttovy domněnky, Barnettova domněnka , že jakýkoli bipartitní 3-pravidelný polyedrický graf je hamiltonovský, zůstává otevřená [7] .

Herschelův graf také uvádí příklad polyedrického grafu, pro který nelze prostřední graf rozdělit na dva nekřížící se hamiltonovské cykly. Prostřední graf Herschelova grafu je 4- pravidelný graf s 18 vrcholy, jedním pro každou hranu Herschelova grafu. Dva vrcholy sousedí ve středním grafu, jestliže odpovídající hrany Herschelova grafu jdou postupně na jedné z jeho ploch [8] .

Algebraické vlastnosti

Herschelův graf není vertex-tranzitivní a jeho skupina plného automorfismu je izomorfní s dihedrální grupou řádu 12 , grupou symetrie pravidelného šestiúhelníku , včetně rotací i odrazů. Libovolná permutace jeho vrcholů čtvrtého stupně může být reprezentována grafovým automorfismem a existuje i netriviální automorfismus, který permutuje zbývající vrcholy bez ovlivnění vrcholů čtvrtého stupně.

Charakteristický polynom Herschelova grafu je .

Poznámky

1. ↑ AS Herschel. pane Wm. Hamiltonova Icosian Game  // Čtvrtletní žurnál čisté a aplikované matematiky . - 1862. - T. 5 . - S. 305 .
2. ↑ 1 2 H. S. M. Coxeter. Pravidelné polytopy . - Dover, 1973. - S.  8 .
3. ↑ David Barnette, Ernest Jučovič. Hamiltonovské obvody na 3-polytopech // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 1 . - S. 54-59 . - doi : 10.1016/S0021-9800(70)80054-0 .
4. ↑ Weisstein, Eric W. Goldner-Harary Graph  na webu Wolfram MathWorld .
5. ↑ P.G. Tait. Listing's Topology  // Filosofický časopis (5. s.). - 1884. - T. 17 . - S. 30-46 . . Přetištěno ve Scientific Papers , sv. II, str. 85-98.
6. ↑ WT Tutte. O hamiltonovských okruzích  // Journal of the London Mathematical Society. - 1946. - T. 21 , čís. 2 . - S. 98-101 . - doi : 10.1112/jlms/s1-21.2.98 .
7. ↑ Robert Samal. Barnettova domněnka . — Zahrada otevřených problémů, 11. června 2007.
8. ↑ JA Bondy, R. Häggkvist. Hranové disjunktní Hamiltonovy cykly ve 4-pravidelných rovinných grafech // Aequationes Mathematicae. - 1981. - T. 22 , no. 1 . - S. 42-45 . - doi : 10.1007/BF02190157 .

Odkazy

• Weisstein, Eric W. Herschel Graph  (anglicky) na webových stránkách Wolfram MathWorld .