Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
graph; automorphism group
graph; automorphism group
Summary:
The problem of finding minimal vertex number of graphs with a given automorphism group is addressed in this article for the case of cyclic groups. This problem was considered earlier by other authors. We give a construction of an undirected graph having $4n+6$ vertices and automorphism group cyclic of order $4n$, $n\ge 1$. As a special case we get graphs with $2^k+6$ vertices and cyclic automorphism groups of order $2^k$. It can revive interest in related problems.
References:
[1] Arlinghaus, W.C.: The classification of minimal graphs with given abelian automorphism group. Mem. Amer. Math. Soc. 57 (1985), no. 330, viii+86 pp. MR 0803975 | Zbl 0568.05031
[2] Babai, L.: On the minimum order of graphs with given group. Canad. Math. Bull. 17 (1974), 467–470. DOI 10.4153/CMB-1974-082-9 | MR 0406855 | Zbl 0311.05120
[3] Babai, L.: In Graham R.L.; Grotschel M.; Lovasz L., Handbook of Combinatorics I. n Graham R.L.; Grotschel M.; Lovasz L., Handbook of Combinatorics I, ch. Automorphism groups, isomorphism, reconstruction, pp. 1447–1540, North-Holland, 1995. MR 1373683
[4] Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput. 24 (1997), 235–265. DOI 10.1006/jsco.1996.0125 | MR 1484478 | Zbl 0898.68039
[5] Bouwer, I.Z., Frucht, R.: In Jagdish N. Srivastava, A survey of combinatorial the. Jagdish N. Srivastava, A survey of combinatorial the, ch. Line-minimal graphs with cyclic group, pp. 53–69, North-Holland, 1973.
[6] Daugulis, P.: $10$-vertex graphs with cyclic automorphism group of order $4$. 2014, http://arxiv.org/abs/1410.1163
[7] Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Heidelberg, 2010. Zbl 1209.00049
[8] Frucht, R.: Herstellung von Graphen mit vorgegebener abstrakter Gruppe. Compositio Math. (in German) 6 (1939), 239–250. MR 1557026
[9] Harary, F.: Graph Theory. Addison-Wesley, Reading, MA, 1969. MR 0256911 | Zbl 0196.27202
[10] McKay, B.D., Piperno, A.: Practical Graph Isomorphism, II. J. Symbolic Comput. 60 (2013), 94–112. DOI 10.1016/j.jsc.2013.09.003 | MR 3131381
[11] Sabidussi, G.: On the minimum order of graphs with given automorphism group. Monatsh. Math. 63 (2) (1959), 124–127. DOI 10.1007/BF01299094 | MR 0104596 | Zbl 0085.37901
Search
Partner of
