Hrabě z Gray

Grayův graf  je bipartitní neorientovaný graf s 54 vrcholy a 81 hranami. Graf je kubický  - libovolný vrchol patří právě třem hranám. Graf objevil Gray v roce 1932 (bez publikace), poté jej nezávisle objevil Bouwer v roce 1968 v reakci na otázku položenou Folkmanem v roce 1967. Grayův graf je pozoruhodný jako historicky první příklad kubického grafu, který má algebraickou vlastnost hrany, ale ne vertexové tranzitivity.

Barevné číslo Grayova grafu je 2, chromatický index  je 3 a poloměr a průměr jsou 6. Je to také nerovinný graf spojený se 3 vrcholy a se 3 okraji .

Konstrukce

Grayův graf lze sestavit [1] z 27 bodů mřížky 3×3×3 a 27 přímek rovnoběžných s osami a procházejících těmito body. Tato sada bodů a čar tvoří projektivní konfiguraci  — každým bodem procházejí přesně tři čáry a na každé přímce leží přesně tři body. Grayův graf je Leviho graf této konfigurace. Graf má vrchol pro každý bod a pro každou čáru této konfigurace a hranu pro každý pár bod-čára, pokud bod leží na přímce. Tuto konstrukci lze zobecnit (Bauwer 1972) na libovolnou dimenzi , čímž získáme -valenční Lévyho grafy s algebraickými vlastnostmi podobnými těm z Grayova grafu.

Může být také sestrojen jako Leviho graf pro hrany a trojúhelníkové plochy některých místně toroidních abstraktních pravidelných 4-polytopů [2] .

Marusic a Pisanski [3] poskytli některé alternativní metody pro konstrukci Grayova grafu. Jako každý jiný bipartitní graf ani Grayův graf neobsahuje cykly liché délky, ani cykly se čtyřmi nebo šesti vrcholy, takže obvod Grayova grafu je 8. Nejjednodušší orientovaná plocha, do které lze Grayův graf vložit je rodu 7 [4] .

Grayův graf je hamiltonovský a lze jej sestavit z LCF notace :

Algebraické vlastnosti

Grupa automorfismu grafu Gray je grupa řádu 1296. Působí tranzitivně na okrajích grafu, ale ne na jeho vrcholech – existují automorfismy, které přebírají jakoukoli hranu k jakékoli jiné hraně, ale neexistují žádné automorfismy, které by vrchol na jakýkoli jiný. Vrcholy odpovídající konfiguraci pod grafem mohou být symetrické pouze k vrcholům odpovídajícím konfiguračním bodům a vrcholy odpovídající čarám jsou symetrické pouze k vrcholům odpovídajícím čarám. Grayův graf je tedy semisymetrická grupa a je nejmenším možným kubickým semisymetrickým grafem.

Charakteristický polynom Grayova grafu je:

Galerie

• hrabě z Gray

• Chromatické číslo hraběte Graye je 2.

• chromatický index Grayova grafu je 3.

• Konfigurace, která je základem Graph Gray.

Poznámky

1. ↑ Bouwer, 1972 .
2. ↑ Monson, Pisanski, Schulte, Ivic-Weiss, 2007 .
3. ↑ Marusic, Pisanski, 2000 .
4. ↑ Marušič, Pisanski, Wilson, 2005 .

Odkazy

• Hranový, ale ne vrcholově tranzitivní kubický graf // Bulletin kanadské matematické společnosti. - 1968. - T. 11 . — S. 533–535 . - doi : 10.4153/CMB-1968-063-0 . .
• IZ Bouwer. Na hraně, ale ne na vrcholu tranzitivní pravidelné grafy // Journal of Combinatorial Theory, Series B. - 1972. - Vol . — S. 32–40 . - doi : 10.1016/0095-8956(72)90030-5 . .
• J Folkman. Pravidelné liniově symetrické grafy // Journal of Combinatorial Theory. - 1967. - T. 3 , vydání. 3 . — S. 533–535 . - doi : 10.1016/S0021-9800(67)80069-3 . .
• Dragan Marušic, Tomaž Pisanski. Revidovaný Grayův graf  // Journal of Graph Theory. - 2000. - T. 35 . — S. 1–7 . - doi : 10.1002/1097-0118(200009)35:1<1::AID-JGT1>3.0.CO;2-7 . .
• Dragan Marusic, Tomaž Pisanski, Steve Wilson. Rod Gray graph je 7 // European Journal of Combinatorics. - 2005. - T. 26 , no. 3–4 . — S. 377–385 . - doi : 10.1016/j.ejc.2004.01.015 . .
• B. Monson, T. Pisanski, E. Schulte, A. Ivic-Weiss. Semisymmetric Graphs from Polytopes // Journal of Combinatorial Theory, Series A. - 2007. - Vol. 114 , no. 3 . — S. 421–435 . - doi : 10.1016/j.jcta.2006.06.007 .
• Weisstein, Eric W. Gray Gray  (anglicky) na webových stránkách Wolfram MathWorld .
• Šedý graf je nejmenší graf svého druhu Archivován 22. února 2014 na Wayback Machine z MathWorld .