ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 19 (2020) 1-15
https://doi.org/10.26493/1855-3974.2163.5df
(Also available at http://amc-journal.eu)
Hamilton cycles in primitive vertex-transitive graphs of order a product of two primes - the case PSL(2, q2) acting on cosets of PGL(2, q)*
Shaofei Du t ©
Capital Normal University, School of Mathematical Sciences, Bejing 100048, People's Republic of China
Klavdija Kutnar * ©
University of Primorska, UP FAMNIT, Glagoljaska 8, 6000 Koper, Slovenia, and University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia
Dragan Marušič § ©
University of Primorska, UP FAMNIT, Glagoljaska 8, 6000 Koper, Slovenia, and University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia, and IMFM, Jadranska 19, 1000 Ljubljana, Slovenia
Received 27 October 2019, accepted 4 May 2020, published online 26 October 2020
A step forward is made in a long standing Lovasz problem regarding hamiltonicity of vertex-transitive graphs by showing that every connected vertex-transitive graph of order a product of two primes arising from the group action of the projective special linear group PSL(2, q2) on cosets of its subgroup isomorphic to the projective general linear group PGL(2, q) contains a Hamilton cycle.
Keywords: Vertex-transitive graph, Hamilton cycle, automorphism group, orbital graph. Math. Subj. Class. (2020): 05C25, 05C45
* The authors wish to thank Kai Yuan for helpful conversations about the material of this paper and to the referees for their helpful comments and suggestions.
tThis work is supported in part by the National Natural Science Foundation of China (11671276, 11971248). i Corresponding author. This work is supported in part by the Slovenian Research Agency (research program P1-0285 and research projects N1-0038, N1-0062, J1-6720, J1-6743, J1-7051, J1-9110, and J1-1695).
§This work is supported in part by the Slovenian Research Agency (I0-0035, research program P1-0285 and research projects N1-0038, N1-0062, J1-6720, J1-9108, and J1-1695), and in part by H2020 Teaming InnoRenew CoE (grant no. 739574).
E-mail addresses: dushf@mail.cnu.edu.cn (Shaofei Du), klavdija.kutnar@upr.si (Klavdija Kutnar), dragan.marusic@upr.si (Dragan Marusic)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
18
Ars Math. Contemp. 19 (2020) 2-23
1	Introduction
In 1969, Lovasz [20] asked if there exists a finite, connected vertex-transitive graph without a Hamilton path, that is, a simple path going through all vertices of the graph. To this date no such graph is known to exist. Intriguingly, with the exception of K2, only four connected vertex-transitive graphs that do not have a Hamilton cycle are known to exist. These four graphs are the Petersen graph, the Coxeter graph and the two graphs obtained from them by replacing each vertex by a triangle. The fact that none of these four graphs is a Cayley graph has led to a folklore conjecture that every Cayley graph is hamiltonian (see [1, 8, 9, 11, 12, 16, 22, 32, 37] and the survey paper [6] for the current status of this conjecture).
Coming back to the general class of vertex-transitive graphs, the existence of Hamilton paths, and in some cases also Hamilton cycles, in connected vertex-transitive graphs has been shown for graphs of particular orders, such as, kp, k < 6, pj, j < 5 and 2p2 (see [5, 15, 17, 18, 23, 24, 26, 27, 38] and the survey paper [16]). (Throughout this paper p will always denote a prime number.) Further, some partial results have been obtained for graphs of order pq, q < p a prime [2, 25]. The main obstacle to obtaining a complete solution lies in graphs with a primitive automorphism group having no imprimitive subgroup. It is the object of this paper to move a step closer to resolving Lovasz question for vertex-transitive graphs of order a product of two primes by showing existence of Hamilton cycles in graphs arising from the action of PSL(2, q2) on cosets of its subgroup isomorphic to PGL(2, q) (see Theorem 3.2). The strategy used in the proof is introduced in Section 3. In the next section we fix the terminology and notation, and gather same useful results and tools.
2	Terminology, notation and some useful results
2.1	Basic definitions and notation
Throughout this paper graphs are finite, simple and undirected, and groups are finite. Furthermore, a multigraph is a generalization of a graph in which we allow multiedges and loops. Given a graph X we let V(X) and E(X) be the vertex set and the edge set of X, respectively. For adjacent vertices u, v e V(X) we write u ~ v and denote the corresponding edge by uv. Let U and W be disjoint subsets of V(X). The subgraph of X induced by U will be denoted by X (U}. Similarly, we let X [U, W] denote the bipartite subgraph of X induced by the edges having one endvertex in U and the other endvertex in W.
Given a transitive group G acting on a set V, we say that a partition B of V is G-invariant if the elements of G permute the parts, the socalled blocks of B, setwise. If the trivial partitions {V} and {{v} : v e V} are the only G-invariant partitions of V, then G is primitive, and is imprimitive otherwise.
A graph X is vertex-transitive if its automorphism group, denoted by Aut X, acts transitively on V (X). A vertex-transitive graph is said to be primitive if every transitive subgroup of its automorphism group is primitive, and is said to be imprimitive otherwise. A graph containing a Hamilton cycle will be sometimes referred as a hamiltonian graph.
2.2	Generalized orbital graphs
In this subsection we recall the orbital graph construction which is used throughout the rest of the paper. A permutation group G on a set V induces the action of G on V x V. The corresponding orbits are called orbitals. An orbital is said to be self-paired if
S. Du, K. Kutnar and D. Marusic: Hamilton cycles in primitive vertex-transitive graphs ... 3
it simultaneously contains or does not contain ordered pairs (x, y) and (y, x), for x, y G V. For an arbitrary union O of orbitals (having empty intersection with the diagonal D = {(x, x) : x G V}), the generalized orbital (di)graph X (V, O) of the action of G on V with respect to O is a simple (di)graph with vertex set V and edge set O. (For simplicity reasons we will refer to any such (di)graph as an orbital (di)graph of G.) It is an (undirected) graph if and only if O coincides with its symmetric closure, that is, O has the property that (x, y) G O implies (y, x) G O. Further, the generalized orbital graph X(V, O) is said to be a basic orbital graph if O is a single orbital or a union of a single orbital and its symmetric closure. Note that the orbital graph X (V, O) is vertex-transitive if and only if G is transitive on V, that the diagonal D is always an orbital provided G acts transitively on V, and that its complement, V x V - D is an orbital if and only if G is doubly transitive.
Every vertex-transitive (di)graph admitting a transitive group of automorphisms G with the corresponding vertex stabilizer H can be constructed as an orbital (di)graph of the action of the group G on the coset space G/H. The orbitals of the action of G on G/H are in 1-1 correspondence with the orbits of the action of H on G/H, called suborbits of G. A suborbit corresponding to a self-paired orbital is said to be self-paired. When presenting the (generalized) orbital (di)graph X (G/H, O) with the corresponding (union) of suborbits S the (di)graph X(G/H, O) is denoted by X(G, H, S).
2.3 Semiregular automorphisms and quotient (multi)graphs
Let m > 1 and n > 2 be integers. An automorphism p of a graph X is called (m, n)-semiregular (in short, semiregular) if as a permutation on V (X) it has a cycle decomposition consisting of m cycles of length n. The question whether all vertex-transitive graphs admit a semiregular automorphism is one of famous open problems in algebraic graph theory (see, for example, [3, 4, 7, 10, 21]). Let P be the set of orbits of p, that is, the orbits of the cyclic subgroup (p) generated by p. Let A, B gP . By d(A) and d(A, B) we denote the valency of X (A) and X [A, B], respectively. (Note that the graph X [A, B] is regular.) We let the quotient graph corresponding to P be the graph Xp whose vertex set equals P with A, B G P adjacent if there exist vertices a G A and b G B, such that a ~ b in X. We let the quotient multigraph corresponding to p be the multigraph Xp whose vertex set is P and in which A, B gP are joined by d(A, B) edges. Note that the quotient graph Xp is precisely the underlying graph of Xp.
2.4 Useful number theory facts
For a prime power r a finite field of order r will be denoted by Fr, with the subscript r being omitted whenever the order of the field is clear from the context. As usual, set
F* = F \ {0}. Set S* = {a2 : a G F*} and N* = F* \ S*. The elements of S* and N* will be called squares and non-squares, respectively. The following basic number-theoretic results will be needed.
Proposition 2.1 ([35, Theorem 21.2]). Let F be a finite field of odd prime order p. Then -1 G S* if p = 1 (mod 4), and -1 G N* if p = 3 (mod 4).
Proposition 2.2 ([35, Theorem 21.4]). Let F be a finite field of odd prime order p. Then 2 G S* if p = 1, 7 (mod 8), and 2 G N* if p = 3, 5 (mod 8).
18
Ars Math. Contemp. 19 (2020) 4-23
Proposition 2.3 ([29, p. 167]). Let F be a finite field of odd prime order p. Then
In particular, if p = 1 (mod 4) then |S* n (S* + 1)| = (p - 5)/4, |N* n (N* + 1)| = (p - 1)/4, and |S* n (N* + 1)| = |S* n (N* - 1)| = (p - 1)/4.
Using Proposition 2.3 the following result may be easily deduced.
Proposition 2.4. Let F be a finite field of odd prime order p. Then for any k G F*, the equation x2 + y2 = k has p - 1 solutions if p = 1 (mod 4), and p +1 solutions if p = 3 (mod 4).
3 Vertex-transitive graphs of order pq
Vertex-transitive graphs whose order is a product of two different odd primes p and q, where p > q can be conveniently split into three mutually disjoint classes. The first class consists of graphs admitting an imprimitive subgroup of automorphisms with blocks of size p - it coincides with (q,p)-metacirculants [2]. The second class consists of graphs admitting an imprimitive subgroup of automorphisms with blocks of size q but no imprimitive subgroup of automorphisms with blocks of size p - it coincides with the class of socalled Fermat graphs, which are certain q-fold covers of Kp where p is a Fermat prime [28]. The third class consists of vertex-transitive graphs with no imprimitive subgroup of automorphisms. Following [31, Theorem 2.1] the theorem below gives a complete classification of connected vertex-transitive graphs of order pq (see also [33, 34]). We would like to remark, however, that there is an additional family of primitive graphs of order 91 = 7 • 13 that was not covered neither in [31] nor in [34]. This is due to a missing case in Liebeck-Saxl's table [19] of primitive group actions of degree mp, m < p. This missing case consists of primitive groups of degree 91 = 7 • 13 with socle PSL(2,13) acting on cosets of A4. In the classification theorem below this missing case is included in Row 7 of Table 1.
Theorem 3.1 ([31, Theorem 2.1]). A connected vertex-transitive graph of order pq, where p and q are odd primes and p > q, must be one of the following:
(i)	a metacirculant,
(ii)	a Fermat graph,
(iii)	a generalized orbital graph associated with one of the groups in Table 1.
The existence of Hamilton cycles in graphs given in Theorem 3.1(i) and (ii) was proved, respectively, in [2] and [25]. It is the aim of this paper to make the next step towards proving the existence of Hamilton cycles in every connected vertex-transitive of order a product of two primes with the exception of the Petersen graph, by showing existence of Hamilton cycles in graphs arising from Row 5 of Table 1.
Theorem 3.2. Vertex-transitive graphs arising from the action of PSL(2, q2) on PGL(2, q) given in Row 5 of Table 1 are hamiltonian.
(mod 4), (mod 4).
S. Du, K. Kutnar and D. Marusic: Hamilton cycles in primitive vertex-transitive graphs ... 5
Table 1: Primitive groups of degree pq without imprimitive subgroups and with non-isomorphic generalized orbital graphs.
Row	soc G	fe q)	Action	Comment
1	2)	(2d - e, 2d-1 + e)	singular 1-spaces	e = +1 : d Fermat prime e = — 1 : d — 1 Mersenne prime
2	M22	(11, 7)	see Atlas	
3	A7	(7, 5)	triples	
4	PSL(2, 61)	(61, 31)	cosets of A5	
5	PSL(2, q2)	( q2+1 ,q)	cosets of PGL(2, q)	q > 5
6	PSL(2,p)	(p, )	cosets of Dp-i	p = 1 (mod 4) P > 13
7	PSL(2,13)	(13, 7)	cosets of A4	missing in [19]
The existence of Hamilton cycles needs to be proved for all connected generalized orbital graphs arising from these actions. Recall that a generalized orbital graph is a union of basic orbital graphs. Since the considered action is primitive and hence the corresponding basic orbital graphs are connected, it suffices to prove the existence of Hamilton cycles solely in basic orbital graphs of this action. This is done in Section 4. The method used is for the most part based on the socalled lifting cycle technique [1,16,22]. Lifts of Hamilton cycles from quotient graphs which themselves have a Hamilton cycle are always possible, for example, when the quotienting is done relative to a semiregular automorphism of prime order and when the corresponding quotient multigraph has two adjacent orbits joined by a double edge contained in a Hamilton cycle. This double edge gives us the possibility to conveniently "change direction" so as to get a walk in the quotient that lifts to a full cycle above. By [21, Theorem 3.4] a vertex-transitive graph of order pq, q < p primes, contains a (q,p)-semiregular automorphism. The lifting cycle technique, however, can only be applied provided appropriate Hamilton cycles can be found in the corresponding quotients. It so happens that graphs arising from Row 5 of Table 1 also admit (p, q)-semiregular automorphisms, and it is with respect to these automorphisms that the lifting cycle technique is applied. In constructing Hamilton cycles, the corresponding quotients have proved to be easier to work with than the quotients obtained from (q,p)-semiregular automorphisms. Namely, as one would expect, it is precisely the existence of Hamilton cycles in the quotients that represents the hardest obstacle one needs to overcome in order to assure the existence of Hamilton cycles in the graphs in question. In this respect the well-known Jackson theorem will be useful.
Proposition 3.3 (Jackson Theorem [13, Theorem 6]). Every 2-connected regular graph of order n and valency at least n/3 contains a Hamilton cycle.
It will be useful to introduce the following terminology. Let X be a graph that admits an (m, n)-semiregular automorphism p. Let P = {Si, S2,..., Sm} be the set of orbits
18
Ars Math. Contemp. 19 (2020) 6-23
of p, and let n: X ^ Xp be the corresponding projection of X to its quotient Xp. For a (possibly closed) path W = Sil Si2 ■ ■ ■ Sik in Xp we let the lift of 'W be the set of all paths in X that project to W. The proof of following lemma is straightforward and is just a reformulation of [26, Lemma 5].
Lemma 3.4. Let X be a graph admitting an (m, p)-semiregular automorphism p, where p is a prime. Let C be a cycle of length k in the quotient graph Xp, where P is the set of orbits of p. Then, the lift of C either contains a cycle of length kp or it consists ofp disjoint k-cycles. In the latter case we have d(S, S') = 1 for every edge SS' of C.
4 Actions of PSL(2,q2)
The following group-theoretic result due to Manning will be needed in the proof of Theorem 3.2.
Proposition 4.1 ([36, Theorem 3.6']). Let G be a transitive group on Q and let H = Ga for some a G Q. Suppose that K < G and at least one G-conjugate of K is contained in H. Suppose further that the set of G-conjugates of K which are contained in H form t conjugacy classes under H with representatives K1,K2,..., Kt. Then K fixes Et=i |NG(Ki) : Nh(Ki)| points of Q.
Let Fq2 = Fq(a), where a2 = 0 for Fq = (d). Let G = PSL(2, q2), where q > 5 is an odd prime. For simplicity reasons we refer to the elements of G as matrices; this should cause no confusion. Then G has two conjugacy classes of subgroups isomorphic to PGL(2, q), with the corresponding representatives H and H'. Since each element in PGL(2, q2) \ PSL(2, q2) interchanges these two classes, it suffices to consider the action of G on the set H of right cosets of H in G. The degree of this action is pq, where P = (q2 + 1)/2. Without loss of generality let
H
1

A : A
a b c d
,a,b,c,d G Fq> < G,
and
H' = Hg where g
1 0
0 p
where p G F*2 \ (F*2 )2. Let
Q =
1 P 01
and Qi
11 01
Then Q < H' and Q n H = 1. Moreover, we have the following result.
Lemma 4.2. The action of Q on H is semiregular. Furthermore, the action of its normal-izer Ng(Q) on H has q+1 orbits of length q and one orbit of length q (q2-1).
Proof. We first prove that the action of Q on H is semiregular. Suppose on the contrary that there exists g G G such that HgQ = Hg. Then HgQg-1 = H, and so gQg-1 < H. But this contradicts the choice of Q. Hence Q is semiregular on H.
S. Du, K. Kutnar and D. Marusic: Hamilton cycles in primitive vertex-transitive graphs ... 7
One can see that
a b
N = Ng(Q) =
0
-i
G (a),b G = Z2 xZ,_i.
We now compute the orbits of N in its action on H, by analyzing subgroups of N conjugate in G to subgroups of H. (Note that there is only one conjugacy class of subgroups in G isomorphic to N.) Observe that a subgroup of N is isomorphic to one of the following groups: Z^, x Zq-1, Z^ x Z;, where 2 < l < q - 1, Zq, Zq x Zq-1, Zq x Z;, where 2 < l < q - 1, and Z;, where l divides q - 1. Since Q is semiregular on H no subgroup of N containing Q fixes a coset in H (that is, no subgroup of N containing Q is conjugate to a subgroup of H). Further, there exists unique subgroup of order q2 in N, which clearly contains Q, and so this subgroup cannot fix a coset in H as well. Therefore, we only need to consider subgroups of N isomorphic to Zq x Z; and Z;, where l divides q - 1.
The group N contains q + 1 conjugacy classes of maximal subgroups isomorphic to Zq x Zq-1, which are divided into two G-conjugate subsets of equal size, with the respective representatives:
K
a b 0 a-1
a G (a), b G Fq > and I
a b,0 0 a-1
: a G (a),b G Fq
where K is contained in H and I is not. Let K = Kg be a subgroup of N conjugate to K. Since H has only one conjugacy class of subgroups isomorphic to K, we have t =1 (for the meaning of t, see Proposition 4.1). Since NG(K) = NH(K) = K, it therefore follows from Proposition 4.1 that Kj fixes only the coset Hg. In view of maximality of Kj in N, the N-orbit of Hg on H is of length |N | /1 Kj | = q. Since the G-conjugates of K in N form q+ different conjugacy classes inside N, we can conclude that N has orbits of length q.
Let Ko be the subgroup of order q in K. Since |NG(Ko) : Nh (Ko)| = |N : K| = q, any Kg < N fixes q cosets, which form the N-orbit containing Hg (see the the previous paragraph). Let K1 be a subgroup of K isomorphic to Zq x Z;, where l | q - 1 and l ^ {1, q - 1}. One may check that any Kg < N has the same fixed cosets as K (and so it is a subgroup of a coset stabilizer in N). Consequently N does not have orbits of length q • for 1 < l < q -1. Further, for any subgroup K2 < K of H isomorphic to Z;, where l divides q - 1 and l > 3, the fact that |NG(K2) : Nh(K2) = |Dq2_1 : D2(q-1)| = 2+1, implies that K2 fixes ^j1 cosets. These cosets are clearly contained in the above ^r1 orbits of N of length q, and consequently N does not have orbits of length 2—1.
We have therefore shown that the only other possible stabilizers are Z2 and Z1. Since |H| = q(q2 + 1)/2 and since the length of an orbit of N on H with coset stabilizer isomorphic to Z2 or to Z1 equals, respectively, q (2-1) and q2 (q - 1), we have
= + aq2^^ + b,2(, - 1),	(4.1)
where a is the number of orbits of N on H with coset stabilizer isomorphic to Z2 and b is the number of orbits of N on H on which N acts regularly. The equation (4.1) simplifies to q2 = q + aq(q - 1) + 2bq(q - 1), which clearly has a = 1 and b = 0 as the only possible solution. This completes the proof of Lemma 4.2.	□
a
a
18
Ars Math. Contemp. 19 (2020) 8-23
Lemma 4.2 will play an essential part in our construction of Hamilton cycles in basic orbital graphs arising from the action of PSL(2, q2) on cosets of PGL(2, q) given in Row 5 of Table 1. The strategy goes as follows. Let X be such an orbital graph. By Lemma 4.2, the action of the normalizer N = NG(Q) on the quotient graph Xq with respect to the orbits Q of a semiregular subgroup Q consists of one large orbit of length q(q - 1)/2 and (q + 1)/2 isolated fixed points. We will show the existence of a Hamilton cycle in X by first showing that the subgraph of Xq induced on the large orbit has at most two connected components and that each component contains a Hamilton cycle with double edges in the corresponding quotient multigraph. If there is only one component then its Hamilton cycle is modified to a Hamilton cycle in Xq by choosing in an arbitrary manner (q + 1)/2 edges and replacing them by 2-paths having as central vertices the (q + 1)/2 isolated fixed points of N in Xq. By Lemma 3.4, this cycle lifts to a Hamilton cycle in X. Such 2-paths indeed exist because every isolated fixed point has to be adjacent to every vertex in the large orbit (see Lemma 4.5). If the subgraph of Xq induced on the large orbit has two components with corresponding Hamilton cycles C0 and Ci, then a Hamilton cycle in X is constructed by first constructing a Hamilton cycle in Xq in the following way. We use two isolated fixed points to modify these two cycles C0 and C1 into a cycle of length q2(q - 1)/2 + 2 by replacing an edge in C0 and an edge in Ci by two 2-paths each having one endvertex in C0 and the other in C1, whereas the central vertices are the above two isolated fixed points. In order to produce the desired Hamilton cycle in Xq the remaining isolated fixed points are attached to this cycle in the same manner as in the case of one component. By Lemma 3.4, this cycle lifts to a Hamilton cycle in X. Formal proofs are given in Propositions 4.7 and 4.8.
It follows from the previous paragraph that we only need to prove that the subgraph of Xq induced on the large orbit of N contains a Hamilton cycle with at least one double edge in the corresponding multigraph or two components each of which contains a Hamilton cycle with double edges in the corresponding multigraph. For this purpose we now proceed with the analysis of the structure of basic orbital graphs (and corresponding suborbits) arising from the action of PSL(2, q2) on cosets of PGL(2, q) given in Row 5 of Table 1. We apply the approach taken in [34] where the computation of suborbits is done using the fact that PSL(2, q2) = PO-(4, q) and that the action of PSL(2, q2) on the cosets of PGL(2, q) is equivalent to the induced action of P^-(4, q) on nonsingular 1-dimensional vector subspaces (v) such that Q(v) = 1, where Q is the associated quadratic form. For the sake of completeness, we give a more detailed description of this action together with a short explanation of the isomorphism PSL(2, q2) = P^-(4,q) (see [14, p. 45] for details).
Let ^ e Aut(Fq 2) be the Frobenius automorphism of Fq2 defined by the rule ^>(a) = aq, a e Fq2. (Note that ^ is an involution.) Let W = (w1, w2) = Fq22 be a natural SL(2, q2)-module. Then SL(2, q2) acts on W in a natural way. In particular, the action of
d e SL(2, q2) on W is given by
w1g = aw1 + bw2,
w2g = cw1 + dw2.
Let W be an SL(2, q2)-module with the underlying space W and the action of SL(2, q2) defined by the rule w * g = wg^, where g = (aj) e SL(2, q2) and g^ = (^(a^)j) = (aq.). One can now see that the action •: W < W x SL(2, q2) ^ W < W defined by the
S. Du, K. Kutnar and D. Marusic: Hamilton cycles in primitive vertex-transitive graphs ... 9
rule
(w ( w') • g = wg ( w' * g = wg ( w'g'

is an action of SL(2, q2) on the 4-dimensional space W ( W (that is, on a tensor product of W and W). The kernel of this action equals Z(SL(2, q2)), and thus this is in fact a 4-dimensional representation of G = PSL(2, q2) (an embedding of G into GL(4, q2)). Further, the set B = {vi, v2, v3, v4}, where vi = wi ( wi, v2 = w2 ( w2, v3 = wi ( w2 + w2 ( w1, v4 = a(w1 ( w2 — w2 ( w1), is a basis for W ( W over Fq2.
Since G fixes the 4-dimensional space V = spanF (B) over Fq it can be viewed as a subgroup of GL(4, q). A non-degenerate symplectic form f of W and W defined by f (wi, w2) = —f (w2, wi) = 1 and f (wi, wi) = f (w2, w2) =0 is fixed by SL(2, q2). It follows that G fixes a non-degenerate symmetric bilinear form of W ( W defined by the rule
(wi ( w2, w'l ( w2') = f (wi, w'')f (w2, w2').
Then we have
(0	1	0	0
1	0	0	0
0	0	-2	0
	0	0	20/
((vi, vj ))4x4
and so for x = J24=i xivi € V and y = J24=i Vivi € V the symmetric form (x, y) and the associated quadratic form Q are given by the rules
(x, y) = x2yi + xiy2 — 2x3^3 + 2^x4 y4 and Q(x) = ^(x, x) = xix2 — x3 + 0x4.
By computation it follows that Q has q2 + 1 singular 1-dimensional subspaces of V. As for the remaining q(q2 + 1) nonsingular 1-dimensional subspaces, G has two orbits {(v) : Q(v) = 1, v € V} and {(v) : Q(v) € F* \ £*, v € V}. Since these two representations of G are equivalent, we set Q to be the first of these two orbits. Then the action of G on H is equivalent to the action of G on Q. By comparing their orders, we get PSL(2, q2) = PQ- (4, q). The following result characterizing suborbits of the action of G on the cosets of PGL(2, q) in the context of the action of PQ- (4, q) on Q was proved in [ ] (see also [ ]).
Proposition 4.3 ([34, Lemma 4.1]). For any (v) € Q where Q(v) = 1, the nontrivial suborbits of the action of G on Q (that is, the orbits of Gty}) are the sets S±\ = {(x) € Q : (x, v) = ±2A, Q(x) = 1}, where A € Fq, and
(i)	|So| = qiq2Ei1 for q = ±1 (mod 4);
(ii)	|S±i| = q2 — 1;
(iii)	|S±A| = q(q +1) for A2 — 1 € N*;
(iv)	|S±A| = q(q — 1) for A2 — 1 € S*.
Moreover, all the suborbits are self-paired.
18
Ars Math. Contemp. 19 (2020) 10-23
Let X = X (G, H, be the basic orbital graph associated with and take
e G.
1 1 0 1
For k € Fq we have
vipk = V1 + k2V2 + kV3,
k
V2P = V2, k
V3P = 2kV2 + V3, k
V4pk = V4,
and so pk maps the vector x = ^4=1 XjVj € V to
xpk = xiVi + (k2xi + X2 + 2kx3)V2 + (kxi + X3)V3 + X4V4.
Identifying x with (xi, x2, x3, x4) we have xpk = (xi, k2xi + x2 + 2kx3, kxi + x3, x4). One can check that for k = 0 we have (xpk} = (x), and thus p is (p, q)-semiregular. Let Q = (p), and let Q be the set of orbits of Q. These orbits will be referred to as blocks. The set Q decomposes into two subsets each of which is a union of blocks from Q:
I = ((0, 0,x3,x4))Q = {((0, 2kx3,x3,x4)) : k € Fq},
where - x2 + 0x4 = 1.
L = ((xi, x2, 0, x4))Q = {((xi, k2xi + x2, kxi, x4)) : k € Fq}
q}
2
where xi =0 and xix2 + 0x2 = 1.
Note that the subset I contains q(q+i) vertices which form blocks, and the subset L
contains q (q,-i) vertices which form q(q2-i) blocks. By Iq and Lq, we denote, respectively, the set of blocks in I and L; that is, Q = Iq U Lq.
Remark 4.4. Recall that
N = Ng (Q) =
€ (a), b € Fq2
0 a-i
One may check directly that Iq consists precisely of the orbits of N of length q and that L is the orbit of N of length q2(q-i).
In the next lemma we observe that X (L) and X (L)q are vertex-transitive and show that the bipartite subgraph of Xq induced by Iq and Lq is a complete bipartite graph.
Lemma 4.5. With the above notation, the following hold:
(i)	The induced subgraph X (L) and the quotient graph X (L) q are both vertex-transitive.
(ii)	For (x)Q € Iq and (y)Q € Lq we have
d«x)Q. mq> = j1; f* =
b
a
S. Du, K. Kutnar and D. Marusic: Hamilton cycles in primitive vertex-transitive graphs ... 11
Proof. By Remark 4.4, N is transitive on L, and so the induced subgraph X(L) and the quotient graph X (L) q are both vertex transitive, and thus (i) holds.
To prove (ii), take two arbitrary blocks (x)Q G Iq where x = (0,0,x3,x4) and (y)Q g Lq where y = (yi, y2,0, y4). Then yi =0 and X3 = 0, and (x) ~ (ypk) if and only if
(x, ypk ) that is, if and only if
((0, 0, X3, X4), (yi, k yi + y2, kyi, y4)) = ±2A,
—2x3kyi + 20X4y4 = ±2A.
(4.2)
From (4.2) we get that k = dXixy34yJX and so for given (x) and (y) we have a unique solution for k if A = 0 and two solutions if A = 0. It follows that for (x)Q G Iq and (y)Q G Lq we have d((x)Q, (y)Q) = 1 or 2, depending on whether A = 0 or A = 0, completing part (ii) of Lemma 4.5.	□
In what follows, we divide the proof into two cases depending on whether A = 0 or A = 0.
4.1 Case S0
Let
J2, if q = 1, 3 (mod 8), £ [0, if q = 5, 7 (mod 8).
The following lemma gives us the number of edges inside a block and between two blocks from Lq for the orbital graph X(G, H, S0).
Lemma 4.6. Lei X = X (G, H, S0). Then for (x)Q G Lq the following hold:
(i)	d((x)Q) = e,
(ii)	d((x)Q, (y)Q) = 1 for ^ blocks (y)Q G Lq,
(iii)	d((x)Q, (y)Q) = 2for 1 (q2 - 3q - 2(e + 1)) blocks (y)Q G Lq f q = 1 (mod 4), and for 4 (q2 - q - 2(e + 1)) blocks (y)Q G Lq if q = 3 (mod 4).
Proof. Fix a block (x)Q G Lq where x = (1,1,0,0). For any (y)Q G Lq, where y = (yi, y2, 0, y4) with yi = 0, we have (x) ~ (y)pk if and only if (k2 + 1)yi + y2 = 0, and therefore, since y1y2 + 0y4 = 1, if and only if
k2 = —y-2 + %rV)2 — 1
(4.3)
It follows from (4.3) that (x) is adjacent to one vertex in the block (y)Q G Lq if k = 0 and to two vertices in this block if k = 0. Clearly, k = 0 if and only if
0y2 = 1 + y2.
(4.4)
Proposition 2.4 implies that (4.4) has q +1 solutions for (yi, y4), and therefore since (y) = (-y) we have a total of choices for (y). This implies that d( (x)Q, (y)Q) = 1 for ^y1 blocks (y)Q G Lq, proving part (ii).
18
Ars Math. Contemp. 19 (2020) 12-23
To prove part (i), take y = ±x = ±(1,1,0,0). Then, by (4.3), there are edges inside the block (x)Q if and only if k2 = -2. This equation has solutions if and only if q = 1,3 (mod 8) (see Propositions 2.1 and 2.2), and thus the induced subgraph X((x)Q) is a q-cycle for q = 1, 3 (mod 8) and a totally disconnected graph qK if q = 5, 7 (mod 8).
Finally, to prove part (iii) let m be the number of blocks (y)Q G Lq for which d((x)Q, (y)Q) = 2. Suppose first that q = 1 (mod 4). Then, combining together the facts that X is of valency 2q(q - 1), that d((x)Q) = e and that (x) is adjacent to 2 (q + 1) vertices in the set I and to exactly one vertex from £¿4 blocks in Lq, we have
m =1 (2q(q - 1) - ^ - ^ - e) =1(q2 - 3q - 2(1 + e)).
Suppose now that q = 3 (mod 4). Then, replacing the valency of X in the above computation with 1 q(q +1) we obtain, as desired, that m = 4(q2 - q - 2(1+ e)). □
We are now ready to prove existence of a Hamilton cycle in X (G, H, S0). Proposition 4.7. The graph X = X(G, H, S0) is hamiltonian.
Proof. Let X (L)' be the graph obtained from X (L) by deleting the edges between any two blocks B1, B2 g Lq for which d(B1, B2) = 1 (see Lemma 4.6(ii)). By Lemma 4.5, X (L)fi is vertex-transitive, and consequently one can see that also X(L)Q is vertex-transitive.
If q = 1 (mod 4) then Lemma 4.6(iii) implies that X(L)Q is of valency m = 1 (q2 -3q - 2(1 + e)). If, however, q = 3 (mod 4) then Lemma 4.6(iii) implies that X(L)Q is of valency m = 4(q2 -q-2(1 + e)). If q = 5 thene = 0 andm = 1 (q2 -3q-2(1 + e)) = 2. If q > 7 then using the facts that q2 - 7q - 6(1 + e) > 0 for q = 1 (mod 4) and that q2 - q - 6(1 + e) > 0 for q = 3 (mod 4) one can see that
m = 4(q2 - (2 ± 1)q - 2(1 + e)) > 1 ^il = 3|Lq|.
Suppose first that X (L)Q is connected. If q = 5, then X (L)Q is just a cycle C. For q > 7, by Proposition 3.3, X(L)Q admits a Hamilton cycle, say C again. Clearly C is also a Hamilton cycle of X (L)q. Form C a Hamilton cycle in Xq can be constructed by choosing arbitrarily (q + 1)/2 edges and replacing them by 2-paths having as central vertices the (q + 1)/2 isolated fixed points of N in Xq. By Lemma 3.4, this lifts to a Hamilton cycle in X.
Next, suppose that X (L)Q is disconnected. For q = 5, since X (L)Q is a vertex transitive graph of order 10 and degree 2, it must be a union of two 5-cycles. For q > 7, since m > 1 |Lq|, it follows that X(L)Q has just two components. By Proposition 3.3, each component admits a Hamilton cycle. Take a respective Hamilton path for each component, say U = U1U2 • • • U, and U' = U'U2 • • • U', where l = >. Choose any two isolated fixed points W1 and W2 and construct the cycle D = W1UW2U' W1. Choose arbitrarily (q + 1)/2 - 2 edges in U U U' and replace them by 2-paths having as central vertices the remaining (q +1)/2 - 2 isolated fixed points. Then we get a Hamilton cycle in Xq, which, by Lemma 3.4, lifts to a Hamilton cycle in X.	□
S. Du, K. Kutnar and D. Marusic: Hamilton cycles in primitive vertex-transitive graphs ... 13
4.2 Case Sx with A = 0
Proposition 4.8. The graph X = X(G, H, S±a), where A = 0, is hamiltonian.
Proof. As in the proof of Lemma 4.6, fix a block (x) Q e Lq where x = (1,1, 0,0). For any (y)Q e Lq where y = (yi,y2,0,y4) with yi = 0, we have ypk = (yi,k2y1 + y2, kyi, y4), and so (x) ~ (ypk) if and only if (k2 + 1)y1 + y2 = ±2A, which implies, since y1y2 + 0y| = 1, that k2 = ±2Ay-1 - y-2 + #(y-1y4)2 - 1. It follows that there are at most four solutions for k. Hence each vertex in L is adjacent to at most four vertices in each block from Lq (including the block containing this vertex).
Let m be the valency of X(L)q. Since, by Proposition 4.3, the valency of X is, respectively, q2 - 1, q2 - q and q2 + q, we get that m > 1 |LP | = 1provided
m > 4((q2 - j) - (q + 1) - 4) = 4(q2 - q - j - 5) > 3,
where j e {1, q, -q} for q > 7 and j e {1, -q} for q = 5. One can check that this inequality holds for all q > 5. We can therefore conclude that X (L)q, which is vertex-transitive by Lemma 4.5, has at most two connected components. The rest of the argument follows word by word from the argument given in the proof of Proposition 4.7, since, by Lemma 4.5, d((x)Q, (y)Q) = 2, for any (x)Q e Iq and (y)Q e Lq.	□
5 Proof of Theorem 3.2
Proof of Theorem 3.2. Let X be a connected vertex-transitive graph of order pq, where q and p = (q2 +1) /2 are primes, arising the action given in Row 5 of Table 1. As explained in Section 3, we can assume that X is a basic orbital graph arising from a group action given in Row 5 of Table 1, and thus it admits a Hamilton cycle by Propositions 4.7 and 4.8. □
ORCID iDs
Shaofei Du S> https://orcid.org/0000-0001-6725-9293 Klavdija Kutnar © https://orcid.org/0000-0002-9836-6398 Dragan Marusic © https://orcid.org/0000-0002-8452-3057
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]	B. Alspach and T. D. Parsons, On Hamiltonian cycles in metacirculant graphs, in: E. Mendelsohn (ed.), Algebraic and Geometric Combinatorics, North-Holland, Amsterdam, volume 65 of North-Holland Mathematics Studies, pp. 1-7, 1982, doi:10.1016/s0304-0208(08)73249-3.
[3]	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.
[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]	Y. Q. Chen, On Hamiltonicity of vertex-transitive graphs and digraphs of order p4, J. Comb. Theory Ser. B 72 (1998), 110-121, doi:10.1006/jctb.1997.1796.
18
Ars Math. Contemp. 19 (2020) 14-23
[6]	S. J. Curran and J. A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey, Discrete Math. 156 (1996), 1-18, doi:10.1016/0012-365x(95)00072-5.
[7]	E. Dobson, A. Malnic, D. Marusic and L. A. Nowitz, Semiregular automorphisms of vertex-transitive graphs of certain valencies, J. Comb. Theory Ser. B 97 (2007), 371-380, doi:10.1016/ j.jctb.2006.06.004.
[8]	E. Durnberger, Connected Cayley graphs of semidirect products of cyclic groups of prime order by abelian groups are Hamiltonian, Discrete Math. 46 (1983), 55-68, doi:10.1016/ 0012-365x(83)90270-4.
[9]	E. Ghaderpour and D. W. Morris, Cayley graphs on nilpotent groups with cyclic commutator subgroup are Hamiltonian, Ars Math. Contemp. 7 (2014), 55-72, doi:10.26493/1855-3974.280. 8d3.
[10]	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.
[11]	H. Glover and D. Marusic, Hamiltonicity of cubic Cayley graphs, J. Eur. Math. Soc. 9 (2007), 775-787, doi:10.4171/jems/96.
[12]	H. H. Glover, K. Kutnar, A. Malnic and D. Marusic, Hamilton cycles in (2, odd, 3)-Cayley graphs, Proc. Lond. Math. Soc. 104 (2012), 1171-1197, doi:10.1112/plms/pdr042.
[13]	B. Jackson, Hamilton cycles in regular 2-connected graphs, J. Comb. Theory Ser. B 29 (1980), 27-46, doi:10.1016/0095-8956(80)90042-8.
[14]	P. Kleidman and M. Liebeck, The Subgroup Structure of the Finite Classical Groups, volume 129 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 1990, doi:10.1017/cbo9780511629235.
[15]	K. Kutnar and D. Marusic, Hamiltonicity of vertex-transitive graphs of order 4p, European J. Combin. 29 (2008), 423-438, doi:10.1016/j.ejc.2007.02.002.
[16]	K. Kutnar and D. Marusic, Hamilton cycles and paths in vertex-transitive graphs — Current directions, Discrete Math 309 (2009), 5491-5500, doi:10.1016/j.disc.2009.02.017.
[17]	K. Kutnar, D. Marusic and C. Zhang, Hamilton paths in vertex-transitive graphs of order 10p, European J. Combin. 33 (2012), 1043-1077, doi:10.1016/j.ejc.2012.01.005.
[18]	K. Kutnar and P. Sparl, Hamilton paths and cycles in vertex-transitive graphs of order 6p, Discrete Math 309 (2009), 5444-5460, doi:10.1016/j.disc.2008.12.005.
[19]	M. W. Liebeck and J. Saxl, Primitive permutation groups containing an element of large prime order, J. London Math. Soc. 31 (1985), 237-249, doi:10.1112/jlms/s2-31.2.237.
[20]	L. Lovasz, The factorization of graphs, in: R. Guy, H. Hanani, N. Sauer and J. Schonheim (eds.), Combinatorial Structures and Their Applications, Gordon and 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, June 1969.
[21]	D. Marusic, On vertex symmetric digraphs, Discrete Math. 36 (1981), 69-81, doi:10.1016/ 0012-365x(81)90174-6.
[22]	D. Marussics, Hamiltonian circuits in Cayley graphs, Discrete Math. 46 (1983), 49-54, doi: 10.1016/0012-365x(83)90269-8.
[23]	D. Marusic, Vertex transitive graphs and digraphs of order pk, in: B. R. Alspach and C. D. Godsil (eds.), Cycles in Graphs, North-Holland, Amsterdam, volume 115 of North-Holland Mathematics Studies, pp. 115-128, 1985, doi:10.1016/s0304-0208(08)73001-9, papers from the workshop held at Simon Fraser University, Burnaby, British Columbia, July 5 - August 20, 1982.
S. Du, K. Kutnar and D. Marusic: Hamilton cycles in primitive vertex-transitive graphs ... 15
[24]	D. Marusic, Hamiltonian cycles in vertex symmetric graphs of order 2p2, Discrete Math. 66 (1987), 169-174, doi:10.1016/0012-365x(87)90129-4.
[25]	D. Marusic, Hamiltonicity of vertex-transitive pq-graphs, in: J. Nesetril and M. Fiedler (eds.), Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, North-Holland, Amsterdam, volume 51 of Annals of Discrete Mathematics, pp. 209-212, 1992, doi: 10.1016/s0167-5060(08)70630-7, proceedings of the symposium held in Prachatice, 1990.
[26]	D. Marusic and T. D. Parsons, Hamiltonian paths in vertex-symmetric graphs of order 5p, Discrete Math 42 (1982), 227-242, doi:10.1016/0012-365x(82)90220-5.
[27]	D. Marusic and T. D. Parsons, Hamiltonian paths in vertex-symmetric graphs of order 4p, Discrete Math 43 (1983), 91-96, doi:10.1016/0012-365x(83)90024-9.
[28]	D. Marusic and R. Scapellato, Characterizing vertex-transitive pq-graphs with an imprimitive automorphism subgroup, J. Graph Theory 16 (1992), 375-387, doi:10.1002/jgt.3190160410.
[29]	D. Marussics and R. Scapellato, A class of non-Cayley vertex-transitive graphs associated with PSL(2,p), Discrete Math 109 (1992), 161-170, doi:10.1016/0012-365x(92)90287-p.
[30]	D. Marusic and R. Scapellato, A class of graphs arising from the action of PSL(2, q2) on cosets of PGL(2, q), Discrete Math 134 (1994), 99-110, doi:10.1016/0012-365x(93)e0065-c.
[31]	D. Marusic and R. Scapellato, Classifying vertex-transitive graphs whose order is a product of two primes, Combinatorica 14 (1994), 187-201, doi:10.1007/bf01215350.
[32]	D. W. Morris, Cayley graphs on groups with commutator subgroup of order 2p are hamiltonian, Art Discrete Appl. Math 1 (2018), #P1.04 (31 pages), doi:10.26493/2590-9770.1240.60e.
[33]	C. E. Praeger, R. J. Wang and M. Y. Xu, Symmetric graphs of order a product of two distinct primes, J. Comb. Theory Ser. B 58 (1993), 299-318, doi:10.1006/jctb.1993.1046.
[34]	C. E. Praeger and M. Y. Xu, Vertex-primitive graphs of order a product of two distinct primes, J. Comb. Theory Ser. B 59 (1993), 245-266, doi:10.1006/jctb.1993.1068.
[35]	J. H. Silverman, A Friendly Introduction to Number Theory, Pearson Education, 4th edition, 2012, https://www.math.brown.edu/-jhs/frint.html.
[36]	H. Wielandt, Finite Permutation Groups, Academic Press, New York-London, 1964.
[37]	D. Witte Morris, Odd-order Cayley graphs with commutator subgroup of order pq are hamiltonian, ArsMath. Contemp. 8 (2015), 1-28, doi:10.26493/1855-3974.330.0e6.
[38]	J.-Y. Zhang, Vertex-transitive digraphs of order p5 are Hamiltonian, Electron. J. Combin. 22 (2015), #P1.76 (12 pages), doi:10.37236/4034.