hrabě Clebsha | |
---|---|
Vrcholy | 16 |
žebra | 40 |
Poloměr | 2 |
Průměr | 2 |
obvod | čtyři |
Automorfismy | 1920 |
Chromatické číslo | 4 [1] |
Vlastnosti |
Silně pravidelný Hamiltonovský graf Beztrojúhelníkový graf Cayleyho graf Vertexově tranzitivní Hraně tranzitivní Vzdálenostně tranzitivní |
Mediální soubory na Wikimedia Commons |
V teorii grafů je Clebschův graf chápán jako jeden ze dvou komplementárních grafů s 16 vrcholy. Jeden z nich má 40 hran a je 5 - běžný graf , druhý má 80 hran a je to 10-běžný graf. Varianta s 80 hranami je graf poloviční krychle5. řádu. Seidelem pojmenován hrabě z Clebsche v roce 1968 [2] kvůli jeho souvislosti s konfigurací čar povrchu čtvrtého řádu, objeveným v roce 1868 německým matematikem Alfredem Clebschem . Varianta se 40 hranami je skládací krychlový graf5. řádu. Známý je také jako Greenwood-Gleasonův graf podle práce Greenwooda a Gleasona [3] , ve které tento graf použili k výpočtu Ramseyho čísla R (3,3,3) = 17 [3] [4] [5 ] .
Graf skládací krychle5. řád (5-pravidelný Clebschův graf) lze sestrojit přidáním hran mezi protilehlé vrcholy 4-rozměrného hyperkrychlového grafu (V n - rozměrné hyperkrychli je dvojice vrcholů opačná, pokud nejkratší vzdálenost mezi nimi obsahuje n hran). Lze jej také sestavit z 5rozměrného grafu hyperkrychle stažením každého páru opačných vrcholů.
Další konstrukcí, která dává stejný graf, je vytvořit vrchol pro každý prvek konečného pole GF (16) a spojit dva vrcholy hranou, pokud je rozdíl odpovídajících prvků pole krychle [6] .
Graf půl kostky5. řád (10-běžný Clebschův graf) je doplňkem 5-pravidelného grafu. Lze jej také postavit z vrcholů 5-rozměrné hyperkrychle spojením dvojic vrcholů, mezi nimiž jsou Hammingova vzdálenost přesně dvě. Tato konstrukce tvoří dvě podmnožiny po 16 vrcholech, které nejsou vzájemně propojeny. Oba získané grafy jsou izomorfní s 10-regulárním Clebschovým grafem.
5-pravidelný Clebschův graf je silně pravidelný graf 5. stupně s parametry [7] [8] . Jeho doplněk, 10-pravidelný Clebschův graf, je také silně pravidelný [1] [5] .
5-pravidelný Clebschův graf je hamiltonovský , neplanární a neeulerovský . Oba grafy jsou spojeny 5 vrcholy a 5 hranami . Podgraf vytvořený deseti vrcholy, které nejsou sousedy žádného vrcholu v tomto grafu, je izomorfní s Petersenovým grafem .
Okraje kompletního grafu K 16 lze rozdělit na tři oddělené kopie 5-pravidelného Clebschova grafu. Protože Clebschův graf neobsahuje trojúhelníky , ukazuje to, že existuje trikolorní zbarvení bez trojúhelníků hran grafu K 16 . Ramseyho číslo R (3,3,3), které popisuje minimální počet vrcholů v kompletním grafu pod trikolorním zbarvením bez trojúhelníků, tedy nemůže být menší než 17. Greenwood a Gleason použili tuto konstrukci jako součást svého důkazu rovnost R (3,3, 3) = 17 [3] [9] .
5-běžný Clebschův graf je Kellerův graf dimenze dvě a patří do rodiny grafů používaných k nalezení pokrytí vysokorozměrných euklidovských prostorů hyperkrychlemi , které nemají společné plochy.
Charakteristickým polynomem 5-pravidelného Clebschova grafu je . Clebschův graf je tedy celočíselný graf – jeho spektrum se skládá výhradně z celých čísel [5] . Clebschův graf je jediný graf s tak charakteristickým polynomem.
5-pravidelný Clebschův graf je Cayleyův graf se skupinou automorfismu řádu 1920 izomorfní s Coxeterovou grupou . Jako v každém Cayleyově grafu působí skupina automorfismu na své vrcholy tranzitivně, takže je vertex-tranzitivní . Ve skutečnosti se jedná o symetrický graf , a proto je přechodově přechodný na hranu a přechod na vzdálenost .
Clebschův graf je hamiltonovský .
Achromatické číslo Clebschova grafu je 8.
Barevné číslo Clebschova grafu je 4.
Chromatická třída Clebschova grafu je 5.
Konstrukce Clebschova grafu z grafu hyperkrychle .