ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 10 (2016) 427-437
Odd automorphisms in vertex-transitive graphs
Ademir Hujdurovic *, Klavdija Kutnar t
University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia University of Primorska, UP FAMNIT, Glagoljaska 8, 6000 Koper, Slovenia
Dragan Marušič *
University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia University of Primorska, UP FAMNIT, Glagoljaska 8, 6000 Koper, Slovenia IMFM, Jadranska 19, 1000 Ljubljana, Slovenia
Received 24 February 2016, accepted 10 July 2016, published online 25 July 2016
An automorphism of a graph is said to be even/odd if it acts on the set of vertices as an even/odd permutation. In this article we pose the problem of determining which vertex-transitive graphs admit odd automorphisms. Partial results for certain classes of vertex-transitive graphs, in particular for Cayley graphs, are given. As a consequence, a characterization of arc-transitive circulants without odd automorphisms is obtained.
Keywords: Graph, vertex-transitive, automorphism group, even permutation, odd permutation. Math. Subj. Class.: 20B25, 05C25
1 Introduction
Apart from being a rich source of interesting mathematical objects in their own right, vertex-transitive graphs provide a perfect platform for investigating structural properties of transitive permutation groups from a purely combinatorial viewpoint. The recent outburst
*This work is supported in part by the Slovenian Research Agency (research program P1-0285 and research projects N1-0032, N1-0038, and J1-7051).
tThis work is supported in part by the Slovenian Research Agency (research program P1-0285 and research projects N1-0032, N1-0038, J1-6720, J1-6743, and J1-7051), in part by WoodWisdom-Net+, W3B, and in part by NSFC project 11561021.
* This work is supported in part by the Slovenian Research Agency (I0-0035, research program P1-0285 and research projects N1-0032, N1-0038, J1-5433, J1-6720, and J1-7051), and in part by H2020 Teaming InnoRenew CoE.
E-mail address: ademir.hujdurovic@upr.si (Ademir Hujdurovic), klavdija.kutnar@upr.si (Klavdija Kutnar)dragan.marusic@upr.si (Dragan Marusic)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
427
Ars Math. Contemp. 10 (2016) 255-268
of research papers on this topic should therefore come as no surprise. Most of these papers have arisen as direct attempts - by developing consistent theories and strategies - to solve open problems in vertex-transitive graphs; the hamiltonicity problem [17], for example, being perhaps the most popular among them.
In this context knowing the full (or as near as possible) automorphism group of a vertex-transitive graph is important because it provides the most complete description of its structure. While some automorphisms are obvious, often part of the defining properties, there are others, not so obvious and hence more difficult to find.
Consider for example bicirculants, more precisely, n-bicirculants, that is, graphs admitting an automorphism p with two orbits of size n > 2 and no other orbits. There are three essentially different possibilities for such a graph to be vertex-transitive depending on whether its automorphism group contains a swap and/or a mixer, where a swap is an automorphism interchanging the two orbits of p, and a mixer is an automorphism which neither fixes nor interchanges the two orbits of p. For example, the Petersen graph has swaps and mixers, prisms (except for the cube) have only swaps, while the dodecahedron has only mixers. Clearly, swaps are the "obvious" automorphisms and mixers are "not so obvious" ones (see Figure 1).
Figure 1: The Petersen graph, the 5-prism and the dodecahedron - the first two admit a swap, while the third one does not.
In this paper we propose to approach the sometimes elusive separation line between the obvious and not so obvious automorphisms via the even/odd permutations dichotomy. Let us call an automorphism of a graph even/odd if it acts on the vertex set as an even/odd permutation. Further, a graph is said to be even-closed if all of its automorphisms are even. The Petersen graph and odd prisms have odd automorphisms, the swaps being such automorphisms. On the other hand, the dodecahedron has only even automorphisms [13]. Furthermore, consider the two cubic 2k-bicirculants, k > 1, shown in Figure 2 for k = 4. Both have swaps which are even automorphisms. More precisely, all of the automorphisms of the 2k-prism on the left-hand side are even. As for the graph on the right-hand side - the Cayley graph Cay(Z4k, {±1,2k}) on the cyclic group Z4k = (1) - any generator of the left regular representation of Z4k is an odd automorphism (note that the bicirculant structure of this graph arises from the action of the square of any generator of the left regular representation of Z4k).
This brings us to the following natural question: Given a transitive group of even automorphisms H of a graph X, is there a group G < Aut(X) containing odd automorphisms
A. Hujdurovic et al.: Odd automorphisms in vertex-transitive graphs	429
of X and H as a subgroup? In particular, we would like to focus on the following problem. Problem 1.1. Which vertex-transitive graphs admit odd automorphisms?
Of course, in some cases, the answer to the above problem will be purely arithmetic. Such is for example the case with cycles. Clearly, all cycles of even length admit odd automorphisms, while cycles of odd length 2k + 1 admit odd automorphisms if and only if k is odd. The answer for some of the well studied classes of graphs, however, suggest that the above even/odd question goes beyond simple arithmetic conditions and is likely to uncover certain more complex structural properties. For example, while the general distinguishing feature for cubic symmetric graphs (with respect to the above question) is their order 2n, n even/odd, there are exceptions on both sides. Namely, there exist cubic symmetric graphs without odd automorphisms for n odd, and with odd automorphisms for n even, see [13].
In this paper a special emphasis is given to certain classes of Cayley graphs (see Section 3), such as circulants for example. Theorem 3.15 gives a necessary and sufficient condition for a normal circulant to be even-closed. This result combined together with certain other results of this section then leads to a characterization of even-closed arc-transitive circulants, see Theorem 3.16. In Section 4 the even/odd question is discussed in the more general context of vertex-transitive graphs.
2 Preliminaries
Here we bring together definitions, notation and some results that will be needed in the remaining sections.
For a finite simple graph X let V(X), E(X), A(X) and Aut(X) be its vertex set, its edge set, its arc set and its automorphism group, respectively. A graph is said to be vertex-transitive, edge-transitive and/or arc-transitive (also symmetric) if its automorphism group acts transitively on the set of vertices, the set of edges, and/or the set of arcs of the graph, respectively. A non-identity automorphism is semiregular, in particular (m,n)-semiregular if it has m cycles of equal length n in its cycle decomposition, in other words m orbits of equal length n. An n-circulant (circulant, in short) is a graph admitting a (1, n)-semiregular automorphism, and an n-bicirculant (bicirculant, in short) is a graph admitting a (2, n)-semiregular automorphism.
430
Ars Math. Contemp. 10 (2016) 255-268
Given a group G and a symmetric subset S = S-1 of G \ {1}, the Cayley graph X = Cay(G, S) has vertex set G and edges of the form {g, gs} for all g G G and s G S. Every Cayley graph is vertex-transitive but there exist vertex-transitive graphs that are not Cayley, the Petersen graph being the smallest such graph. Cayley graphs are characterized in the following way. A graph is a Cayley graph of a group G if and only if its automorphism group contains a regular subgroup GL, referred to as the left regular representation of G, isomorphic to G, see [19]. Using the terminology and notation of Cayley graphs, note that an n-circulant is a Cayley graph Cay(G, S) on a cyclic group G of order n relative to some symmetric subset S of G \ {id}, usually denoted by Circ(n, S).
The first of the two group-theoretic observations below reduces the question of existence of odd automorphisms to Sylow 2-subgroups of the automorphism group.
Proposition 2.1. A permutation group G contains an odd permutation if and only if its Sylow 2-subgroups contain an odd permutation.
Proof. Since any odd permutation a is of even order, we can conclude that ak, where k is the largest odd number dividing the order of a, is a non-trivial odd permutation belonging to a Sylow 2-subgroup of G.	□
Proposition 2.2. A permutation group G acting semiregularly with an odd number of orbits admits odd permutations if and only if its Sylow 2-subgroups are cyclic and non-trivial.
Proof. Note that any Sylow 2-subgroup of G must also have an odd number of orbits. Thus if a Sylow 2-subgroup is cyclic and non-trivial, the corresponding generators are odd permutations. On the other hand, if a Sylow 2-subgroup J is not cyclic (or is trivial) then the semiregularity of G implies that all of the elements of J must be even permutations. By Proposition 2.1 G itself consists solely of even permutations.	□
As a consequence of Proposition 2.2, for some classes of graphs the existence of odd automorphisms is easy to establish. For instance, in Cayley graphs the corresponding regular subgroup contains odd automorphisms if and only if its Sylow 2-subgroup is cyclic and non-trivial. When a Sylow 2-subgroup is not cyclic, however, the search for odd automorphisms has to be done outside this regular subgroup, raising the complexity of the problem.
3 Cayley graphs
In this section we give some general results about the existence of odd automorphisms in Cayley graphs and discuss the problem in detail for circulants. The first proposition, a corollary of Proposition 2.2, gathers straightforward facts about the existence of odd automorphisms in Cayley graphs. (A graph is said to be a graphical regular representation, or a GRR, for a group G if its automorphism group is isomorphic to G and acts regularly on the vertex set of the graph.)
Proposition 3.1. A Cayley graph on a group G admits an odd automorphism in GL if and only if G has cyclic Sylow 2-subgroups. In particular,
•	a Cayley graph of order 2 (mod 4) admits odd automorphisms,
•	a GRR admits an odd automorphism if and only if the Sylow 2-subgroups of G are cyclic.
A. Hujdurovic et al.: Odd automorphisms in vertex-transitive graphs
431
By Proposition 3.1, Cayley graphs of order twice an odd number admit odd automorphisms (they exist in a regular subgroup of the automorphism group). As for Cayley graphs whose order is odd or divisible by 4 the answer is not so simple. The next proposition answers the question of existence of odd automorphisms in particular subgroups of automorphisms of Cayley graphs on abelian groups.
Proposition 3.2. Let X = Cay(G, S) be a Cayley graph on an abelian group G and let t € Aut(G) be such that t(i) = -i. Then (Gl,t} < Aut(X), and there exists an odd automorphism in (GL, t } if and only if one of the following holds:
(i)	|G| = 3 (mod 4) (in which case t is an odd automorphism),
(ii)	|G| = 2 (mod 4),
(iii)	|G| = 0 (mod 4) and a Sylow 2-subgroup of G is cyclic.
Proof. First recall that the mapping t : G ^ G defined by t(i) = -i is an automorphism of the group G if and only if G is abelian. Moreover, since S = -S it is easy to see that t € Aut(X).
Clearly, when |G| = 1 (mod 4) there are no odd automorphisms in (GL, t}. Suppose now that |G| = 1 (mod 4). If |G| = 3 (mod 4) then the involution t has 2k + 1 cycles of length 2 and one fixed vertex in its cyclic decomposition, and so it is an odd automorphism. If |G| = 2 (mod 4) then there exist odd automorphisms in GL < (Gl,t} by Proposition 3.1.
We are therefore left with the case |G| = 0 (mod 4). Hence suppose that G is of such order. If a Sylow 2-subgroup J of GL is cyclic then a generator of J is a product of an odd number |G|/| J| of cycles of length | J|, and is thus an odd automorphism. On the other hand, if J is not cyclic then every element of J has an even number of cycles in its cyclic decomposition. As for t, an element of G is fixed by t if and only if it is an involution. In other words, it fixes the largest elementary abelian 2-group T inside the Sylow 2-subgroup J, say of order 2k. Consequently, the number of transpositions in the cyclic decomposition of t equals |G|/2 - 2k, which is an even number if and only if k > 1. Consequently, t is an odd automorphism if and only if T = Z2 and hence J is cyclic.	□
Corollary 3.3. Let X = Circ(n, S), where S is a symmetric subset of Zn, and either n is even or n = 3 (mod 4). Then X admits odd automorphisms.
When n = 1 (mod 4) the situation is more complex. For example, cycles C4k+1 = Circ(4k + 1, {±1}) admit only even automorphisms. On the other hand, the circulant Circ(13, {±1, ±5}) is an example of a (4k + 1)-circulant admitting odd automorphisms. Namely, one can easily check that the permutation (0)(1,5,12,8)(2,10,11,3)(4, 7, 9, 6) arising from the action of 5 € Z\3 is one of its odd automorphisms. (For a positive integer n we use Z*n to denote the multiplicative group of units of Zn.) We therefore propose the following problem.
Problem 3.4. Classify even-closed circulants of order n = 1 (mod 4).
A partial answer to this problem is given at the end of this section, see Corollary 3.11 and Theorem 3.16. We start with the class of connected arc-transitive circulants. The classification of such circulants, obtained independently by Kovacs [12] and Li [16], is essential to this end. In order to state the classification let us recall the concept of normal Cayley graphs and certain graph products.
432
Ars Math. Contemp. 10 (2016) 255-268
Let X and Y be graphs. The wreath (lexicographic) product X[Y] of X by Y is the graph with vertex set V(X) x V(Y) and edge set {{(xi,yi), (x2,y2)}: {xi,x2} G E(X), or xi = x2 and {y1,y2} G E(Y)}. The deleted wreath (deleted lexicographic) product X ld Y of X by Y is the graph with vertex set V (X) x V(Y) and edge set {{(xi,yi), (x2,y2)}: {xi,X2} G E(X) and yi = y2, or xi = X2 and {yi,y2} G E(Y)}. If Y = Kb = bKi then the deleted lexicographic product X ld Y is denoted by X [Kb] - bX.
Let X = Cay(G, S) be a Cayley graph on a group G. Denote by Aut(G, S) the set of all automorphisms of G which fix S setwise, that is,
Aut(G, S) = {a G Aut(G)|SCT = S}.
It is easy to check that Aut(G, S) is a subgroup of Aut(X) and that it is contained in the stabilizer of the identity element id G G. Following Xu [25], X = Cay(G, S) is called a normal Cayley graph if GL is normal in Aut(X), that is, if Aut(G, S) coincides with the vertex stabilizer id G G. Moreover, if X is a normal Cayley graph, then Aut(X) = Gl x Aut(G, S) (see [11]).
Proposition 3.5. [12, 16] Let X be a connected arc-transitive circulant of order n. Then one of the following holds:
(i)	X = K„;
(ii)	X = Y [Kd], where n = md, m, d > 1 and Y is a connected arc-transitive circulant of order m;
(iii)	X = Y[Kd] — dY, where n = md, d > 3, gcd(d, m) = 1 and Y is a connected arc-transitive circulant of order m;
(iv)	X is a normal circulant.
The proof of the next proposition is straightforward.
Proposition 3.6. Complete graphs Kn and their complements Kn, n > 2, admit odd automorphisms.
Propositions 3.7, 3.8, 3.9, and 3.10 deal with the existence of odd automorphisms in the framework of (deleted) lexicographic products of graphs.
Proposition 3.7. Let Z be a graph admitting an odd automorphism. Then a lexicographic product Y [Z] of the graph Z by a graph Y admits odd automorphisms. In particular, Y[Kd], d > 1, admits odd automorphisms.
Proof. An odd automorphism is constructed by taking a map that acts trivially on all blocks (that is, copies of the graph Z) but one, where it acts as an odd automorphism of the graph Z. By Proposition 3.6, Kd admits an odd automorphism, so such a map exists when
Z = Kd.	□
Proposition 3.8. Let X be the deleted lexicographic product X = Y id Z of a graph Y by a graph Z, where Z has odd automorphisms and Y is of odd order. Then X admits odd automorphisms.
Proof. An odd automorphism is constructed by taking a map that acts as the same odd automorphism on each of the odd number of copies of the graph Z.	□
A. Hujdurovic et al.: Odd automorphisms in vertex-transitive graphs
433
Proposition 3.9. Let X be the deleted lexicographic product X = Y id Z of a graph Y by a graph Z, where Z is of odd order and Y has odd automorphisms. Then X admits odd automorphisms.
Proof. Let a' be an odd automorphism of Y. Let a : V (X) ^ V(X ) be defined with a((y, z)) = (a'(y), z). It is easy to see that a e Aut(X), and the fact that |V(Z)| is odd implies that a is an odd automorphism of X.	□
Propositions 3.8 and 3.9 combined together imply existence of odd automorphisms in arc-transitive circulants belonging to the family given in Proposition 3.5(iii).
Proposition 3.10. Let X be an arc-transitive circulant isomorphic to the deleted lexicographic product Y[dKi] — dY, where Y is an arc-transitive circulant of order coprime with d > 1. Then X has an odd automorphism.
Proof. Suppose first that Y is of odd order. Then, since, by Proposition 3.6, d,K1 admits odd automorphisms, the existence of odd automorphisms in Aut(X ) follows from Proposition 3.8. Suppose now that Y is of even order. Then any generator of a regular cyclic subgroup of Aut(Y) is an odd automorphism. Since in this case d is odd the existence of odd automorphisms in Aut(X) follows from Proposition 3.9.	□
Corollary 3.3 and Propositions 3.6, 3.7 and 3.10 combined together imply that even-closed arc-transitive circulants may only exist amongst normal arc-transitive circulants of order 1 (mod 4). In all other cases an arc-transitive circulant admits an odd automorphism.
Corollary 3.11. An even-closed arc-transitive circulant is normal and has order 1 (mod 4).
For the rest of this section we may, in our search for odd automorphisms, therefore restrict ourselves to normal circulants. Let X = Circ(n, S) be a normal arc-transitive circulant of order order 1 (mod 4) and let s e S. Then for any s' e S there must be an automorphism a of G such that a(s) = s', and so s and s' are of the same order. Thus if s is not of order n then Circ(n, S) is not connected. Hence it has at least three components (since n is not even), and has an automorphism that fixes all but one component while rotating that component, but this automorphism does not normalize the regular cyclic subgroup of Aut(X). This shows that we may assume that 1 e S (note that additive notation is used for Zn). This fact is used throughout this section.
The following lemma about the action of the multiplicative group of units is needed in this respect. For a positive integer n we use np to denote the highest power of p dividing n.
Lemma 3.12. Let p be an odd prime, and let k > 1 be a positive integer. Then Zp k, in its natural action on Zpk, admits an odd permutation if and only if k is odd.
Proof. By Proposition 2.1 it suffices to consider the Sylow 2-subgroup J of Z*pk. Since Z*k is a cyclic group, J is cyclic too. Let a be a generator of J. We claim that (a) acts semiregularly on Zpk \ {0}. Suppose on the contrary that this is not the case. Then there exist m e N such that am = 1 and am(x) = x for some x e Zpk \ {0}. This is equivalent to
(am — 1)x = 0 (mod pk).
434
Ars Math. Contemp. 10 (2016) 255-268
The above equation admits a non-trivial solution if and only if am - 1 is divisible by p. Suppose that j < k is such that pj || am - 1. There exists A e Z such that am = Apj + 1 and (A,p) = 1. Since am e J there exists s e N such that (am)2° = 1 (mod pk). It follows that (Apj + 1)2s = 1 (mod pk), and so
^ f2H (Apj )i = 0 (mod pk).
i=1 ^ % '
For each i > 1 the number (2i ) (Apj )i is divisible by pj+1. Consequently, 2sApj is divisible by pj+1, and so we conclude that p divides 2s A, a contradiction. As claimed above, this shows that a acts semiregularly on Zpk \ {0} with
P - 1 Pk - 1=(1+P + ... +pk"l)- P - 1
(pk — pk 1)2 p — 1 (pk — pk 1)2
cycles of even length (pk — pk-1)2 = (p — 1)2 in its cycle decomposition (since a is a generator of J). Since the parity of 1 + p + ... + pk-1 depends on whether k is even or odd, it follows that a is an odd permutation if and only if k is odd. The result follows. □
Corollary 3.13. Let p be an odd prime, and let k > 1 be a positive integer such that pk = 1 (mod 4). Then a normal arc-transitive circulant X = Cay(Zpk, S) admits an odd automorphism if and only if k is odd and S contains the Sylow 2-subgroup of Z*pk.
Proof. Recall that Aut(X) = Zpk x S, and thus X admits odd automorphisms if and only if S contains an element giving rise to an odd permutation on Zpk (generators of Sylow 2-subgroups of Z*pk are odd permutations on Zpk). The result is thus obtained by combining together Proposition 2.1 and Lemma 3.12.	□
Lemma 3.14. Let n = p2kl+1 • • • paka+1q2il ... q2'6 be a prime decomposition of an odd integer n, andletZn = P1 ©• • •©Pa©Q1 ©• • •©Qb, where Pi = Z^+i, i € {1,..., a}, and Qi = Z^^, i € {1,... ,b}. Further, let ai and fa, respectively, be generators of the Sylow 2-subgroup of P* and the Sylow 2-subgroup of Q*. Then, for each i, we have that ai is an odd permutation on Zn, and fa is an even permutation on Zn.
Proof. Observe that each cycle in the cycle decomposition of ai € Pi (considered as a permutation of Zp2^+i) is lifted to n/p2ki+1 cycles of the same length in the cycle decomposition of ai (when considered as a permutation of Zn). By Lemma 3.12, ai is an odd permutation on Zp2^+i for each i. Similarly, is an even permutation on Zq2^ for each i. Since n is odd, the result follows.	□
We introduce the fo a positive integer n, let
We introduce the following notation. Let n = p^ • • • pkaa be a prime decomposition of
Zn = ©Pi, where P, ^ Z
--11 i, where P i = Zpki
and let J(p,) be the Sylow 2-subgroup of P*. In the next theorem a necessary and sufficient condition for a normal circulant to be even-closed is given. One of the immediate consequences is, for example, that a normal circulant of order n2, n odd, is even-closed.
A. Hujdurovic et al.: Odd automorphisms in vertex-transitive graphs
435
Theorem 3.15. Let n = pk1 ■ ■ ■ p'ka be a prime decomposition of a positive integer n, and let X = Circ(n, S) be a normal arc-transitive circulant on Zn = ©a=1Pj. Then X is even-closed if and only if n = 1 (mod 4) and for every a = ©a=1 aj G S we have
± 6i(a) = 0 (mod 2), where 6+a) = { J Jp^ <*> and ki is odd .
i= l ^ '
Proof. By Corollary 3.3 for n = 1 (mod 4) the graph X admits odd automorphisms. We may therefore assume that n = 1 (mod 4). By Lemma 3.14, the existence of odd automorphisms in X depends solely on the parity of the exponents ki and the containment of the generators of the corresponding Sylow 2-subgroups in S, and the result follows. (Recall, that we are using the assumption that 1 G S and the fact that in a normal arc-transitive circulant, every element of S is conjugate, so every a g S is odd if and only if X has an odd automorphism.)	□
Combined together with Corollary 3.11 and Theorem 3.15 we have the following characterization of even-closed arc-transitive circulants.
Theorem 3.16. Let X be an even-closed arc-transitive circulant of order n and let n = Pi1 • • • Paa be a prime decomposition of n. Then X is a normal circulant X = Circ(n, S) on Zn = ®'a=1Pi, n = 1 (mod 4) and for every a = ®a=1ai G S we have
]T 0i(a) = 0 (mod 2), where 6(a) = { 1 ^¿^ and k is odd .
i= 1 ^ '
4 Vertex-transitive graphs
It is known that every finite transitive permutation group contains a fixed-point-free element of prime power order (see [9, Theorem 1]), but not necessarily a fixed-point-free element of prime order and, hence, a semiregular element (see for instance [3, 9]). In 1981 the third author asked if every vertex-transitive digraph with at least two vertices admits a semiregular automorphism (see [20, Problem 2.4]).
Despite considerable efforts by various mathematicians the problem remains open, with the class of vertex-transitive graphs having a solvable automorphism group being the main obstacle. The most recent result on the subject is due to Verret [24] who proved that every arc-transitive graph of valency 8 has a semiregular automorphism, which was the smallest open valency for arc-transitive graphs (see [7, 10, 23] and [15] for an overview of the status of this problem). While the existence of such automorphisms in certain vertex-transitive graphs has proved to be an important building block in obtaining at least partial solutions in many open problems in algebraic graph theory, such as for example the hamiltonicity problem (see [14, 2, 17]), the connection to the even/odd problem is straightforward.
Proposition 4.1. An even-closed vertex-transitive graph does not have even order semiregular automorphisms with an odd number of orbits.
This suggest that in a search for odd automorphisms a special attention should be given to semiregular automoprhisms of even order.
Furthermore, for those classes of vertex-transitive graphs for which a complete classification (together with the corresponding automorphism groups) exists, the answer to
436
Ars Math. Contemp. 10(2016)411-425
Problem 1.1 is, at least implicitly, available right there - in the classification. Such is, for example, the case of vertex-transitive graphs of order a product of two primes, see [6, 8, 21, 22, 18], and the case of vertex-transitive graphs which are graph truncations, see [1]. The hard work needed to complete these classifications suggest that the even/odd question is by no means an easy one. Let us consider, for example, the class of all vertex-transitive graphs of order 2p, p a prime. In the completion of the classification of these graphs, the classification of finite simple groups is an essential ingredient in handling the case of primitive automorphism groups. We know, by this classification, that the Petersen graph and its complement are the only such graphs with a primitive automorphism group. Of course, they both admit odd automorphisms. As for imprimitive automorphism groups, it all depends on the arithmetic of p. When p = 3 (mod 4), the graphs are necessarily Cayley graphs (of dihedral groups) and hence must admit odd automorphisms. (Namely, reflections interchanging the two orbits of the rotation in the dihedral group are odd automorphisms.) When p = 1 (mod 4), then it follows by the classification of these graphs [20] that there is an automorphism of order 2k, k > 1, interchanging the two blocks of imprimitivity of size p, having one orbit of size 2 and 2(p — 1)/2k orbits of size 2k, thus an odd number of orbits in total (since 2k divides p — 1). We have thus shown that every vertex-transitive graph of order twice a prime number admits an odd automorphism. However, no "classification of finite simple groups free" proof of the above fact is known to us.
In conclusion we would like to make the following comment with regards to cubic vertex-transitive graphs. Recall that the class of cubic vertex-transitive graphs decomposes into three subclasses depending on the number of orbits of the vertex-stabilizer on the set of neighbors of a vertex. These subclasses are arc-transitive graphs (one orbit), graphs with vertex-stabilizers being 2-groups (two orbits) andGRR graphs (three orbits), see [4]. (Note that there are two types of cubic GRR graphs, those with connecting set consisting of three involutions and those with connecting set consisting of an involution, a non-involution and its inverse, see [5].) For the first and third subclass the answer to Problem 1.1 is given in [13] and Proposition 3.1, respectively, while the problem is still open for the second subclass. Examples given in Section 1 (see also Figure 2) show, however, that this second subclass contains infinitely many even-closed graphs as well as infinitely many graphs admitting odd automorphisms.
Problem 4.2. Classify cubic vertex-transitive graphs with vertex-stabilizers being 2-groups that admit odd automorphisms.
References
[1]	B. Alspach and E. Dobson, On automorphism groups of graph truncations, Ars Math. Contemp. 8 (2015), 215-223.
[2]	K. K. and, and p. sparl, hamilton paths and cycles in vertex-transitive graphs of order 6p, Discrete Math 309 (2009), 5444-5460.
[3]	P. J. Cameron, M. Giudici, W. M. Kantor, G. A. Jones, M. H. Klin, D. M. sic and L. A. Nowitz, Transitive permutation groups without semiregular subgroups, J. London Math. Soc 66 (2002), 325-333.
[4]	P. P. cnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J. Symbolic Computation 50 (2013), 465-477.
A. Hujdurovic et al.: Odd automorphisms in vertex-transitive graphs
437
[5]	M. D. E. Conder and T. Pisanski, and a. Zitnik, Vertex-transitive graphs and their arc-types, arXiv:, http://arxiv.org/abs/150 5.02 02 9.
[6]	E. Dobson, Automorphism groups of metacirculant graphs of order a product of two distinct primes, Combin. Probab. Comput 15 (2006), 105-130.
[7]	E. Dobson, A. M. c, D. Marusic and L. A. Nowitz, Semiregular automorphisms of vertex-transitive graphs of certain valencies, J. Combin. Theory, Ser. B 97 (2007), 371-380.
[8]	E. Dobson and D. Witte, Transitive permutation groups of prime-squared degree, J. Algebraic Combin 16 (2002), 43-69.
[9]	B. Fein, W. M. Kantor and M. Schacher, Relative brauer groups ii, J. Reine Angew. Mat 328 (1981), 39-57.
[10]	M. Giudici and G. Verret, Semiregular automorphisms in arc-transitive graphs of valency 2p, in preparation.
[11]	C. D. Godsil, On the full automorphism group of a graph, Combin 1 (1981), 243-256.
[12]	I. Kovacs, Classifying arc-transitive circulants, J. Algebr. Combin 20 (2004), 353-358.
[13]	K. Kutnar and D. M. sics, Cubic symmetric graphs via odd automorphisms, manuscript.
[14]	K. Kutnar and D. M. sic, Hamiltonicity of vertex-transitive graphs of order 4p, European J. Combin 29 (2008), 423-438.
[15]	K. Kutnar and D. M. sic, Recent trends and future directions in vertex-transitive graphs, Ars Math. Contemp 1 (2008).
[16]	C. H. Li, Permutation groups with a cyclic regular subgroup and arc-transitive circulants, J. Algebr. Combin 21 (2005), 131-136.
[17]	L. Lovasz, Combinatorial structures and their applications, (proc, Calgary Internat. Conf., Calgary, Alberta 1969 (1970), 243-246.
[18]	C. E. Praeger and M. Y. Xu, Vertex-primitive graphs of order a product of two distinct primes, J. Combin. Theory, Ser. B 59 (1993), 245-266.
[19]	G. Sabidussi, On a class of fixed-point-free graphs, in: Proc. Amer. Math. Soc, 9, 1958 pp. 800-804.
[20]	D. M. sic, On vertex symmetric digraphs, Discrete Math 36 (1981), 69-81.
[21]	D. M. sic and R. Scapellato, Characterizing vertex-transitive pq-graphs with imprimitive automorphism subgroups, J. Graph Theory 16 (1992), 375-387.
[22]	D. M. sic and R. Scapellato, Classifying vertex-transitive graphs whose order is a product of two primes, Combinatorics 14 (1994), 187-201.
[23]	D. M. sic and R. Scapellato, Permutation groups, vertex-transitive digraphs and semiregular automorphisms, European J. Combin 19 (1998), 707-712.
[24]	G. Verret, Arc-transitive graphs of valency 8 have a semiregular automorphism, Ars Math. Contemp 8 (2015), 29-34.
[25]	M. Y. Xu, Automorphism groups and isomorphisms of cayley digraphs, Discrete Math 182 (1998), 309-320.