Lublaňský graf - Ljubljana graph - Wikipedia

Lublaňský graf
Lublaňský graf - reprezentace Heawood.jpg
Lublaňský graf jako a krycí graf z Heawoodův graf
Vrcholy112
Hrany168
Poloměr7
Průměr8
Obvod10
Automorfismy168
Chromatické číslo2
Chromatický index3
VlastnostiKrychlový
Polosymetrické
Hamiltonian
Tabulka grafů a parametrů

V matematický pole teorie grafů, Lublaňský graf je neorientovaný bipartitní graf s 112 vrcholy a 168 hrany.[1]

Je to kubický graf o průměru 8, poloměru 7, chromatické číslo 2 a chromatický index 3. Jeho obvod je 10 a je v něm přesně 168 cyklů délky 10. Existuje také 168 cyklů o délce 12.[2]

Konstrukce

Lublaňský graf je Hamiltonian a lze je postavit z LCF notace  : [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39]2.

Lublaňský graf je Leviho graf konfigurace v Lublani, konfigurace bez čtyřúhelníků s 56 linkami a 56 body.[2] V této konfiguraci obsahuje každý řádek přesně 3 body, každý bod patří přesně 3 řádkům a jakékoli dva řádky se protínají maximálně v jednom bodě.

Algebraické vlastnosti

The automorfická skupina lublaňského grafu je skupina řádu 168. Působí přechodně na okraje grafu, ale ne na jeho vrcholy: existují symetrie přičemž každý okraj k jakékoli jiné hraně, ale ne každý vrchol k jinému vrcholu. Proto je graf v Lublani a polosymetrický graf, třetí nejmenší možný kubický polosymetrický graf po Šedý graf na 54 vrcholech a Iofinova-Ivanovův graf na 110 vrcholech.[3]

Charakteristický polynom Lublaňského grafu je

Dějiny

Lublaňský graf byl poprvé publikován v roce 1993 autorem Brouwer, Dejter a Thomassen[4]jako doplňkový podgraf Dejterův graf.[5]

V roce 1972 již Bouwer mluvil o kubickém grafu s hranami 112 vrcholů, ale ne vrcholem, který našel R. M. Foster, přesto nepublikováno.[6] Conder, Malnič, Marušič, Pisanski a Potočnik znovuobjevili tento graf s vrcholy 112 v roce 2002 a pojmenovali jej Lublaň graf za kapitálem Slovinsko.[2] Dokázali, že to byl jedinečný kubický graf s hranami 112, ale ne vrcholem, a proto to byl graf nalezený Fosterem.

Galerie

  • Lublaňský graf je hamiltoniánský a bipartitní

  • The chromatický index lublaňského grafu je 3.

  • Alternativní kresba Lublaňského grafu.

  • Lublaňský graf je Leviho graf této konfigurace.

Reference

  1. ^ Weisstein, Eric W. „Lublaňský graf“. MathWorld.
  2. ^ A b C Conder, M.; Malnič, A .; Marušič, D .; Pisanski, T .; a Potočnik, P. „Lublaňský graf.“ 2002. [1].
  3. ^ Marston Conder, Aleksander Malnič, Dragan Marušič a Primž Potočnik. „Sčítání polosymetrických kubických grafů až na 768 vrcholech.“ Journal of Algebraic Combinatorics: An International Journal. Svazek 23, číslo 3, strany 255-294, 2006.
  4. ^ Brouwer, A.E .; Dejter, I.J .; a Thomassen, C. „Vysoce symetrické podgrafy hyperkrychlí.“ J. Algebraic Combinat. 2, 25-29, 1993.
  5. ^ Klin M .; Lauri J .; Ziv-Av M. „Vazby mezi dvěma semisymetrickými grafy na 112 vrcholech optikou asociačních schémat“, Jour. SymbolicComput., 47–10, 2012, 1175–1191.
  6. ^ Bouwer, I. A. „Na hraně, ale ne vrcholné přechodné pravidelné grafy.“ J. Combin. Čt. Ser. B 12, 32-40, 1972.