Gráfico de Ivanov-Iofinova de 110 vértices
| Gráfico de Ivanov-Iofinova de 110 vértices | |
|---|---|
| picos | 110 |
| costillas | 165 |
| Radio | 7 |
| Diámetro | 7 |
| Circunferencia | diez |
| automorfismos | 1320 (PGL 2 (11)) |
| número cromático | 2 |
| índice cromático | 3 |
| Propiedades |
Hamiltoniano cúbico bipartito semisimétrico |
El gráfico de Ivanov-Iofinova de 110 vértices es un gráfico cúbico semisimétrico con 110 vértices y 165 aristas.
Propiedades
Ivanov e Iofinova demostraron en 1985 la existencia de cinco y sólo cinco grafos bipartitos cúbicos semisimétricos cuyos grupos de automorfismos actúan primitivamente sobre cada parte del grafo bipartito [1] . El gráfico más pequeño tiene 110 vértices. Los otros cuatro tienen 126, 182, 506 y 990 vértices [2] . El gráfico Ivanov-Iofinova de 126 vértices también se conoce como Tatta de 12 celdas .
El diámetro del gráfico Ivanov-Iofinova de 110 vértices (la distancia más grande entre cualquier par de vértices) es 7. Su radio también es 7. Su circunferencia es 10.
El gráfico tiene 3 conexiones y 3 aristas : para desconectarlo, debe eliminar al menos tres aristas o tres vértices.
Dibujo para colorear
El número cromático del gráfico Ivanov-Iofinova de 110 vértices es 2: sus vértices se pueden colorear con dos colores para que no haya dos vértices del mismo color conectados por un borde. Su índice cromático es 3: los bordes del gráfico se pueden colorear en 3 colores para que no converjan dos bordes del mismo color en el mismo vértice.
Propiedades algebraicas
El polinomio característico de la gráfica es . El grupo de simetría es el grupo proyectivo PGL 2 (11) con 1320 elementos [3] .
Semisimetría
Pocos gráficos exhiben semisimetría: la mayoría de los gráficos transitivos de borde también son transitivos de vértice. El gráfico semisimétrico más pequeño es el gráfico de Folkman de 20 vértices , que es 4-regular. Los tres gráficos semisimétricos cúbicos más pequeños son el gráfico de Gray con 54 vértices, el más pequeño de los gráficos de Ivanov-Iofinova con 110 vértices y el gráfico de Ljubljana con 112 vértices [4] [5] .
Notas
- ↑ Grupos primitivos afines a Han y Lu y gráficos semisimétricos . combinatorias.org . Consultado el 12 de agosto de 2015. Archivado desde el original el 3 de octubre de 2018.
- ↑ Weisstein, Eric Iofinova-Ivanov Gráficos . Wolframio mundo matemático . Wolframio. Consultado el 11 de agosto de 2015. Archivado desde el original el 19 de enero de 2019.
- ↑ Iofinova, Ivanov, 2013 , pág. 470.
- ↑ Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
- ↑ Conder, Malnič, Marušič, Potočnik, 2006 , pág. 255–294.
Literatura
- Iofinova ME, Ivanov AA Investigaciones en teoría algebraica de objetos combinatorios / IA Faradžev, AA Ivanov, MH Klin, AJ Woldar. - editor = Springer-Science + Business Media, BV, 2013. - T. 94. - (Matemáticas y sus aplicaciones, serie soviética). - ISBN 978-90-481-4195-1 . — ISBN 978-94-017-1972-8 . traducción de libros
- Estudios en la teoría algebraica de objetos combinatorios: Tr. Seminario / Responsable edición 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: Instituto de Matemáticas, Física y Mecánica, 2002. - V. 40 , no. 845 .
- Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. Un censo de gráficos cúbicos semisimétricos en hasta 768 vértices // Journal of Algebraic Combinatorics. - 2006. - T. 23 . — S. 255–294 . -doi : 10.1007/ s10801-006-7397-3 .
- Ivanov A. A., Iofinova M. E. Gráficos cúbicos biprimitivos // Estudios en la teoría algebraica de objetos combinatorios. - M. , 1985. - S. 137-152. - (Serie: Instituto de Investigación de toda Rusia para la Investigación del Sistema. Actas del Seminario).
- Alexander Anatolievich Ivanov. Cálculo de las longitudes de órbitas de un subgrupo en un grupo de permutaciones transitivas // Métodos y programas para el estudio de sistemas complejos. Actas de la conferencia de jóvenes científicos. - M. : VNIISI, 1983. - S. 3-7.
- Ivanov AV Gráficos regulares transitivos en el borde pero no en el vértice // Teoría del diseño combinatorio / Ed. CJ Colbourn y R. Mathon. - Ámsterdam, Nueva York, Oxford, Tokio, Holanda Septentrional: Elsevier Science Publishers BV, 1987. - Vol. 149/34. — S. 273–285. — (Estudios matemáticos de Holanda Septentrional/Annals of Discrete Mathematics). — ISBN 0-444-70328-4 .