Iofinova-Ivanov Graphs

Iofinova and Ivanov (1985) showed that there exist exactly five bipartite cubic semisymmetric graphs whose automorphism groups preserves the bipartite parts and acts primitively on each part. These graphs have 110, 126, 182, 506, and 990 vertices, and their automorphism groups are PGL_2(11), G_2(2), PGL_2(13), PSL_2(23), and Aut(M_(12)), respectively, where M_(12) is one of the Mathieu groups.


The smallest Iofinova-Ivanov graph is the graph on 110 vertices illustrated above in two embeddings which is the second smallest cubic semisymmetric graph (Iofinova and Ivanov 2002, Marušič et al. 2005). It was constructed in Ivanov (1983) in terms of the Paley design P(11).


The 110-vertex Iofinova-Ivanov graph is illustrated above in three LCF notations of degree 11 and four of degree 5.

The 126-vertex graph is the Tutte 12-cage.

The graphs on 182 and 506 vertices can be described in terms of the projective line over GF(q) for q=13 and 23, respectively (Iofinova and Ivanov 2002).

The 990-vertex graph was described by Chuvaeva (1983), Faradžev et al., and Ronan and Stroth (1984) in terms of the Steiner system S(5,6,12).

See also

Cubic Semisymmetric Graph, Gray Graph, Ivanov-Ivanov-Faradjev Graph, Ljubljana Graph, Semisymmetric Graph, Truncated Witt Graph, Tutte 12-Cage

Explore with Wolfram|Alpha


Biggs, N. L. Algebraic Graph Theory. Cambridge, England: Cambridge University Press, p. 164, 1974.Chuvaeva, I. V. "On Some Combinatoria Objects which Admit the Mathieu Group M_(12)." In Methods for Complex System Studies. Moscow: VNIISI, pp. 47-52, 1983.Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. "The Ljubljana Graph." 2002.žev, I. A.; Klin, M. H.; and Muzichuk, M. E. "Cellular Rings and Groups of Automorphisms of Graphs."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.Marušič, D.; Pisanski, T.; and Wilson, S. "The Genus of the Gray Graph is 7." Europ. J. Combin. 26, 377-385, 2005.Ronan, M. A. and Stroth, G. "Minimal Parabolic Geometries of the Sporadic Groups." Europ. J. Combin. 5, 59-91, 1984.Wong, W. "Determination of a Class of Primitive Permutation Groups." Math. Z. 99, 235-246, 1967.

Referenced on Wolfram|Alpha

Iofinova-Ivanov Graphs

Cite this as:

Weisstein, Eric W. "Iofinova-Ivanov Graphs." From MathWorld--A Wolfram Web Resource.

Subject classifications