Graphical Frobenius representations. (English) Zbl 1404.05077
Summary: A Frobenius group is a transitive permutation group that is not regular and such that only the identity fixes more than one point. A graphical Frobenius representation (GFR) of a Frobenius group \(G\) is a graph whose automorphism group, as a group of permutations of the vertex set, is isomorphic to \(G\). The problem of classifying which Frobenius groups admit a GFR is a natural extension of the classification of groups that have a graphical regular representation (GRR), which occupied many authors from 1958 through 1982. In this paper, we review for graph theorists some standard and deep results about finite Frobenius groups, determine classes of finite Frobenius groups and individual groups that do and do not admit GFRs, and classify those Frobenius groups of order at most 300 having a GFR. Because a Frobenius group, as opposed to a regular permutation group, has a highly restricted structure, the GFR problem emerges as algebraically more complex than the GRR problem. This paper concludes with some further questions and a strong conjecture.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 20B27 | Infinite automorphism groups |
Software:
MagmaReferences:
| [1] | Babai, L., Finite digraphs with given regular automorphism groups, Per. Math. Hungar., 11, 257-270, (1980) · Zbl 0452.05030 · doi:10.1007/BF02107568 |
| [2] | Babai, L.; Godsil, CD, On the automorphism groups of almost all Cayley graphs, Eur. J. Combin., 3, 9-15, (1982) · Zbl 0483.05033 · doi:10.1016/S0195-6698(82)80003-6 |
| [3] | Bhoumik, S.; Dobson, E.; Morris, J., On the automorphism groups of almost all circulant graphs and digraphs, Ars Math. Contemp., 7, 487-506, (2014) · Zbl 1323.05063 · doi:10.26493/1855-3974.315.868 |
| [4] | Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system I: the user language, J. Symb. Comput., 24, 235-265, (1997) · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125 |
| [5] | Collins, MJ, Some infinite Frobenius groups, J. Algebra, 131, 161-165, (1990) · Zbl 0744.20003 · doi:10.1016/0021-8693(90)90170-S |
| [6] | Conder., M.D.E., Spiga, P., Tucker, T.W.: Exceptions for the GFR Problem (in progress) |
| [7] | Dixon, J.D., Mortimer, B.: Permutation Groups. Springer, New York (1996) · Zbl 0951.20001 · doi:10.1007/978-1-4612-0731-3 |
| [8] | Dobson, E., Asymptotic automorphism groups of Cayley digraphs and graphs of abelian groups of prime-power order, Ars Math. Contemp., 3, 200-213, (2010) · Zbl 1213.05122 · doi:10.26493/1855-3974.120.c55 |
| [9] | Dobson, E.; Spiga, P.; Verret, G., Cayley graphs on Abelian groups, Combinatorica, 36, 371-393, (2016) · Zbl 1399.05100 · doi:10.1007/s00493-015-3136-5 |
| [10] | Doyle, J.K.: Graphical Frobenius Representations of Abstract Groups, Ph.D. thesis, Syracuse University (1976) |
| [11] | Frobenius, F.G.: Über auflösbare Gruppen IV, Berliner Sitz. pp. 1216-1230 (1901) · JFM 32.0137.01 |
| [12] | Godsil, CD, GRRs for nonsolvable groups, Colloq. Math. Soc. János Bolyai, 25, 221-239, (1981) · Zbl 0476.05041 |
| [13] | Godsil, CD, On the full automorphism group of a graph, Combinatorica, 1, 243-256, (1981) · Zbl 0489.05028 · doi:10.1007/BF02579330 |
| [14] | Hetzel, D.: Über reguläre graphische Darstellung von auflösbaren Gruppen, Diplomarbeit Fachbereich Mathematik, Technische Universität Berlin (1977) |
| [15] | Imrich, W.: Graphs with transitive Abelian automorphism groups. In: Combinatorial Theory and Its Applications, Colloq. Math. Soc. János Bolyai 4, pp. 651-656. Balatonfűred, Hungary (1969) · Zbl 0206.26202 |
| [16] | Imrich, W.: Graphical Regular Representations of Groups of Odd Order, Colloq. Math. Soc. János Bolyai 18, Combinatorics, Keszthely, Hungary, pp. 611-621 (1976) · Zbl 0413.05017 |
| [17] | Imrich, W.; Izbicki, H., Associative products of graphs, Monatsh. Math., 80, 277-281, (1975) · Zbl 0328.05136 · doi:10.1007/BF01472575 |
| [18] | Imrich, W., Klavz̆ar, S.: Product Graphs. Structure and Recognition, Wiley, New York (2000) · Zbl 0963.05002 |
| [19] | Imrich, W.; Watkins, ME, On graphical regular representations of cyclic extensions of groups, Pac. J. Math., 54, 1-17, (1974) · Zbl 0272.42016 · doi:10.2140/pjm.1974.54.1 |
| [20] | Imrich, W.; Watkins, ME, On automorphism groups of Cayley graphs, Per. Math. Hungar., 7, 243-258, (1976) · Zbl 0335.05118 · doi:10.1007/BF02017943 |
| [21] | Kovács, I., Classifying arc-transitive circulants, J. Algebr. Combin., 20, 353-358, (2004) · Zbl 1057.05040 · doi:10.1023/B:JACO.0000048519.27295.3b |
| [22] | Li, CH, Permutation groups with a cyclic regular subgroup and arc transitive circulants, J. Algebr. Combin., 21, 131-136, (2005) · Zbl 1102.20002 · doi:10.1007/s10801-005-6903-3 |
| [23] | Morris, J.; Spiga, P., Every finite non-solvable group admits an oriented regular representation, J. Combin. Theory Ser. B, 126, 198-234, (2017) · Zbl 1368.05161 · doi:10.1016/j.jctb.2017.05.003 |
| [24] | Morris, J.; Spiga, P.; Verret, G., Automorphisms of Cayley graphs on generalised dicyclic groups, Eur. J. Combin., 43, 68-81, (2015) · Zbl 1301.05173 · doi:10.1016/j.ejc.2014.07.003 |
| [25] | Morris, J., Tymburski, J.: Most rigid representations and Cayley index. Ars Math. Contemp. (to appear) · Zbl 1420.05077 |
| [26] | Nowitz, LA; Watkins, ME, Graphical regular representations of non-abelian groups I, II, Canad. J. Math., 24, 1009-1018, (1972) · Zbl 0249.05123 · doi:10.4153/CJM-1972-102-3 |
| [27] | Passman, D.S.: Permutation Groups. Benjamin, New York (1968) · Zbl 0179.04405 |
| [28] | Sabidussi, G., On a class of fixed-point free graphs, Proc. Am. Math. Soc., 9, 800-804, (1958) · Zbl 0091.37701 · doi:10.1090/S0002-9939-1958-0097068-7 |
| [29] | Sabidussi, G., Vertex-transitive graphs, Monatsh. Math., 68, 426-438, (1964) · Zbl 0136.44608 · doi:10.1007/BF01304186 |
| [30] | Scott, W.R.: Group Theory. Prentice-Hall, Englewood Cliffs (1964) · Zbl 0126.04504 |
| [31] | Thompson, JG, Finite groups with fixed-point-free automorphisms of prime order, Proc. Nat. Acad. Sci. USA, 45, 578-581, (1959) · Zbl 0086.25101 · doi:10.1073/pnas.45.4.578 |
| [32] | Watkins, ME, On the action of non-Abelian groups on graphs, J. Combin. Theory, 11, 95-104, (1971) · Zbl 0227.05108 · doi:10.1016/0095-8956(71)90019-0 |
| [33] | Watkins, M.E.: On Graphical regular representations of \(C_n\times Q\). Graph Theory and Its Applications. Conference at Western Michigan University, pp. 305-311. Springer, Berlin (1972) · Zbl 0249.05124 |
| [34] | Watkins, ME, Graphical regular representations of alternating, symmetric, and miscellaneous small groups, Aequat. Math., 11, 1-17, (1974) · Zbl 0294.05114 · doi:10.1007/BF01837731 |
| [35] | Watkins, M.E.: The state of the GRR problem. In: Fiedler, M. (ed.) Recent Advances in Graph Theory, Proceedings of the Second Czechoslovak Conference on Graph Theory, pp. 517-522. Prague (1974) · Zbl 0333.05109 |
| [36] | Watkins, ME, Graphical regular representations of free products of groups, J. Combin. Theory Ser. B, 21, 47-66, (1976) · Zbl 0319.05114 · doi:10.1016/0095-8956(76)90026-5 |
| [37] | Watkins, M.E.: Infinite Graphical Frobenius Representations (submitted) · Zbl 1398.05147 |
| [38] | Xu, MY, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math., 182, 309-319, (1998) · Zbl 0887.05025 · doi:10.1016/S0012-365X(97)00152-0 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
