110 csúcsos Ivanov-Iofinova gráf

A 110 csúcsos Ivanov-Iofinova gráf  egy félszimmetrikus köbös gráf 110 csúcsgal és 165 éllel.

Tulajdonságok

Ivanov és Iofinova 1985-ben bebizonyította, hogy létezik öt és csak öt félszimmetrikus köbös bipartit gráf, amelyek automorfizmuscsoportjai primitív módon hatnak a bipartit gráf minden egyes részein [1] . A legkisebb ilyen gráfnak 110 csúcsa van. A másik négynek 126, 182, 506 és 990 csúcsa van [2] . A 126 csúcsból álló Ivanov-Iofinova gráf 12 cellás Tatta néven is ismert .

A 110 csúcsos Ivanov-Iofinova gráf átmérője (a csúcspárok legnagyobb távolsága) 7. A sugara is 7. A kerülete 10.

A gráf 3- és 3-él-összekötésű  – a szétkapcsoláshoz legalább három élt vagy három csúcsot el kell távolítania.

Színező oldal

A 110 csúcsból álló Ivanov-Iofinova gráf kromatikus száma 2 – csúcsai két színnel színezhetők úgy, hogy két azonos színű csúcs ne legyen éllel összekötve. A kromatikus indexe 3 - a gráf élei 3 színben színezhetők úgy, hogy ne konvergáljon két azonos színű él ugyanabban a csúcsban.

Algebrai tulajdonságok

A gráf karakterisztikus polinomja: . A szimmetriacsoport a PGL 2 (11) projektív csoport 1320 elemmel [3] .

Félszimmetria

Kevés gráfnak van félszimmetriája – a legtöbb éltranzitív gráf csúcstranzitív is. A legkisebb félszimmetrikus gráf a 20 csúcsos Folkman-gráf , amely 4-reguláris. A három legkisebb köbös félszimmetrikus gráf az 54 csúcsos Gray gráf , ez a legkisebb a 110 csúcsos Ivanov-Iofinova gráf és a 112 csúcsos Ljubljana gráf [4] [5] .

Jegyzetek

1. ↑ Han és Lu affin primitív csoportok és félszimmetrikus gráfok . kombinatorials.org . Letöltve: 2015. augusztus 12. Az eredetiből archiválva : 2018. október 3.. (határozatlan)
2. ↑ Weisstein, Eric Iofinova-Ivanov Graphs . wolfram mathworld . Volfrám. Letöltve: 2015. augusztus 11. Az eredetiből archiválva : 2019. január 19. (határozatlan)
3. ↑ Iofinova, Ivanov, 2013 , p. 470.
4. ↑ Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
5. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , p. 255–294.

Irodalom

• Iofinova ME, Ivanov AA Investigations in Algebraic Theory of Combinatorial Objects / IA Faradžev, AA Ivanov, MH Klin, AJ Woldar. - kiadó = Springer-Science + Business Media, BV, 2013. - T. 94. - (Matematika és alkalmazásai, szovjet sorozat). - ISBN 978-90-481-4195-1 . — ISBN 978-94-017-1972-8 . Könyvfordítás
  • Tanulmányok a kombinatorikus objektumok algebrai elméletében: Tr. Szeminárium / Felelős szerk. M. Kh. Klin, I. A. Faradzsev. - M. : VNIISI, 1985. - T. 185.
• Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph  // IMFM Preprints. - Ljubljana: Matematikai, Fizikai és Mechanikai Intézet, 2002. - V. 40 , no. 845 .
• Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. Félszimmetrikus köbös gráfok összeírása akár 768 csúcson // Journal of Algebraic Combinatorics. - 2006. - T. 23 . – S. 255–294 . - doi : 10.1007/s10801-006-7397-3 .
• Ivanov A. A., Iofinova M. E. Biprimitív köbös gráfok // Tanulmányok a kombinatorikus objektumok algebrai elméletében. - M. , 1985. - S. 137-152. - (Sorozat: Összoroszországi Rendszerkutatási Kutatóintézet. A szeminárium anyaga).
• Alekszandr Anatoljevics Ivanov. Alcsoport pályái hosszának kiszámítása tranzitív permutációs csoportban // Módszerek és programok komplex rendszerek tanulmányozásához. Fiatal tudósok konferenciájának anyaga. - M. : VNIISI, 1983. - S. 3-7.
• Ivanov AV On Edge But Not Vertex Tranzitív reguláris gráfok // Kombinatorikus tervezéselmélet / Szerk. CJ Colbourn és R. Mathon. - Amszterdam, New York, Oxford, Tokió, Észak-Holland: Elsevier Science Publishers BV, 1987. - 149/34. – S. 273–285. — (North-Holland Mathematics studies/Annals of Discrete Mathematics). — ISBN 0-444-70328-4 .