Ljubljana grófja

Ljubljana grófja

Ljubljana grófja Heawood gróf fedőgrófjaként
Csúcsok 112
borda 168
Sugár 7
Átmérő nyolc
Heveder tíz
Automorfizmusok 168
Kromatikus szám 2
Kromatikus index 3
Tulajdonságok Köbös
Hamiltoni
félszimmetrikus
 Médiafájlok a Wikimedia Commons oldalon

A ljubljanai gráf egy irányítatlan bipartit gráf , 112 csúcsával és 168 élével [1] .

A gráf egy köbös gráf, melynek átmérője 8, sugara 7, kromatikus száma 2, kromatikus indexe 3. kerülete 10, és pontosan 168 10 hosszúságú ciklusa van. 168 12 hosszúságú ciklus is létezik [2] .

Épület

A ljubljanai gráf hamiltoni gráf, és egy LCF kódból szerkeszthető  : [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 .

A ljubljanai gráf a ljubljanai konfiguráció Lévy-gráfja, egy négyszög nélküli konfiguráció, 56 vonallal és 56 ponttal [2] . Ebben a konfigurációban minden egyenes pontosan 3 pontot tartalmaz, minden pont pontosan 3 egyeneshez tartozik, és bármely két egyenes legfeljebb egy pontban metszi egymást.

Algebrai tulajdonságok

A ljubljanai gráf automorfizmuscsoportja egy 168-as rendű csoport. Az élekre tranzitívan hat, de a csúcsokra nem - vannak szimmetriák , amelyek bármelyik élt bármely másik élre viszi, de nincs olyan szimmetria, amely bármely csúcsot bármely másik csúcsba vinné. . Ezért a ljubljanai gráf egy félszimmetrikus gráf , a harmadik köbös félszimmetrikus gráf az 54 csúcsos Gray -gráf és a 110 csúcsos Ivanov-Iofinova gráf után [3] .

A ljubljanai gráf jellegzetes polinomja az

Történelem

A ljubljanai grófot először 1993-ban publikálta Brouwer, Dejter és Thomassen [4] a Dejter Count [5] önkiegészítő részgráfjaként .

1972-ben Brouwer már egy 112 csúcsos éltranzitív, de nem csúcstranzitív köbös gráfról beszélt, amelyet Foster talált meg , de nem publikált [6] . Conder, Malnic, Marušić és Potocnik 2002-ben fedezték fel újra ezt a 112 csúcsból álló gráfot, és Szlovénia fővárosa után Ljubljana grófjának nevezték el [2] . Bebizonyították, hogy a gráf az egyetlen 112 csúcsú éltranzitív, de nem csúcstranzitív köbös gráf, és ezért ugyanaz a gráf, amelyet Foster talált.

Galéria

Jegyzetek

  1. ↑ Weisstein, Eric W. Ljubljana grafikonja  a Wolfram MathWorld webhelyén .
  2. ↑ 1 2 3 Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
  3. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , p. 255-294.
  4. ↑ Brouwer, Dejter, Thomassen, 1993 , p. 25-29.
  5. ↑ Klin, Lauri, Ziv-Av, 2012 , p. 1175–1191.
  6. ↑ Bouwer, 1972 , p. 32-40.

Irodalom