Hrabě z Lublaně

hrabě z Lublaně

Hrabě z Lublaně jako krycí hrabě hrabě Heawood
Vrcholy 112
žebra 168
Poloměr 7
Průměr osm
obvod deset
Automorfismy 168
Chromatické číslo 2
Chromatický index 3
Vlastnosti Kubický
hamiltonovský
polosymetrický
 Mediální soubory na Wikimedia Commons

Lublaňský graf je neorientovaný bipartitní graf se 112 vrcholy a 168 hranami [1] .

Graf je kubický graf o průměru 8, poloměru 7, chromatickém čísle 2 a chromatickém indexu 3. Jeho obvod je 10 a má přesně 168 cyklů délky 10. Dále je zde 168 cyklů délky 12 [2] .

Budova

Lublaňský graf je hamiltonovský a lze jej sestavit z kódu LCF  : [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 Lévyho graf lublaňské konfigurace, konfigurace bez čtyřúhelníků s 56 čarami a 56 body [2] . V této konfiguraci obsahuje každá úsečka přesně 3 body, každý bod patří přesně 3 úsečkám a libovolné dvě úsečky se protínají nejvýše v jednom bodě.

Algebraické vlastnosti

Grupa automorfismu lublaňského grafu je grupa řádu 168. Působí tranzitivně na hrany, ale ne na vrcholy - existují symetrie , které přivádějí jakoukoli hranu k jakékoli jiné hraně, ale neexistuje žádná symetrie, která by přiváděla jakýkoli vrchol k jinému vrcholu. . Proto je lublaňský graf semisymetrickým grafem , třetím kubickým semisymetrickým grafem po Grayově grafu s 54 vrcholy a grafu Ivanov-Iofinova se 110 vrcholy [3] .

Charakteristickým polynomem lublaňského grafu je

Historie

Ljubljanský hrabě byl poprvé publikován v roce 1993 nakladatelstvím Brouwer, Dejter a Thomassen [4] jako samodoplňkový podgraf Hraběte Dejte [5] .

V roce 1972 už Brouwer mluvil o 112 vrcholovém hranově tranzitivním, ale ne vertexově tranzitivním kubickém grafu, který Foster našel , ale nepublikoval [6] . Conder, Malnic, Marušić a Potocnik znovuobjevili tento 112-vrcholový graf v roce 2002 a pojmenovali jej hrabě z Lublaně podle hlavního města Slovinska [2] . Dokázali, že graf byl jediným 112-vrcholovým hranově tranzitivním, ale ne vertexově tranzitivním kubickým grafem, a proto je to stejný graf, který našel Foster.

Galerie

Poznámky

  1. ↑ Weisstein, Eric W. Ljubljana Graph  na webu Wolfram MathWorld .
  2. ↑ 1 2 3 Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
  3. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , str. 255-294.
  4. ↑ Brouwer, Dejte, Thomassen, 1993 , str. 25-29.
  5. ↑ Klin, Lauri, Ziv-Av, 2012 , str. 1175–1191.
  6. ↑ Bouwer, 1972 , str. 32-40.

Literatura