Clebschův graf - Clebsch graph
V matematický pole teorie grafů, Clebschův graf je jeden ze dvou komplementární grafy na 16 vrcholech,běžný graf se 40 hranami a 10 pravidelným grafem s 80 hranami. Varianta s 80 okraji je objednávka 5 graf na polovinu krychle; to bylo nazýváno názvem Clebschova grafu Seidelem (1968)[2] kvůli jeho vztahu ke konfiguraci 16 čar na kvartickém povrchu objeveném v roce 1868 německým matematikem Alfred Clebsch. U varianty se 40 okraji je objednávka 5 skládaný krychlový graf; je také známý jako Graf Greenwood – Gleason po práci Roberta E. Greenwooda a Andrew M. Gleason (1955 ), který ji použil k vyhodnocení Ramseyovo číslo R(3,3,3) = 17.[3][4][5]
Konstrukce
Objednávka-5 skládaný krychlový graf (5-pravidelný Clebschův graf) lze zkonstruovat přidáním hran mezi protilehlé páry vrcholů v 4rozměrném hyperkrychlovém grafu. (V n-dimenzionální hyperkrychle, dvojice vrcholů jsou naproti pokud má nejkratší cesta mezi nimi n hrany.) Alternativně může být vytvořen z 5rozměrného hyperkrychlového grafu pomocí identifikace společně (nebo uzavírat smlouvy) každý protilehlý pár vrcholů.
Další konstrukcí, vedoucí ke stejnému grafu, je vytvoření vrcholu pro každý prvek prvku konečné pole GF (16), a spojit dva vrcholy hranou, kdykoli je rozdíl mezi odpovídajícími dvěma prvky pole a dokonalá kostka.[6]
Objednávka-5 graf na polovinu krychle (10-pravidelný Clebschův graf) je doplněk 5 pravidelného grafu. Může být také vytvořeno z vrcholů 5rozměrné hyperkrychle spojením párů vrcholů, jejichž Hammingova vzdálenost jsou přesně dva. Tato konstrukce je instancí stavby Frankl – Rödlovy grafy. Produkuje dvě podmnožiny 16 vrcholů, které jsou navzájem odpojeny; oba poloviční čtverce hyperkrychle jsou izomorfní do 10 pravidelného Clebschova grafu. Dvě kopie 5-pravidelného Clebschova grafu mohou být vyrobeny stejným způsobem z 5-dimenzionální hyperkrychle spojením párů vrcholů, jejichž Hammingova vzdálenost je přesně čtyři.
Vlastnosti
5-pravidelný Clebschův graf je a silně pravidelný graf stupně 5 s parametry .[7][8]Jeho doplněk, 10 pravidelný Clebschův graf, je tedy také silně pravidelný graf,[1][4] s parametry .
5 pravidelný Clebschův graf je hamiltonián, nerovinný a ne eulerian. Je to také 5-připojen k vrcholu a 5-připojeno k okraji. The indukovaný podgraf deseti nesousedícími jakéhokoli vrcholu v tomto grafu tvoří izomorfní kopie Petersenův graf.
Má to tloušťka knihy 4 a číslo fronty 3.[9]

Okraje kompletní graf K.16 mohou být rozděleny do tří disjunktních kopií 5 pravidelného Clebschova grafu. Protože Clebschův graf je a graf bez trojúhelníků, to ukazuje, že existuje trojúhelníkové zbarvení okrajů K.16; to znamená, že Ramseyovo číslo R(3,3,3) popisující minimální počet vrcholů v úplném grafu bez tříbarevnosti bez trojúhelníků je nejméně 17. Greenwood & Gleason (1955) použili tuto konstrukci jako součást svého důkazu, že R(3,3,3) = 17.[5][10]
Může být 5-pravidelný Clebschův graf barevný se čtyřmi barvami, ale ne se třemi: jeho největší nezávislá sada má pět vrcholů, což nestačí k rozdělení grafu do tří nezávislých barevných tříd. Obsahuje jako indukovaný podgraf the Grötzschův graf, nejmenší bez trojúhelníků čtyřchromatický graf a každý čtyřbarevný indukovaný podgraf Clebschova grafu je supergrafem Grötzschova grafu. Silněji každý trojúhelníkový čtyřchromatický graf bez č indukovaná cesta délky šest nebo více je indukovaný podgraf Clebschova grafu a indukovaný supergraf Grötzschova grafu.[11]
5-pravidelný Clebschův graf je Kellerův graf dimenze dva, která je součástí rodiny grafů používaných k hledání vrstev vysokodimenzionálních Euklidovské prostory podle hyperkrychle žádné dva se nesetkávají tváří v tvář.
5-běžný Clebschův graf lze vložit jako a běžná mapa v orientovatelném potrubí rodu 5, tvořící pětiúhelníkové tváře; a na neorientovatelném povrchu rodu 6, tvořící čtyřboké tváře.
Algebraické vlastnosti
The charakteristický polynom 5-pravidelného Clebschova grafu je . Protože tento polynom lze zcela započítat do lineárních výrazů s celočíselnými koeficienty, je Clebschův graf integrální graf: své spektrum skládá se výhradně z celých čísel.[4] Clebschův graf je jediným grafem s tímto charakteristickým polynomem, což z něj činí graf určený svým spektrem.
5-pravidelný Clebschův graf je a Cayleyův graf se skupinou automorfismu řádu 1920, izomorfní s Skupina coxeterů . Jako Cayleyův graf působí jeho skupina automorfismu přechodně na své vrcholy, čímž se stává vrchol tranzitivní. Ve skutečnosti je oblouk tranzitivní, proto hrana tranzitivní a vzdálenost tranzitivní. Je to také připojeno-homogenní, což znamená, že každý izomorfismus mezi dvěma spojenými indukovanými podgrafy lze rozšířit na automorfismus celého grafu.
Galerie
Clebschův graf je Hamiltonian.
The achromatické číslo Clebschova grafu je 8.
The chromatické číslo Clebschova grafu je 4.
The chromatický index Clebschova grafu je 5.
Konstrukce Clebschova grafu z a hyperkrychlový graf.
Reference
- ^ A b Weisstein, Eric W. „Clebschův graf“. From MathWorld — A Wolfram Web Resource. Citováno 2009-08-13.
- ^ J. J. Seidel, Silně pravidelné grafy s (-1,1,0) maticí sousedství s vlastní hodnotou 3, Lin. Alg. Appl. 1 (1968) 281-298.
- ^ Clebsch, A. (1868), „Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen“, Journal für die reine und angewandte Mathematik, 69: 142–184.
- ^ A b C Clebschův graf na domovské stránce Billa Cherowitza
- ^ A b Greenwood, R.E .; Gleason, A. M. (1955), „Kombinatorické vztahy a chromatické grafy“, Kanadský žurnál matematiky, 7: 1–7, doi:10.4153 / CJM-1955-001-4, PAN 0067467.
- ^ De Clerck, Frank (1997). "Konstrukce a charakterizace (polo) dílčích geometrií". Letní škola konečných geometrií. p. 6.
- ^ Godsil, C.D. (1995). „Problémy v algebraické kombinatorice“ (PDF). Electronic Journal of Combinatorics. 2: 3. Citováno 2009-08-13.
- ^ Peter J. Cameron Silně pravidelné grafy na DesignTheory.org, 2001
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Sun, Hugo S .; Cohen, M. E. (1984), „Snadný důkaz vyhodnocení Ramseyova čísla ze strany Greenwood – Gleason R(3,3,3)" (PDF), Fibonacciho čtvrtletně, 22 (3): 235–238, PAN 0765316.
- ^ Randerath, Bert; Schiermeyer, Ingo; Tewes, Meike (2002), „Tříbarevnost a zakázané podgrafy. II. Polynomiální algoritmy“, Diskrétní matematika, 251 (1–3): 137–153, doi:10.1016 / S0012-365X (01) 00335-1, PAN 1904597.