ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 461-468
Semiregular automorphisms in vertex-transitive graphs with a solvable group of automorphisms
Dragan Marušič *
University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia University of Primorska, UP FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia IMFM, Jadranska 19, 1000 Ljubljana, Slovenia
Received 15 September 2017, accepted 26 September 2017, published online 29 September 2017
It has been conjectured that automorphism groups of vertex-transitive (di)graphs, and more generally 2-closures of transitive permutation groups, must necessarily possess a fixed-point-free element of prime order, and thus a non-identity element with all orbits of the same length, in other words, a semiregular element. The known affirmative answers for graphs with primitive and quasiprimitive groups of automorphisms suggest that solvable groups need to be considered if one is to hope for a complete solution of this conjecture. It is the purpose of this paper to present an overview of known results and suggest possible further lines of research towards a complete solution of the problem.
Keywords: Solvable group, semiregular automorphism, fixed-point-free automorphism, polycirculant conjecture.
Math. Subj. Class.: 20B25, 05C25
1 Introduction
It is known that each finite transitive permutation group contains a fixed-point-free element of prime power order (see [8, Theorem 1]), but not necessarily a fixed-point-free element of prime order (which is equivalent to existence of a semiregular element) [2, 8]. In 1981 it was asked if every vertex-transitive digraph admits a semiregular automorphism (see [18, Problem 2.4]). The existence of such automorphisms plays an important role in solutions to many important open problems in algebraic graph theory, such as, for example, in the classifications of graphs satisfying certain prescribed symmetry conditions (see [15, 16,
*This work is supported in part by the Slovenian Research Agency (I0-0035, research program P1-0285 and research projects N1-0032, N1-0038, N1-0062, J1-5433, and J1-6720), and in part by H2020 Teaming InnoRenew CoE.
E-mail address: dragan.marusic@upr.si (Dragan Marusic)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
461
Ars Math. Contemp. 13 (2017) 275-291
20, 22, 25]). Semiregular automorphisms have also proved useful in the long standing hamiltonicity problem for connected vertex-transitive graphs and in a recently explored dichotomy of even/odd automorphisms (see [1, 13, 17]).
In 1997 Klin generalized the semiregularity problem conjecturing that every transitive 2-closed permutation group contains a semiregular element (see [4]) - the term polycir-culant conjecture is sometimes used for the semiregularity problem in this wider context. (Recall that for a finite permutation group G on a set V the 2-closure of G is the largest subgroup of the symmetric group Sym( V) containing G and having the same orbits as G in the induced action on V x V.) Both terms will be used throughout the paper, this should cause no confusion. The problem has spurred a lot of interest in the mathematical community producing several partial results - addressing graphs with valency and/or order restrictions - with varying degrees of difficulties involved in their proofs (see for instance [2, 3, 5, 6, 7, 8, 9, 10, 12, 14, 19, 21, 23, 24]). Recently, Giudici, Potocnik and Verret [11] considered the problem in the context of graphs whose automorphism group acts transitivity on edges and not necessarily on vertices. They proved that every regular edge-transitive graph of valency three or four has a semiregular automorphism. Also, in 2003 Giudici [9] proved the polycirculant conjecture for quasiprimitive groups, and in 2007 Giudici and Xu [12] proved it for biquasiprimitive groups.
Since the automorphism group of a vertex-transitive graph is a transitive 2-closed group these results imply that the only graphs for which the semiregularity problem has not yet been settled are graphs whose automorphism groups contain a non-identity normal subgroup with at least three orbits. Clearly, since disconnected vertex-transitive graphs must contain semiregular automorphisms, we can restrict ourselves to connected graphs.
It is usually the case that algebraic graph theory problems dealing with group actions on graphs are considerably harder to address for nonsolvable groups than for the solvable ones. Such is the case, for example, with various types of classification problems for arc-transitive graphs and vertex-transitive graphs in general. Counter-intuitively, this does not seem to be the case with the polycirculant conjecture. While, as already mentioned it has been proved that the polycirculant conjecture holds for quasiprimitive groups [9], nothing of that nature is known for groups at the opposite end of the spectrum. For example, solvable groups turned out to be the steepest hill to climb in the completion of the proof that groups of square-free degree satisfy the polycirculant conjecture, see [5].
Our aim is to discuss possible ways of approaching the semiregularity problem for solvable groups, trying to single out certain idiosyncrasies of this class of groups relevant to the problem.
Problem 1.1. Does the 2-closure G(2) of a solvable group G contain a semiregular element?
In Proposition 2.3 a partial solution to this problem is given for groups of degree mp2, where m < p is square-free. As a consequence a partial solution to existence of semiregular automorphism in vertex-transitive graphs of order p2q, where p and q are primes, is shown (see Theorem 2.4 and Corollary 2.5). Since disconnected vertex-transitive graphs clearly contain semiregular automorphisms, the graphs considered in Section 2 are connected.
2 Searching for semiregular elements
First let us recall the definition of a pseudometric first defined in [5] where it was used as one of the tools in proving the existence of semiregular elements in transitive permutation
D. Marusic: Semiregular automorphisms in vertex-transitive graphs with a solvable
463
groups of square-free degree.
Let G be a transitive permutation group with a complete block system B such that fixG(B) contains a subgroup K = Us, for some s > 1 and such that the restriction KB = Ur, 1 < r < s, acts transitively on B, for each B G B. Then in view of [5, Proposition 3.1] we can define apseudometric on B by letting
DistK (B,B')=log|u||K(BB)|.
(For the proof that DistK is symmetric and that it satisfies the triangle inequality see [5, Proposition 3.1].)
In Proposition 2.1 below the extremal case where the possible distances in this pseudo-metric are only 0 and 1 is considered.
Proposition 2.1. Let p be a prime, let s > 1 be an integer, let U be a simple group and let G be a transitive permutation group on a set V admitting an imprimitivity block system B with blocks of length divisible by p. If fixG(B) contains a subgroup K = Us such that for each block B G B, the restriction
KB
is isomorphic to U, acts transitively on B and contains a semiregular element of order p, then G(2) contains a semiregular element of order p.
Proof. Observe that the assumptions in the statement of the proposition imply that in the above pseudometric language the possible distances between any two blocks in B are either
0	or 1. Namely, since K(is a normal subgroup of KB = U it follows that K(( is either
1	or U .In particular, for B, B' G B, the following holds
DistK(B, B') = 1 ^ K(B) is transitive on B' and K(B/) is transitive on B. (2.1)
This will allow us to construct a semiregular element in G(2) by a succession of superpositions of permutations acting independently on collections of blocks at distance 0. First, if s = 1 then the distance between any two blocks in B is equal to 0, and thus the element of K whose restriction to a block B G B is semiregular on B is semiregular on V too. We may therefore assume that the maximal distance between blocks in B is precisely 1. One can easily see that each of the subsets of those blocks in B being at mutual distance 0 forms a block of G. More precisely,
C = |{Bj0 u ... U Bifc | DistK(Bij, Bit ) = 0 for all j, it G {io,..., ik}} |
i G {0,...,e}},
where e = |B|, is an imprimitivity block system of G. Moreover, in view of (2.1) for every block Ci = Bi0 U... U Bik G C there exists an element Yi G K such that is semiregular
C -
and Yi j =1 for all blocks Cj G C, i = j. Consequently, y0yi • • • Yk is semiregular on V, completing the proof of Proposition 2.1.	□
Corollary 2.2. Let G be a permutation group acting transitively on a set V and let M be a minimal normal subgroup of G having orbits of prime length p on V. Then G(2) contains a semiregular element of order p.
Proof. Since M is a minimal normal subgroup of G it is isomorphic to a direct product of isomorphic simple groups, that is, M = Us, s > 1, where U is a simple group. The orbits
464
Ars Math. Contemp. 13 (2017) 275-291
of M form an imprimitivity block system B consisting of blocks of length p. For B e B the restriction MB is therefore a transitive group of prime degree p, and thus MB = U. Hence Proposition 2.1 applies.	□
Proposition 2.3. Let G be a transitive solvable group of degree mp2, where m < p is square-free. Then G(2) contains a semiregular element of prime order.
Proof. Let M be a minimal normal subgroup of G. Since G is solvable we have M = Zq, where q is a prime and s > 1. The orbits of M give rise to an imprimitivity block system B. If the blocks in B are of prime length then Corollary 2.2 applies. We may therefore assume that B consists of blocks of size p2 and M = Zp, s > 1.
Let B = {B0,..., Bm-1}. Assume that G(2) does not contain semiregular elements, and let a e M be an element of order p with a minimal number of orbits of M on which the restriction of a is the identity. Without loss of generality we may assume that
B. fi; 0 < i < t a i = <
1 = 1; t < i < m - 1
where t < m — 1. Let B e B be a block for which aB = 1. Because of transitivity of G there exists fi e M, a conjugate of a, such that fiB = 1. Since m < p there exists k e Zp such that afik is semiregular and of order p on each of the blocks Bj, t < i < m — 1, as well as on the block B. Therefore, the number of blocks on which the restriction of afik is the identity is at least one less than the number of blocks on which the restriction of a is the identity, contradicting the minimality condition. It follows that G(2) must contain semiregular elements as claimed. (Note that the assumption that m < p was essential in this respect.)	□
With the use of Corollary 2.2 and Proposition 2.3 we can now prove the following result about existence of semiregular automorphisms in vertex-transitive graphs of order qp2, where p and q are primes.
Theorem 2.4. Let X be a connected vertex-transitive graph of order p2q, where p and q are primes, and either q < p or p2 < q. Then either
(i)	X admits a semiregular automorphism, or
(ii)	2 < q < p and Aut(X) is nonsolvable with an intransitive non-abelian minimal normal subgroup whose orbits are either of length p2 or of length pq.
Proof. First, we may assume that p > 3 and q > 2 and that q = p. Namely, if q = 2 or q = p then the order of X equals 2p2 or p3, and the existence of semiregular automorphisms was proved in [19] and [18], respectively. If q > p2 then the existence of semiregular automorphisms follows from results in [18]. Therefore, we may assume that q < p2.
If Aut(X) is primitive or quasiprimitive then, by [9], X contains a semiregular automorphism. We may therefore assume that there exists a minimal normal subgroup M of Aut(X) whose orbits give rise to a non-trivial imprimitivity block system B.
If Aut(X) is solvable then M is abelian and isomorphic to Zji, where r e {q,p} and k > 1. Hence B consists of blocks of length q, p or p2, and Corollary 2.2 and Proposition 2.3 imply the existence of semiregular automorphisms of X. If, however, Aut(X)
D. Marusic: Semiregular automorphisms in vertex-transitive graphs with a solvable
465
is nonsolvable then M is non-abelian. If the orbits of M are of prime length then Corollary 2.2 applies. Otherwise the orbits of M are either of length p2 or qp, completing the proof of Theorem 2.4.	□
The following corollary is an immediate consequence of Theorem 2.4.
Corollary 2.5. Let q and p be primes such that either q < p or p2 < q. A connected vertex-transitive graph of order p2q admitting a transitive solvable group of automorphisms has a semiregular automorphism.
In our search for semiregular group elements we now turn to vertex-transitive graphs admitting a solvable group of automorphisms and satisfying certain valency restrictions. For a graph X admitting a transitive action of a group G with an imprimitivity block system B arising from the orbits of a normal subgroup M < G, we let X/B denote the corresponding quotient graph having vertex set B with two blocks B, B' e B being adjacent if there is an edge in X joining a vertex in B to a vertex in B'. Further, for B, B' e B we let [B, B'] denote the bipartite graph induced by the edges of X joining blocks B and B', and we let val(B, B') denote the valency of [B, B']. Also let val(X) denote the valency of X.
Lemma 2.6. Let X be a connected vertex-transitive graph admitting a transitive action of a solvable group G with a minimal normal subgroup M = and suppose further that val(X) < pq, where p > q is the largest prime dividing |G|. Then either
(i)	G contains a semiregular subgroup or
(ii)	M is intransitive and there exist orbits B, B' of M such that val(B, B') > mq, where mp is the smallest multiple of q exceeding p.
Proof. Assume that (i) does not hold. It follows that M is intransitive for otherwise X would be a Cayley graph of M and so M would act semiregularly on V (X). Let B be the imprimitivity block system arising from the orbits of M, and let Dist = DistM be the associated pseudometric on B. If Dist(B, B') = 0 for every two adjacent blocks B and B' in X/B, then clearly M contains a semiregular element of order q. We may therefore assume that there are adjacent blocks B and B' such that d = Dist(B, B') > 1. Furthermore, we may assume that Gv, for v e V(X), contains elements of order q as well as elements of order p.
Fix a vertex v e B. Since d > 1, we have that val(B, B') is a positive multiple of q, and so is at least q. By assumption, there exists an element 7 e Gv of order p which cyclically permutes at leastp neighbors w0, wi, ... , wp-1 of v, where 7j(w0) = wj, and clearly fixes all other neighbors.
Without loss of generality let w0 e B'. We claim that wj belongs to B' for every i e {0,..., p - 1}. If that was not the case there would be p distinct blocks 7j(B'), with Dist(B, 7j(B')) > 1, i e {0,... ,p - 1}. Consequently, v would have at least q neighbors in each of these p blocks and so the valency of X would be at least pq, which contradicts the assumption. We conclude that each wj e B'. It follows that val(B, B') > p. But val(B, B') is a multiple of q, and hence at least mq.	□
Proposition 2.7. Let p > q be primes and let X be a connected vertex-transitive graph admitting a transitive solvable {p, q} -group G, and let M be a minimal normal elementary abelian subgroup of G. Then one of the following possibilities occurs:
466
Ars Math. Contemp. 13 (2017) 275-291
(i)	G contains a semiregular subgroup, or
(ii)	M = Zk and val(X) > mq, where mq is the smallest multiple of q exceeding p, or
(iii)	M = Zk and val(X) > p.
Proof. Assuming that G does not contain a semiregular subgroup and assuming that M = Zk we have, by Lemma 2.6, that the valency val(X) of X is at least mq. Further if it is exactly mq then the imprimitivity block system B arising from the orbits of M consists of two blocks alone, that is, B = {B, B'} with valency val(B, B') = mq. It follows that X is a bipartite graph (with bipartition {B, B'}). As the blocks of B have order qj for some j it must be that either X has order a power of 2 or p = 2. But q < p which is not possible. Therefore val(X) > mq. Finally, suppose that M = Zp. Then the nonexistence of a semregular subgroup implies that there must exist a pair of adjacent blocks B and B' in X/B such that in the above defined pseudometrc Dist we have Dist(B, B') > 1. This implies that val(X) > p. But if val(X) was equal to p then a semiregular automorphism could be produced in an analogous way to the previous case.	□
3 Conclusions
Special cases for valencies 3 and 4 of Lemma 2.6 and Proposition 2.7 played an important role in the proofs of these results, see [6, 19]. For example, in a cubic vertex-transitive graph an automorphism of prime order greater than 3 is clearly semiregular. In fact, in a vertex-transitive graph an automorphism of order greater than the valency of the graph is necessarily semiregular. Therefore, in order to complete the proof of the existence of semiregular automorphisms in such graphs it suffices to deal with graphs having a group of automorphisms which is a {2,3}-group. Clearly, Proposition 2.7 applies. As for quartic vertex-transitive graphs again assuming that all automorphisms are of order 2 and 3, and hence a group in question is a {2, 3}-group, Proposition 2.7 implies that the minimal normal elementary abelian subgroup M has to be a 3-group, and furthermore that the quotient graph with respect to the imprimitivity block system arising from the orbits of M is a multicycle of even length obtained from a cycle with every second edge replaced by a triple of edges. A delicate analysis of this case is then needed in order to prove the existence of a semiregular automorphism (see [6]).
An obvious possible next goal would be to prove the existence of semiregular automorphisms in quintic vertex-transitive graphs. In 2007 Giudici and Xu [12] proved that all vertex-transitive locally-quasiprimitive graphs have a semiregular automorphism, implying that arc-transitive graphs of prime valency have semiregular automorphisms. This result combined together with the above remark about automorphisms of order greater than the valency of the graph allows us to assume that the group of automorphisms in question is a {2,3}-group. Two cases may occur depending on whether the elementary abelian subgroup is a 2-group or a 3-group. If M = Zk then, using Proposition 2.7, one can prove that the quotient graph with respect to the imprimitivity block system arising from the orbits of M is a multicycle of even length obtained from a cycle with every second edge replaced by a quadruple of edges. It is reasonable to expect that an approach similar to the one used in [5] for the quartic case would result in a construction of semiregular automorphisms. If on the other hand M = Zg, two possibilities needing further analysis may arise from Proposition 2.7. First, the quotient graph is a multicycle of even length obtained from a cycle with every other edge replaced, respectively, by a pair of edges and a triple of edges.
D. Marusic: Semiregular automorphisms in vertex-transitive graphs with a solvable
467
Second, the quotient graph is a vertex-transitive multigraph obtained from a cubic graph
with every edge in a perfect matching replaced by a triple of edges. A complete solution
for quintic vertex-transitive graphs depends heavily on a successful analysis of these three
remaining cases.
References
[1]	B. Alspach, Lifting Hamilton cycles of quotient graphs, Discrete Math. 78 (1989), 25-36, doi: 10.1016/0012-365x(89)90157-x.
[2]	P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Marusic and L. A. Nowitz, Transitive permutation groups without semiregular subgroups, J. London Math. Soc. 66 (2002), 325-333, doi:10.1112/s0024610702003484.
[3]	P. J. Cameron, J. Sheehan and P. Spiga, Semiregular automorphisms of vertex-transitive cubic graphs, European J. Combin. 27 (2006), 924-930, doi:10.1016/j.ejc.2005.04.008.
[4]	P. J. Cameron (ed.), Problems from the Fifteenth British Combinatorial Conference, Discrete Math. 167/168 (1997), 605-615, doi:10.1016/s0012-365x(96)00212-9.
[5]	E. Dobson, A. Malnic, D. Marusic and L. A. Nowitz, Minimal normal subgroups of transitive permutation groups of square-free degree, Discrete Math. 307 (2007), 373-385, doi:10.1016/j. disc.2005.09.029.
[6]	E. Dobson, A. Malnics, D. Marussics and L. A. Nowitz, Semiregular automorphisms of vertex-transitive graphs of certain valencies, J. Combin. Theory Ser. B 97 (2007), 371-380, doi:10. 1016/j.jctb.2006.06.004.
[7]	E. Dobson and D. Marusic, On semiregular elements of solvable groups, Comm. Algebra 39 (2011), 1413-1426, doi:10.1080/00927871003738923.
[8]	B. Fein, W. M. Kantor and M. Schacher, Relative Brauer groups II, J. Reine Angew. Math. 328 (1981), 39-57.
[9]	M. Giudici, Quasiprimitive groups with no fixed point free elements of prime order, J. London Math. Soc. 67 (2003), 73-84, doi:10.1112/s0024610702003812.
[10]	M. Giudici, New constructions of groups without semiregular subgroups, Comm. Algebra 35 (2007), 2719-2730, doi:10.1080/00927870701353357.
[11]	M. Giudici, P. Potocnik and G. Verret, Semiregular automorphisms of edge-transitive graphs, J. Algebraic Combin. 40 (2014), 961-972, doi:10.1007/s10801-014-0515-8.
[12]	M. Giudici and J. Xu, All vertex-transitive locally-quasiprimitive graphs have a semiregular automorphism, J. Algebraic Combin. 25 (2007), 217-232, doi:10.1007/s10801-006-0032-5.
[13]	A. Hujdurovic, K. Kutnar and D. Marusic, Odd automorphisms in vertex-transitive graphs, Ars Math. Contemp. 10 (2016), 427-437, http://amc-journal.eu/index.php/amc/ article/view/104 6.
[14]	K. Kutnar and D. Marusic, Recent trends and future directions in vertex-transitive graphs, Ars Math. Contemp. 1 (2008), 112-125, http://amc-journal.eu/index.php/amc/ article/view/81.
[15]	K. Kutnar and D. Marusic, A complete classification of cubic symmetric graphs of girth 6, J. Combin. Theory Ser. B 99 (2009), 162-184, doi:10.1016/j.jctb.2008.06.001.
[16]	K. Kutnar, D. Marusic, P. Sparl, R.-J. Wang and M.-Y. Xu, Classification of half-arc-transitive graphs of order 4p, European J. Combin. 34 (2013), 1158-1176, doi:10.1016/j.ejc.2013.04. 004.
468
Ars Math. Contemp. 13 (2017) 275-291
[17]	L. Lovasz, Problem 11, in: R. Guy, H. Hanani, N. Sauer and J. Schonheim (eds.), Combinatorial Structures and Their Applications, Gordon & Breach, New York, 1970 pp. 243-246, proceedings of the Calgary International Conference on Combinatorial Structures and their Applications held at the University of Calgary (Calgary, Alberta, Canada, 1969).
[18]	D. Marusic, On vertex symmetric digraphs, Discrete Math. 36 (1981), 69-81, doi:10.1016/ 0012-365x(81)90174-6.
[19]	D. Marusic and R. Scapellato, Permutation groups, vertex-transitive digraphs and semiregular automorphisms, European J. Combin. 19 (1998), 707-712, doi:10.1006/eujc.1997.0192.
[20]	A. Ramos Rivera and P. Sparl, The classification of half-arc-transitive generalizations of Bouwer graphs, European J. Combin. 64 (2017), 88-112, doi:10.1016/j.ejc.2017.04.003.
[21]	P. Spiga, Semiregular elements in cubic vertex-transitive graphs and the restricted Burn-side problem, Math. Proc. Cambridge Philos. Soc. 157 (2014), 45-61, doi:10.1017/ s0305004114000188.
[22]	P. Sparl, A classification of tightly attached half-arc-transitive graphs of valency 4, J. Combin. Theory Ser. B 98 (2008), 1076-1108, doi:10.1016/j.jctb.2008.01.001.
[23]	G. Verret, Arc-transitive graphs of valency 8 have a semiregular automorphism, Ars Math. Contemp. 8 (2015), 29-34, http://amc-journal.eu/index.php/amc/article/ view/492.
[24]	J. Xu, Semiregular automorphisms of arc-transitive graphs with valency pq, European J. Combin. 29 (2008), 622-629, doi:10.1016/j.ejc.2007.04.008.
[25]	S. Zhou, Classification of a family of symmetric graphs with complete 2-arc-transitive quotients, Discrete Math. 309 (2009), 5404-5410, doi:10.1016/j.disc.2008.12.001.