110-vertex Ivanov-Iofinova graf

Ivanov-Iofinova- grafen med 110 hjørner  er en semisymmetrisk kubisk graf med 110 hjørner og 165 kanter.

Egenskaber

Ivanov og Iofinova beviste i 1985 eksistensen af ​​fem og kun fem semisymmetriske kubiske todelte grafer, hvis automorfigrupper virker primitivt på hver del af den todelte graf [1] . Den mindste sådan graf har 110 hjørner. De andre fire har 126, 182, 506 og 990 hjørner [2] . Ivanov-Iofinova-grafen med 126 hjørner er også kendt som Tatta med 12 celler .

Diameteren af ​​Ivanov-Iofinova-grafen med 110 toppunkter (den største afstand mellem ethvert hjørnepar) er 7. Dens radius er også 7. Dens omkreds er 10.

Grafen er 3-forbundet og 3-kant-forbundet  - for at gøre den frakoblet skal du fjerne mindst tre kanter eller tre hjørner.

Farvelægningsside

Det kromatiske tal på Ivanov-Iofinova-grafen med 110 hjørner er 2 - dens hjørner kan farves med to farver, så ikke to hjørner af samme farve er forbundet med en kant. Dens kromatiske indeks er 3 - grafens kanter kan farves i 3 farver, så ikke to kanter af samme farve konvergerer i samme toppunkt.

Algebraiske egenskaber

Grafens karakteristiske polynomium er . Symmetrigruppen er den projektive gruppe PGL 2 (11) med 1320 elementer [3] .

Semisymmetri

Få grafer udviser semisymmetri - de fleste kanttransitive grafer er også toppunkttransitive. Den mindste semisymmetriske graf er Folkman-grafen med 20 hjørner , som er 4-regulær. De tre mindste kubiske semisymmetriske grafer er den grå graf med 54 toppunkter, denne mindste af Ivanov-Iofinova graferne med 110 toppunkter og Ljubljana grafen med 112 toppunkter [4] [5] .

Noter

1. ↑ Han og Lu Affine primitive grupper og semisymmetriske grafer . combinatorials.org . Hentet 12. august 2015. Arkiveret fra originalen 3. oktober 2018. (ubestemt)
2. ↑ Weisstein, Eric Iofinova-Ivanov Grafer . wolfram mathworld . Wolfram. Hentet 11. august 2015. Arkiveret fra originalen 19. januar 2019. (ubestemt)
3. ↑ Iofinova, Ivanov, 2013 , s. 470.
4. ↑ Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
5. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , s. 255-294.

Litteratur

• Iofinova ME, Ivanov AA Undersøgelser i algebraisk teori om kombinatoriske objekter / IA Faradžev, AA Ivanov, MH Klin, AJ Woldar. - udgiver = Springer-Science + Business Media, BV, 2013. - T. 94. - (Mathematics and Its Applications, sovjetiske serier). - ISBN 978-90-481-4195-1 . — ISBN 978-94-017-1972-8 . Bogoversættelse
  • Studier i den algebraiske teori om kombinatoriske objekter: Tr. Seminar / Ansvarlig udg. M. Kh. Klin, I. A. Faradzhev. - M. : VNIISI, 1985. - T. 185.
• Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph  // IMFM Preprints. - Ljubljana: Institut for Matematik, Fysik og Mekanik, 2002. - V. 40 , no. 845 .
• Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. En folketælling af semisymmetriske kubiske grafer på op til 768 hjørner // Journal of Algebraic Combinatorics. - 2006. - T. 23 . — S. 255–294 . - doi : 10.1007/s10801-006-7397-3 .
• Ivanov A. A., Iofinova M. E. Biprimitive kubiske grafer // Studier i den algebraiske teori om kombinatoriske objekter. - M. , 1985. - S. 137-152. - (Serie: All-Russian Research Institute for System Research. Proceedings of the Seminar).
• Alexander Anatolyevich Ivanov. Beregning af længderne af kredsløb for en undergruppe i en transitiv permutationsgruppe // Metoder og programmer til undersøgelse af komplekse systemer. Proceedings fra konferencen for unge forskere. - M. : VNIISI, 1983. - S. 3-7.
• Ivanov AV On Edge But Not Vertex Transitive Regular Graphs // Combinatorial Design Theory / Ed. CJ Colbourn og R. Mathon. - Amsterdam, New York, Oxford, Tokyo, Nordholland: Elsevier Science Publishers BV, 1987. - Vol. 149/34. — S. 273–285. — (North-Holland Mathematics studies/Annals of Discrete Mathematics). — ISBN 0-444-70328-4 .