Prime-valent symmetric graphs with a quasi-semiregular automorphism. (English) Zbl 1505.05068
Summary: An automorphism of a graph is called quasi-semiregular if it fixes a unique vertex of the graph and its remaining cycles have the same length. This kind of symmetry of graphs was first investigated by K. Kutnar et al. [J. Korean Math. Soc. 50, No. 6, 1199–1211 (2013; Zbl 1278.05250)], as a generalization of the well-known problem regarding existence of semiregular automorphisms in vertex-transitive graphs. Symmetric graphs of valency three or four, admitting a quasi-semiregular automorphism, have been classified in recent two papers (Y.-Q. Feng et al. [Appl. Math. Comput. 353, 329–337 (2019; Zbl 1428.20006)] and F.-G. Yin and Y.-Q. Feng [ibid. 399, Article ID 126014, 6 p. (2021; Zbl 1508.05078)]).
Let \(\Gamma\) be a connected symmetric graph of prime valency \(p \geq 5\) admitting a quasi-semiregular automorphism. In this paper, it is proved that either \(\Gamma\) is a connected Cayley graph \(\mathrm{Cay}(M, S)\) such that \(M\) is a 2-group admitting a fixed-point-free automorphism of order \(p\) with \(S\) as an orbit of involutions, or \(\Gamma\) is a normal \(N\)-cover of a \(T\)-arc-transitive graph of valency \(p\) admitting a quasi-semiregular automorphism, where \(T\) is a non-abelian simple group and \(N\) is a nilpotent group. Further, for \(p = 5\) a complete classification of graphs \(\Gamma\) such that either \(\mathrm{Aut}(\Gamma)\) has a solvable arc-transitive subgroup or \(\Gamma\) is \(T\)-arc-transitive with \(T\) a non-abelian simple group is given. Finally, a construction of an infinite family of symmetric graphs admitting a quasi-semiregular automorphism and having nonsolvable automorphism group is given.
Let \(\Gamma\) be a connected symmetric graph of prime valency \(p \geq 5\) admitting a quasi-semiregular automorphism. In this paper, it is proved that either \(\Gamma\) is a connected Cayley graph \(\mathrm{Cay}(M, S)\) such that \(M\) is a 2-group admitting a fixed-point-free automorphism of order \(p\) with \(S\) as an orbit of involutions, or \(\Gamma\) is a normal \(N\)-cover of a \(T\)-arc-transitive graph of valency \(p\) admitting a quasi-semiregular automorphism, where \(T\) is a non-abelian simple group and \(N\) is a nilpotent group. Further, for \(p = 5\) a complete classification of graphs \(\Gamma\) such that either \(\mathrm{Aut}(\Gamma)\) has a solvable arc-transitive subgroup or \(\Gamma\) is \(T\)-arc-transitive with \(T\) a non-abelian simple group is given. Finally, a construction of an infinite family of symmetric graphs admitting a quasi-semiregular automorphism and having nonsolvable automorphism group is given.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 20B25 | Finite automorphism groups of algebraic, geometric, or combinatorial structures |
| 05E18 | Group actions on combinatorial structures |
Software:
MagmaReferences:
| [1] | Bosma, W.; Cannon, J.; Playoust, C., The MAGMA algebra system I: the user language, J. Symb. Comput., 24, 235-265 (1997) · Zbl 0898.68039 |
| [2] | Biggs, N., Three remarkable graphs, Can. J. Math., 25, 397-411 (1973) · Zbl 0256.05114 |
| [3] | Biggs, N., Algebraic Graph Theory, Cambridge Mathematical Library, vol. 67 (1993), Cambridge University Press: Cambridge University Press New York |
| [4] | Burness, T. C.; Giudici, M., Classical Groups, Derangements and Primes, Australian Mathematical Society Lecture Series, vol. 25 (2016), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1372.11001 |
| [5] | Cameron, P.; Sheehan, J.; Spiga, P., Semiregular automorphisms of vertex-transitive cubic graphs, Eur. J. Comb., 27, 924-930 (2006) · Zbl 1090.05032 |
| [6] | Conway, J. H.; Curtis, R. T.; Norton, S. P.; Parker, R. A.; Wilson, R. A., Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups (1985), Oxford University Press: Oxford University Press New York · Zbl 0568.20001 |
| [7] | Dixon, J. D.; Mortimer, B., Permutation Groups, Graduate Texts in Mathematics, vol. 163 (1996), Springer New York: Springer New York New York · Zbl 0951.20001 |
| [8] | Dobson, E.; Malnič, A.; Marušič, D.; Nowitz, L. A., Semiregular automorphisms of vertex-transitive graphs of certain valencies, J. Comb. Theory, Ser. B, 97, 371-380 (2007) · Zbl 1113.05046 |
| [9] | Doyle, J. K.; Tucker, T. W.; Watkins, M. E., Graphical Frobenius representations, J. Algebraic Comb., 48, 405-428 (2018) · Zbl 1404.05077 |
| [10] | Du, J.-L.; Feng, Y.-Q., Tetravalent 2-arc-transitive Cayley graphs on non-abelian simple groups, Commun. Algebra, 47, 4565-4574 (2019) · Zbl 1418.05073 |
| [11] | Feng, Y.-Q.; Hujdurović, A.; Kovács, I.; Kutnar, K.; Marušič, D., Quasi-semiregular automorphisms of cubic and tetravalent arc-transitive graphs, Appl. Math. Comput., 353, 329-337 (2019) · Zbl 1428.20006 |
| [12] | Giudici, M.; Potočnik, P.; Verret, G., Semiregular automorphisms of edge-transitive graphs, J. Algebraic Comb., 40, 961-972 (2014) · Zbl 1304.05059 |
| [13] | Giudici, M.; Verret, G., Arc-transitive graphs of valency twice a prime admit a semiregular automorphism, Ars Math. Contemp., 18, 179-186 (2020) · Zbl 1486.05127 |
| [14] | Giudici, M.; Xu, J., All vertex-transitive locally-quasiprimitive graphs have a semiregular automorphism, J. Algebraic Comb., 25, 217-232 (2007) · Zbl 1112.05050 |
| [15] | Godsil, C. D., On the full automorphism group of a graph, Combinatorica, 1, 243-256 (1981) · Zbl 0489.05028 |
| [16] | Gorenstein, D., Finite Groups (1980), Chelsea Publishing Co.: Chelsea Publishing Co. New York · Zbl 0202.02402 |
| [17] | Gorenstein, D.; Lyons, R.; Solomon, R., The Classification of the Finite Simple Groups, Number 3, Mathematical Surveys and Monographs, vol. 40.3 (1998), American Mathematical Society: American Mathematical Society Providence, Rhode Island · Zbl 0890.20012 |
| [18] | Guo, S.-T.; Feng, Y.-Q., A note on pentavalent s-transitive graphs, Discrete Math., 312, 2214-2216 (2012) · Zbl 1246.05105 |
| [19] | Higman, G., Groups and rings having automorphisms without non-trivial fixed elements, J. Lond. Math. Soc., 32, 321-334 (1957) · Zbl 0079.03203 |
| [20] | Hujdurović, A., Quasi m-Cayley circulants, Ars Math. Contemp., 6, 147-154 (2013) · Zbl 1301.05171 |
| [21] | Huppert, B., Endliche Gruppen I, Die Grundlehren der Mathematischen Wissenschaften, Band 134 (1967), Springer Berlin: Springer Berlin Heidelberg, (in German) · Zbl 0217.07201 |
| [22] | Huppert, B.; Blackburn, N., Finite Groups III, Grundlehren der Mathematischen Wissenschaften, vol. 243 (1982), Springer Berlin: Springer Berlin Heidelberg · Zbl 0514.20002 |
| [23] | Kleidman, P. B.; Liebeck, M. W., The Subgroup Structure of the Finite Classical Groups, London Mathematical Society Lecture Note Series, vol. 129 (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0697.20004 |
| [24] | Korchmáros, G.; Nagy, G. P., Graphical Frobenius representations of non-abelian groups, Ars Math. Contemp., 20 (2021) · Zbl 1542.20015 |
| [25] | Kutnar, K.; Malnič, A.; Martínez, L.; Marušič, D., Quasi m-Cayley strongly regular graphs, J. Korean Math. Soc., 50, 1199-1211 (2013) · Zbl 1278.05250 |
| [26] | Kutnar, K.; Šparl, P., Distance-transitive graphs admit semiregular automorphisms, Eur. J. Comb., 31, 25-28 (2010) · Zbl 1208.05049 |
| [27] | Li, C. H., Semiregular automorphisms of cubic vertex transitive graphs, Proc. Am. Math. Soc., 136, 1905-1910 (2008) · Zbl 1157.05028 |
| [28] | Lorimer, P., Vertex-transitive graphs: symmetric graphs of prime valency, J. Graph Theory, 8, 55-68 (1984) · Zbl 0535.05031 |
| [29] | Marušič, D., On vertex symmetric digraphs, Discrete Math., 36, 69-81 (1981) · Zbl 0459.05041 |
| [30] | Marušič, D., Semiregular automorphisms in vertex-transitive graphs of order \(3 p^2\), Electron. J. Comb., 25, 2-25 (2018) · Zbl 1458.20003 |
| [31] | Marušič, D., Semiregular automorphisms in vertex-transitive graphs with a solvable group of automorphisms, Ars Math. Contemp., 13, 461-468 (2017) · Zbl 1381.20005 |
| [32] | Marušič, D.; Scapellato, R., Permutation groups, vertex-transitive digraphs and semiregular automorphism, Eur. J. Comb., 19, 707-712 (1998) · Zbl 0912.05038 |
| [33] | Morris, J.; Spiga, P.; Verret, G., Semiregular automorphisms of cubic vertex-transitive graphs and the abelian normal quotient method, Electron. J. Comb., 22, 1-12 (2015) · Zbl 1335.05237 |
| [34] | Ronan, M. A., Semiregular graph automorphisms and generalized quadrangles, J. Comb. Theory, Ser. A, 29, 319-328 (1980) · Zbl 0453.05016 |
| [35] | Sabidussi, B. O., Vertex-transitive graphs, Monatshefte Math., 68, 426-438 (1964) · Zbl 0136.44608 |
| [36] | Spiga, P., On the existence of Frobenius digraphical representations, Electron. J. Comb., 25, Article #P2.6 pp. (2018) · Zbl 1390.05095 |
| [37] | Spiga, P., On the existence of graphical Frobenius representations and their asymptotic enumeration, J. Comb. Theory, Ser. B, 142, 210-243 (2020) · Zbl 1437.05100 |
| [38] | Suzuki, M., On a class of doubly transitive groups, Ann. Math. (2), 75, 105-145 (1964) · Zbl 0106.24702 |
| [39] | Thompson, J. G., Finite groups with fixed-point-free automorphisms of prime order, Proc. Natl. Acad. Sci. USA, 45, 578-581 (1959) · Zbl 0086.25101 |
| [40] | Verret, G., Arc-transitive graphs of valency 8 have a semiregular automorphism, Ars Math. Contemp., 8, 29-34 (2015) · Zbl 1318.05090 |
| [41] | Xu, J., Semiregular automorphisms of arc-transitive graphs with valency pq, Eur. J. Comb., 29, 622-629 (2008) · Zbl 1142.05044 |
| [42] | Yin, F.-G.; Feng, Y.-Q., Symmetric graphs of valency 4 having a quasi-semiregular automorphism, Appl. Math. Comput., 399, Article 126014 pp. (2021) · Zbl 1508.05078 |
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.
