×

zbMATH — the first resource for mathematics

A census of semisymmetric cubic graphs on up to 768 vertices. (English) Zbl 1089.05032
Summary: A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to \(768\). This list was determined by the authors using Goldschmidt’s classification of finite primitive amalgams of index \((3,3)\), and a computer algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms, its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of the list are identified with these. The special case of those graphs having \(K_{1,3}\) as a normal quotient is investigated in detail.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
Software:
Magma
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bosma, W.; Cannon, C.; Playoust, C., The Magma algebra system I: The user language, J. Symbolic Comput., 24, 235-265, (1997) · Zbl 0898.68039
[2] Bouwer, I. Z., An edge but not vertex transitive cubic graph, Bull. Can. Math. Soc., 11, 533-535, (1968) · Zbl 0182.58102
[3] Bouwer, I. Z., On edge but not vertex transitive regular graphs, J. Combin. Theory, B, 12, 32-40, (1972) · Zbl 0228.05114
[4] I.Z. Bouwer (ed.), The Foster Census, Charles Babbage Research Centre, Winnipeg, 1988. · Zbl 0639.05043
[5] Conder, M. D.E.; Lorimer, P., Automorphism Groups of Symmetric Graphs of Valency 3, J. Combin. Theory, Series B, 47, 60-72, (1989) · Zbl 0682.05036
[6] M.D.E. Conder, P. Dobcsányi, B. Mc Kay and G. Royle, The Extended Foster Census, http://www.cs.uwa.edu.au/gordon/remote/foster.
[7] Conder, M. D.E.; Dobcsányi, P., Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput., 40, 41-63, (2002) · Zbl 0996.05069
[8] Conder, M. D.E.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P., The edge-transitive but not vertex-transitive cubic graph on 112 vertices, J. Graph Theory, 50, 25-42, (2005) · Zbl 1069.05039
[9] J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson, Atlas of finite groups, Oxford University Press, Eynsham, 1985. · Zbl 0568.20001
[10] J.D. Dixon and B. Mortimer, Permutation Groups, Springer-Verlag, New York, 1996. · Zbl 0951.20001
[11] Djoković, D.Ž.; Miller, G. L., Regular groups of automorphisms of cubic graphs, J. Combin. Theory. B, 29, 195-230, (1980) · Zbl 0385.05040
[12] P. Dobcsányi, Home Page, http://www.scitec.auckland.ac.nz/peter.
[13] Du, S. F.; Marušič, D., Biprimitive graphs of smallest order, J. Algebraic Combin., 9, 151-156, (1999) · Zbl 0937.05049
[14] S.F. Du and M.Y. Xu, “A classification of semisymmetric graphs of order 2pq (I),” Comm. Algebra28 (2000), 2685-2715. J. Combin. Theory, Series B29 (1980), 195-230. · Zbl 0944.05051
[15] Folkman, J., Regular line-symmetric graphs, J. Combin. Theory, 3, 215-232, (1967) · Zbl 0158.42501
[16] Frucht, R., A canonical representation of trivalent Hamiltonian graphs, J. Graph Theory, 1, 45-60, (1977) · Zbl 0358.05029
[17] M. Giudici, C.H. Li and C.E. Praeger, “Characterising finite locally s-arc transitive graphs with a star normal quotient,” preprint. · Zbl 1113.05047
[18] Godsil, C., On the full automorphism group of Cayley graphs, Combinatorica, 1, 143-156, (1981)
[19] C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer-Verlag, New York, 2001. · Zbl 0968.05002
[20] Goldschmidt, D., Automorphisms of trivalent graphs, Ann. Math., 111, 377-406, (1980) · Zbl 0475.05043
[21] D. Gorenstein, Finite Groups, Harper and Row, New York, 1968. · Zbl 0185.05701
[22] D. Gorenstein, Finite Simple Groups: An Introduction To Their Classification, Plenum Press, New York, 1982. · Zbl 0483.20008
[23] J.L. Gross and T.W. Tucker, Topological Graph Theory, Wiley-Interscience, New York, 1987. · Zbl 0621.05013
[24] M.E. Iofinova and A.A. Ivanov, Biprimitive cubic graphs, Investigations in Algebraic Theory of Combinatorial Objects (Proceedings of the seminar, Institute for System Studies, Moscow, 1985) Kluwer Academic Publishers, London, 1994, pp 459-472.
[25] Ivanov, A. V., On edge but not vertex transitive regular graphs, Ann. Discrete Math., 34, 273-286, (1987) · Zbl 0629.05040
[26] M.H. Klin, “On edge but not vertex transitive graphs,” Coll. Math. Soc. J. Bolyai, (25. Algebraic Methods in Graph Theory, Szeged, 1978), Budapest, 1981, 399-403.
[27] Lazebnik, F.; Viglione, R., An infinite series of regular edge- but not vertex-transitive graphs, J. Graph Theory, 41, 249-258, (2002) · Zbl 1012.05083
[28] Lipschutz, S.; Xu, M. Y., Note on infinite families of trivalent semisymmetric graphs, European J. Combin., 23, 707-711, (2002) · Zbl 1014.05032
[29] Malnič, A.; Marušič, D.; Potočnik, P., On cubic graphs admitting an edge-transitive solvable group, J. Algebraic Combinatorics, 20, 99-113, (2004) · Zbl 1054.05055
[30] Malnič, A.; Marušič, D.; Potočnik, P.; Wang, C. Q., An infinite family of cubic edge- but not vertex-transitive graphs, Discrete Mathematics, 280, 133-148, (2004) · Zbl 1041.05039
[31] Malnič, A.; Marušič, D.; Potočnik, P., Elementary abelian covers of graphs, J. Algebraic Combinatorics, 20, 71-97, (2004) · Zbl 1065.05050
[32] Malnič, A.; Nedela, R.; Skoviera, M., Lifting graph automorphisms by voltage assignments, European J. Combin., 21, 927-947, (2000) · Zbl 0966.05042
[33] Marušič, D., Constructing cubic edge- but not vertex-transitive graphs, J. Graph Theory, 35, 152-160, (2000) · Zbl 1021.05050
[34] Marušič, D.; Pisanski, T., The Gray graph revisited, J. Graph Theory, 35, 1-7, (2000) · Zbl 1021.05049
[35] Marušič, D.; Potočnik, P., Semisymmetry of generalized Folkman graphs, European J. Combin., 22, 333-349, (2001) · Zbl 0979.05056
[36] Skoviera, M., A contribution to the theory of voltage graphs, Discrete Math., 61, 281-292, (1986) · Zbl 0594.05029
[37] Tutte, W. T., A family of cubical graphs, Proc. Cambridge Phil. Soc., 43, 459-474, (1948) · Zbl 0029.42401
[38] H. Wielandt, Finite Permutation Groups, Academic Press, New York-London, 1964. · Zbl 0138.02501
[39] Wilson, S. E., A worthy family of semisymmetric graphs, DiscreteMath., 271, 283-294, (2003) · Zbl 1021.05048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.