Misplaced Pages

110-vertex Iofinova–Ivanov graph

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Semi-symmetric cubic graph with 110 vertices and 165 edges
110-vertex Iofinova–Ivanov graph
Vertices110
Edges165
Radius7
Diameter7
Girth10
Automorphisms1320 (PGL2(11))
Chromatic number2
Chromatic index3
Propertiessemi-symmetric
bipartite
cubic
Hamiltonian
Table of graphs and parameters

The 110-vertex Iofinova–Ivanov graph is, in graph theory, a semi-symmetric cubic graph with 110 vertices and 165 edges.

Properties

Iofinova and Ivanov proved in 1985 the existence of five and only five semi-symmetric cubic bipartite graphs whose automorphism groups act primitively on each partition. The smallest has 110 vertices. The others have 126, 182, 506 and 990. The 126-vertex Iofinova–Ivanov graph is also known as the Tutte 12-cage.

The diameter of the 110-vertex Iofinova–Ivanov graph, the greatest distance between any pair of vertices, is 7. Its radius is likewise 7. Its girth is 10.

It is 3-connected and 3-edge-connected: to make it disconnected at least three edges, or at least three vertices, must be removed.

Coloring

The chromatic number of the 110-vertex Iofina-Ivanov graph is 2: its vertices can be 2-colored so that no two vertices of the same color are joined by an edge. Its chromatic index is 3: its edges can be 3-colored so that no two edges of the same color met at a vertex.

Algebraic properties

The characteristic polynomial of the 110-vertex Iofina-Ivanov graph is ( x − 3 ) x 20 ( x + 3 ) ( x 4 − 8 x 2 + 11 ) 12 ( x 4 − 6 x 2 + 6 ) 10 {\displaystyle (x-3)x^{20}(x+3)(x^{4}-8x^{2}+11)^{12}(x^{4}-6x^{2}+6)^{10}} . The symmetry group of the 110-vertex Iofina-Ivanov is the projective linear group PGL2(11), with 1320 elements.

Semi-symmetry

Few graphs show semi-symmetry: most edge-transitive graphs are also vertex-transitive. The smallest semi-symmetric graph is the Folkman graph, with 20 vertices, which is 4-regular. The three smallest cubic semi-symmetric graphs are the Gray graph, with 54 vertices, this the smallest of the Iofina-Ivanov graphs with 110, and the Ljubljana graph with 112. It is only for the five Iofina-Ivanov graphs that the symmetry group acts primitively on each partition of the vertices.

References

  1. Han and Lu. "Affine primitive groups and Semisymmetric graphs". combinatorics.org. Retrieved 12 August 2015.
  2. Weisstein, Eric. "Iofinova-Ivanov Graphs". Wolfram MathWorld. Wolfram. Retrieved 11 August 2015.
  3. Iofinova and Ivanov (2013). Investigations in Algebraic Theory of Combinatorial Objects. Springer. p. 470. ISBN 9789401719728. Retrieved 12 August 2015.
  4. Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002), "The Ljubljana Graph" (PDF), IMFM Preprints, vol. 40, no. 845, Ljubljana: Institute of Mathematics, Physics and Mechanics
  5. Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), "A census of semisymmetric cubic graphs on up to 768 vertices", Journal of Algebraic Combinatorics, 23 (3): 255–294, doi:10.1007/s10801-006-7397-3.

Bibliography

  • Iofinova, M. E. and Ivanov, A. A. Bi-Primitive Cubic Graphs. In Investigations in the Algebraic Theory of Combinatorial Objects. pp. 123–134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137–152, 1985.)
  • Ivanov, A. A. Computation of Lengths of Orbits of a Subgroup in a Transitive Permutation Group. In Methods for Complex System Studies. Moscow: VNIISI, pp. 3–7, 1983.
  • Ivanov, A. V. On Edge But Not Vertex Transitive Regular Graphs. In Combinatorial Design Theory (Ed. C. J. Colbourn and R. Mathon). Amsterdam, Netherlands: North-Holland, pp. 273–285, 1987.
Categories: