J.
Indones.
Math.
Soc.
Vol.
No.
, pp.
xxAexx.
EDGE TRANSITIVE DIHEDRAL COVERS OF THE
HEAWOOD GRAPH
Mehdi Alaeiyan1 .
Laleh Pourmokhtar2 Department of Mathematics.
Iran University of Science and Technology.
Narmak.
Tehran 16844, alaeiyan@iust.
laleh pourmokhtar@iust.
Abstract.
A graph is called edge-transitive if its automorphism group acts transitively on its edge set and a regular cover of a connected graph is called dihedral if its transformation group is dihedral.
In this paper, the authors classify all dihedral coverings of the Heawood graph whose fibre-preserving automorphism subgroups act edge-transitively.
Key words and Phrases: regular covering, edge-transitive graphs, the Heawood Abstrak.
Suatu graf disebut transitif sisi jika grup automorfisma graf tersebut beraksi secara transitif pada himpunan sisinya.
Suatu regular cover dari graf terhubung disebut dihedral jika grup transformasinya adalah dihedral.
Dalam paper ini, penulis mengklasifikasikan semua dihedral covering dari graf Heawood yang subgrup automorfisma fibre-preserving-nya beraksi secara transitif sisi.
Kata kunci: regular covering, graf transitif sisi, graf Heawood
INTRODUCTION
Throughout this paper, we consider finite connected graphs without loops or multiple edges.
For a graph X, each edge X gives rise to a pair of opposite arcs and we denote by V (X).
E(X).
A(X) and Aut(X) the vertex set, the edge set, the arc set and the full automorphism group of X, respectively.
The neighbourhood of a vertex v OO V (X), denoted by N .
, is the set of vertices adjacent to v in X.
Let a group G act on a set E, and let OO E.
We denote by G the stabilizer of in G, that is the subgroup of G fixing .
The group G is said to be semiregular if 2000 Mathematics Subject Classification: 05C25, 20B25.
Received: 13-12-2015, revised: 17-02-2018, accepted: 17-02-2018.
Mehdi Alaeiyan and Laleh Pourmokhtar G = 1 for each OO E, and regular if G is semiregular and transitive on E.
Let N be a subgroup of Aut(X) such that N is intransitive on V (X).
The quotient graph X/N induced by N is defined as the graph for which the set of N -orbits in V (X) is the vertex set of X/N and B.
C OO are adjacent if and only if there exists u OO B and v OO C such that uv OO E(X).
e is called a covering of a graph X with a projection A : X e Ie X.
A graph X if A is a surjection from V (X) to V (X) such that A|NXf.
E) : NXe .
E) Ie NX .
is e is called the a bijection for any vertex v OO V (X) and vE OO AOe1 .
The graph X covering graph and X is the base graph.
A covering X of X with a projection A is said to be regular .
r K- coverin.
if there is a semiregular subgroup K of the e such that the graph X is isomorphic to the quotient automorphism group Aut(X) e Ie X/K graph X/K, say by h, and the quotient map X is the composition Ah of A and h ( for the purpose of this paper, all functions are composed from left e is called a cyclic, to righ.
If K is cyclic, elementary abelian or dihedral, then X elementary abelian or dihedral covering of X, and if X is connected.
K becomes the covering transformation group.
The fibre of an edge or a vertex is its preimage e is said to be fibre-preserving if it maps a fibre to a under A.
An automorphism of X fibre, while every covering transformation maps each fibre on to itself.
All of such fibre-preserving automorphisms form a group called fibre-preserving group.
An s-arc in a graph X is an ordered .
-tuple .
0 , v1 , .
, vs ) of vertices of X such that viOe1 is adjacent to vi for 1 O i O s, and viOe1 6= vi 1 for 1 O i < s.
in other words, it is a directed walk of length s which never includes a backtracking.
A graph X is said to be s-arc-transitive if Aut(X) acts transitively on the set of s-arcs in X.
In particular, 0-arc-transitive means vertex-transitive, and 1arc-transitive means arc-transitive or symmetric.
An s-arc-transitive graph is said to be s-transitive if it is not .
-arc-transitive.
A symmetric graph X is said to be s-regular if for any two s-arcs in X, there is a unique automorphism of X mapping one to the other.
In other words, the automorphism group Aut(X) acts freely and transitively .
on the set of s-arcs in X.
A subgroup of the automorphism group of a graph X is said to be s-regular if it acts regularly on the set of s-arcs of X.
Regular coverings of a graph have received considerable attention.
For example, for a graph X which is the complete graph K4 , the complete bipartite graph K3,3 , hypercube Q3 or Petersen graph O3 , the s-regular cyclic or elementary abelian coverings of X, whose fibre-preserving groups are arc-transitive, classified for each 1 s 5 in .
, 6, 7, 8, .
As an application of these classifications, all s-regular cubic graphs of order 4p, 4p2 , 6p, 6p2 , 8p, 8p2 , 10p and 10p2 constructed for each 1 s 5 and each prime p in .
, 5, 6, .
In .
, it was shown that all cubic graphs admitting a solvable edge-transitive group of automorphisms arise as regular covers of one of the following basic graphs: the complete graph K4 , the dipole Dip3 with two vertices and three parallel edges, the complete bipartite graph K3,3 , the Pappus graph of order 18, and the Gray graph of order 54.
In this paper all dihedral coverings of the Heawood graph, whose fibre- preserving automorphism Edge transitive dihedral covers of the heawood graph subgroups act arc-transitively are determined.
PRELIMINARIES
We start with some notational conventions used throughout this paper.
Let n be a positive integer.
Denote by ZOn the multiplicative group consisting of numbers coprime to n.
For two groups M and N .
N o M denotes a semidirect product of N by M .
For an abelian group H, the generalized dihedral group Dih(H) is the semidirect product H o Z2 , where the unique involution in Z2 maps each element of H to its inverse.
In particular.
Dih(Zn ) is the dihedral group D2n of order 2n.
For a subgroup H of a group G, denote by CG (H) the centralizer of H in G and by NG (H) the normalizer of H in G.
It is easy to see that CG (H) is normal in NG (H).
Proposition 2.
The quotient group NG (H)/CG (H) is isomorphic to a subgroup of the automorphism group Aut(H) of H.
Let X be a cubic graph and let G Aut(X) act transitively on the edges of X.
Let N be a normal subgroup of G.
The quotient graph XN of X relative to N is defined as the graph with vertices the orbits of N in V (X) and with two orbits adjacent if there is an edge in X between the vertices lying in those two Below we introduce two propositions, of which the first is a special case of .
Theorem .
Proposition 2.
Let X be a cubic graph and let G Aut(X) be transitive on E(X) and V (X).
Then G is an s-arc-regular subgroup of Aut(X) for some integer If N G has more than two orbits in V (X), then N is semiregular on V (X).
XN is a cubic symmetric graph with G/N as an s-arc-regular group of automorphisms, and X is an N -cover of XN .
Given a finite group G and an inverse closed subset S OI G Oe .
, the Cayley graph Cay(G.
S) on G relative to S is defined to have vertex set G and edge set {.
, s.
| g OO G, s OO S}.
It is known that Cay(G.
S) is connected if and only if S generates G.
Given g OO G, define the permutation R.
on G by x 7OeIe xg, x OO G.
Then R(G) = {R.
OO G}, called the right regular representation of G, is a permutation group isomorphic to G, which acts regularly on G.
Thus the Cayley graph Cay(G.
S) is vertex-transitive.
A Cayley graph Cay(G.
S) is said to be normal if R(G) is normal in Aut(Cay(G.
S)).
It is easy to see that the group Aut(G.
S) = .
OO Aut(G)|Sa = S} is a sub group of Aut(Cay(G.
S))1 , the stabilizer of the vertex 1 in Aut(Cay(G.
S)).
Godsil .
Corollary 2.
proved the following proposition .
ee also Xu .
Proposition 1.
Proposition 2.
Cay(G.
S) is normal if and only if Aut(Cay(G.
S))1 = Aut(G.
S).
Mehdi Alaeiyan and Laleh Pourmokhtar Let m and k be positive integers.
Let Dih(Zmk y Zm ) = ha, b, c a2 = bmk = cm = 1, aba = bOe1 , aca = cOe1 , bc = cbi.
Assume that = 0 for k = 1 and 2 1 O 0 .
for k > 1.
Define DC.
, k, ) = Cay(Dih(Zmk y Zm ), a, ab, abOe .
By .
Theorem .
, .
, we have the following proposition.
Proposition 2.
Let k > 1 be an odd integer and m a positive integer.
Then every connected cubic symmetric Cayley graph on Dih(Zmk y Zm ) is isomorphic to some DC.
, k, ).
Furthermore, .
DC.
, 1, .
is the 3-arc-regular Pappus graph.
DC.
, 7, .
= DC.
, 7, .
is the 4-arc-regular Heawood graph.
DC.
, 1, .
and DC.
, 3, .
> .
are 2-arc-regular and normal.
If k > 3 and .
, .
6= .
, .
, then the graphs DC.
, k, ) are normal and 1-arc-regular, and for any two distinct values 1 and 2 satisfying the equation x2 x 1 = 0 in Zk .
DC.
, k, 1 ) O = DC.
, k, 2 ) if and only if 1 2 O 1 .
od Proposition 2.
Let n > 3 be an integer.
Then there exists a solution OO Zn of the equation x2 x 1 = 0 if and only if n = 3t pk1 1 .
pks , where t 1, s 1 and pi s are distinct primes such that pi O 1 .
Furthermore, if Equation .
has a solution in Zn , then it has exactly 2s solutions.
Let p be a prime congruent to 1 modulo 3.
By Proposition 2.
Equation .
has exactly two solutions in Zp which are just the two elements of ZOp of order 3.
Combining this fact with Proposition 2.
4, we know that DC.
, p, ) is independent of the choice of .
Thus, we shall denote this graph by DC2p .
Dihedral covers of the Heawood graph In .
Feng and Kwak classified all dihedral covers of K4 , whose fiber preserving groups are edge-transitive.
The main purpose of this section is to generalize this result to the Heawood graph.
We first prove the following lemmas.
Lemma 3.
Let X be a connected cubic graph, and let H Aut(X) be abelian and act semiregularly on V (X).
If H has two orbits each of which contains no edges of X, then X is isomorphic to a Cayley graph on Dih(H).
Edge transitive dihedral covers of the heawood graph Proof Let 4 = .
| h OO H} and 4A = .
| h OO H} be the two orbits of H in V (X).
One may assume that the actions of H on 4 and 4A are just by right multiplication, that is, 4.
g = 4.
and 4A.
g = 4A.
for any h, g OO H.
By assumption, there are no edges in 4 and 4A, implying that X is bipartite.
Let the neighbors of 4.
be 4A.
1 ), 4A.
2 ) and 4A.
3 ), where h1 , h2 , h3 OO H.
Since H is abelian, for any h OO H, the neighbors of 4.
are 4A.
h1 ), 4A.
h2 ) Oe1 Oe1 and 4A.
h3 ), and the neighbors of 4A.
hOe1 1 ), 4.
h2 ) and 4.
h3 ).
Oe1 is easy to see that the map defined by 4.
7OeIe 4A.
), 4A.
7OeIe 4.
Oe1 ) for any h OO H, is an automorphism of X of order 2.
For any hA, h OO H, one has Oe1 Oe1 4.
A)h = 4.
AhOe1 ) = 4.
A)h and 4A.
A)h = 4A.
AhOe1 ) = 4A.
A)h , implying that h = hOe1 .
It follows that hH, i O = Dih(H) acts regularly on V (X), and hence X is isomorphic to a Cayley graph on Dih(H).
Lemma 3.
Let G Aut(DC14 ) act edge-transitively on DC14 .
Then G contains a subgroup acting regularly on the edges .
ot arc.
of DC14 .
Proof We know that DC14 is the Heawood graph with automorphism group P GL.
, .
Since G is edge-transitive on DC14 .
G O = Z7 .
Z3 .
P SL.
, .
or P GL.
, .
Thus.
G has a subgroup N O = Z7 o Z3 acting regularly on the edges of DC14 .
By Propositions 2.
4, 2.
5 it is easy to see that the graph DC.
, p, ) is independent of the choice of .
For the convenience of statement, we denote this graph by DC8p .
The main purpose of this paper is to prove the following theorem.
Theorem 3.
Let X be the Heawood graph.
Let n > 1 be an integer.
Then XE is a connected edge-transitive D2n -cover of X if and only if is isomorphic to DC56 .
Proof First, we show the sufficiency.
By Equation .
DC56 = Cay(G, .
, ab,abOe .
), where G = ha, b, c a2 = b14 = c2 = 1, aba = bOe1 , ac = ca, bc = cbi and 2 1 O 0 .
From Proposition 2.
4, it follows that R(G)Aut(DC.
It is easy to see that N = hR.
p ).
i O = D4 is the maximal normal 2-subgroup of R(G).
So.
N is characteristic in R(G) and hence it is normal in Aut(DC56 ).
Clearly.
N has more than two orbits in V (DC56 ).
By Proposition 2.
2, the quotient graph (DC56 )N of DC56 relative to N is a cubic symmetric graph of order 14, and DC56 is an N -cover of (DC56 )N .
We know (DC56 )N is a cubic symmetric graph of order 14 and by .
, (DC56 )N O = DC14 .
We note that.
DC14 is the Heawood graph .
he only cubic symmetric graph of order .
Thus.
DC56 is a D4 -cover of DC14 .
For the necessity, let XE be a connected edge-transitive D2n -cover of the Heawood graph and n > 1 an integer.
Let K = D2n and let F be the fibre-preserving Then K F .
Since F is edge-transitive on XE.
F/K is an edge-transitive group of automorphisms of X.
Assume n = 2.
Then K O = D4 .
By Lemma 3.
F/K contains a subgroup
M/K(O
= Z7 o Z3 ) acting regularly on the edges of X.
Let C = CM (K).
Then K C and by Proposition 2.
M/CAut(K) O = GL.
, .
Since M/K O = Z7 o Z3 , one has 7 | |C/K|.
Let N/K M/K such that N/K O = Z7 .
Then N/K is the normal Sylow 7-subgroup of M/K.
Since 7 | |C/K|, it follows that N/K C/K.
Mehdi Alaeiyan and Laleh Pourmokhtar and hence N O = Z14 y Z2 .
Clearly.
N acts semiregularly on V (XE) with two orbits.
Since M is edge-transitive on XE, the normality of N in M implies that each orbit of N contains no edges of XE.
By Lemma 3.
X is isomorphic to a Cayley graph on Dih(Z14 y Z2 ), and by Proposition 2.
XE O
= DC.
, 7, ) = DC56 .
Assume n > 2.
Recall that K = D2n .
Let N be the cyclic subgroup of K of order n.
Since n > 2.
N is characteristic in K.
Then N F because K F .
By Proposition 2.
2, the quotient graph XN of XE relative to N is a connected cubic edge-transitive graph of order 28 with F/N as an edge-transitive group of automorphisms.
By .
, every connected cubic edge-transitive graph of order 28 is also arc-transitive.
Then.
XN is the 3-arc-regular Coxeter graph of order 28, which is non-bipartite by .
It follows that F/N is also arc-transitive one XN .
Since Aut(XuN ) O = P GL.
, .
, one has F/N O = P SL.
, .
or P GL.
, .
However, since K F .
K/N O = Z2 is a normal subgroup of F/N , a contradiction.
REFERENCES