**On vertex-transitive non-Cayley graphs**

Jin-Xin Zhou

Mathematics, Beijing Jiaotong University Beijing 100044, P.R. China

SODO, Queenstown, 2012

**Definitions**

Vertex-transitive graph:A graph isvertex-transitiveif its automorphism group acts transitively on its vertices.

Cayley graphs:Given a finite groupGand an inverse closed subsetS⊆G\ {1}, theCayley graphCay(G,S)on Gwith respect toSis defined to have vertex setGand edge set{{g,sg} |g ∈G,s∈S}.

Every Cayley graph is vertex-transitive.

**Definitions**

It is well known that a vertex-transitive graph is a Cayley graph if and only if its automorphism group contains a subgroup acting regularly on its vertex set (see, for example, [17, Lemma 4]).

There are vertex-transitive graphs which are not Cayley graphs and the smallest one is the well-knownPetersen graph. Such a graph will be called avertex-transitive non-Cayley graph, or a VNC-graphfor short.

**Related problems**

Marušiˇc (1983) posed the following problem.

**Problem 1**

Determine the setNCof non-Cayley numbers, that is, those numbers for which there exists a VNC-graph of ordern.

To settle this question, a lot of VNC-graphs were constructed by Marušiˇc, McKay, Royle, Praeger, Miller, Seress etc. in 1990’s.

**Related problems**

Feng (2002) considered the following question.

**Problem 2**

Determine the smallest valency for VNC-graphs of a given order.

He solved this problem for the graphs of odd prime power order.

**Related problems**

In [11, Table 1], forn≤26, the total number of vertex-transitive graphs of ordernand the number of VNC-graphs of ordernare listed. It seems that, for small orders at least, the great majority of vertex-transitive graphs are Cayley graphs. This is

particularly true for small valent vertex-transitive graphs (see [14]). This may suggest the following problem.

**Problem 3**

Classify small valent VNC-graphs with given order.

The main purpose of this talk is to introduce some work about this problem.

**Strategy in classification**

LetX be a connected graph with a vertex-transitive automorphism groupG. LetBbe aG-invariant partition of V(X).

Quotient graphXB:vertex setB, and for any two vertices B,C ∈ B,B is adjacent toC if and only if there existu ∈B andv ∈Cwhich are adjacent inX.

Normal quotient:whenBis a set of orbits of some normal subgroup ofG.

**Strategy in classification**

The quotient theory was developed by Praeger etc., and it can be used to reduce a large vertex-transitive graph to a small one. This reduction enables us to analysis the structure of various families of vertex-transitive graphs.

This strategy also works in the classification of small valent VNC-graphs.

**Interesting cases in classification**

Cubic VNC-graphs.

Tetravalent VNC-graphs.

**A well-known class of graphs**
**Generalized Petersen graphs**

Letn≥3 and 1≤t<n/2. Thegeneralized Petersen graphP(n,t)is the
graph with vertex set{xi,yi|i∈Zn}and edge set the union the out edges
{{xi,xi+1} |i∈Z^{n}}, the inner edges{yi,yi+t |i∈Z^{n}}and the spokes
{{xi,yi}, |i∈Z^{n}}.

P(8,3)

xa^{}^{}_{1}

@

@ q
x_{2}
TT
q

x_{}_{0} P_{P}ax_{3}
a

x_{7}

PP ^{@}_{@}qx_{4}
qx_{6}
TT

ax_{5}

qy_{1}

%

%

%
ay_{2}
e
e
e

ay_{6}
e

e e qy5

%

%

% qy_{3}
ay_{4}
q

y7

ya_{0}

It is known thatP(n,t)is VNC if and only if eithert^{2}≡ −1(modn)or
(n,t) = (10,2).

**Cubic VNC-graphs of order a product of three primes**

**Theorem (****Zhou, J. Sys. Sci. & Math. Sci., 2008****)**

Letpbe a prime. A connected cubic graph of order 4pis a VNC-graph if and only if it is isomorphic to one of the following:

P(10,2), the Dodecahedron, the Coxeter graph, or
P(2p,k)(k^{2}≡ −1(mod2p)).

**Theorem (****Zhou, Adv. Math. (China), 2008****)**

Letpbe a prime. A connected cubic graph of order 2p^{2}is a
VNC-graph if and only if it is isomorphic to

P(p^{2},t)(t^{2}≡ −1(modp^{2})).

**Cubic VNC-graphs of order a product of three primes**

**Theorem (****Zhou & Feng, J. Graph Theory, 2010****)**
Letp>q be odd primes andX a connected cubic
vertex-transitive non-Cayley graph of order 2pq. Then

(1) X is symmetric if and only ifX ∼=F030,F102,F182C, F182D,F506A, orF2162;

(2) X is non-symmetric if and only ifX ∼=VN C^{1}_{30},VN C^{2}_{30},
P(pq,t), wheret^{2}≡ −1(modpq), andAut(VN C^{1}_{30})∼=S_{5}
andAut(VN C^{2}_{30})∼=A5.

**Cubic VNC-graphs of order**4**times a prime power**

**Theorem (****Kutnar, Maruši ˇc & Zhang, J. Graph Theory, 2012****)**
Every cubic VNC-graphs of order 4p^{2},p>7 a prime, is a
generalized Petersen graph.

**A question**

Are there infinite family of cubic VNC-graphs different from generalized Petersen graph?

**Two families of cubic vertex-transitive graphs**

We modify the generalized Petersen graph construction slightly so that the subgraph induced by the out edges is a union of two n-cycles.

**Double generalized Petersen graphs**

Letn≥3 andt∈Z^{n}− {0}. Thedouble generalized Petersen graph DP(n,t)
(DGPG for short) is defined to have vertex set{xi,yi,ui,vi|i∈Z^{n}}and edge
set the union of theout edges{{xi,xi+1},{yi,yi+1} |i∈Zn}, theinner edges
{{ui,vi+t},{vi,ui+t} |i∈Z^{n}}and thespokes{{xi,ui},{yi,vi} |i∈Z^{n}}.

**DP(10,2) and P(8,3)**

DP(10,2)

r r r r r r r r r r

b

r

b

r

b

r

b

r

b r

b HH

HHH r HH

HHH b HH

HHH r HH

HHH b HH

HHH r HH

HHH b HH

HHH r HH

HHH

b r

r r r r r r r r r r

y0 y1 y2 y3 y4 y5 y6 y7 y8 y9

x0 x1 x2 x3 x4 x5 x6 x7 x8 x9

u0 u1 u2 u3 u4 u5 u6 u7 u8 u9

v0 v1 v2 v3 v4 v5 v6 v7 v8 v9

P(8,3)

1a^{}^{}

@

@ q T2 T q

0_{} P_{P}a3
a

7PP ^{@}_{@}q4
q6

TT a5

q1^{0}

%

%

%
a2^{0}
e
e
e

a6^{0}
e

e
e
q5^{0}

%

%

% q3^{0}
a4^{0}
7q^{0}

0a^{0}

**An interesting problem**

**Problem**

Determining all vertex-transitive graphs and all VNC-graphs among DGPGs.

The complete solution of this problem may be a topic for our future effort. Here, we just give a sufficient condition for a DGPG being vertex-transitive non-Cayley.

**A sufficient condition**

**Sufficient condition**

Letpbe a prime such thatp≡1(mod4). ThenDP(2p, λ)is a
connected cubic VNC-graph of order 8p, whereλis a solution
ofx^{2}≡ −1(modp)inZ2p..

**The second family**
**Definition 1**

For integern≥2, letX(n,2)be the graph of order 4nand valency 3 with
vertex setV0∪V1∪. . .V2n−2∪V2n−1, whereVi={x_{i}^{0},x_{i}^{1}}, and adjacencies
x_{2i}^{r} ∼x_{2i+1}^{r} (i∈Z^{n},r ∈Z^{2})andx_{2i+1}^{r} ∼x_{2i+2}^{s} (i∈Z^{n};r,s∈Z^{2}).

**Remark**Note thatX(n,2)is obtained fromCn[2K1]by expending each
vertex into an edge, in a natural way, so that each of the two blown-up
endvertices inherits half of the neighbors of the original vertex.

r r r r r

r r r r r

@

@@

@

@@

@

@@

@

@@ XX XX XX XX X

C5[2K1] X(5,2)

r r@

@@r r@

@@r r@

@@r r@

@@r r

r r r r r r r r r r

**The second family**

**The second family**

LetEX(n,2)be the graph obtained fromX(n,2)by blowing up each vertexx_{i}^{r}
into two verticesx_{i}^{r,0}andx_{i}^{r,1}. The adjacencies are as the following:

x_{2i}^{r,s}∼x_{2i+1}^{r,t} andx_{2i+1}^{r,s} ∼x_{2i+2}^{s,r} , wherei∈Z^{n}andr,s,t∈Z^{2}(see Fig. 1 for
EX(5,2)).

**A picture of EX(5,2)**

r r r r r r r r r r

r

@

@

@

r r

@

@

@

r r

@

@

@

r r

@

@

@

r r

@

@

@ r

r r

@

@

@

r r

@

@

@

r r

@

@

@

r r

@

@

@

r r

r

@

@

@

r r

@

@

@

r r

@

@

@

r r

@

@

@

r r

@

@

@ r

x_{0}^{0,0} x_{1}^{0,0} x_{2}^{0,0} x_{3}^{0,0} x_{4}^{0,0} x_{5}^{0,0} x_{6}^{0,0} x_{7}^{0,0} x_{8}^{0,0} x_{9}^{0,0}
x_{0}^{1,1} x_{1}^{1,1} x_{2}^{1,1} x_{3}^{1,1} x_{4}^{1,1} x_{5}^{1,1} x_{6}^{1,1} x_{7}^{1,1} x_{8}^{1,1} x_{9}^{1,1}
x_{0}^{1,0} x_{1}^{1,0} x_{2}^{1,0} x_{3}^{1,0} x_{4}^{1,0} x_{5}^{1,0} x_{6}^{1,0} x_{7}^{1,0} x_{8}^{1,0} x_{9}^{1,0}

x_{0}^{0,1} x_{1}^{0,1} x_{2}^{0,1} x_{3}^{0,1} x_{4}^{0,1} x_{5}^{0,1} x_{6}^{0,1} x_{7}^{0,1} x_{8}^{0,1} x_{9}^{0,1}

**Figure:**The graphEX(5,2)

Dobson et al. (2007) showed thatEX(n,2)is vertex-transitive for eachn≥2. However,EX(n,2)is not necessarily a Cayley graph.

**Sufficient condition**

Letp>3 be a prime. Then the graphEX(p,2)is a connected cubic VNC-graph of order 8p.

**Cubic VNC-graphs of order**8p

Recently, we classified cubic VNC-graphs of order 8p.

**Theorem (Zhou & Feng, 2011, submitted to Elec. J. Combin.)**
A connected cubic graph of order 8pfor a primep is a
VNC-graph if and only if it is isomorphic toF56B,F56C,
DG(2p, λ)orEX(p,2).

**Cubic VNC-graphs of square-free order**

Li, Lu & Wang (2012) classified cubic vertex-transitive graphs of square-free order. From their result, one may pick out all cubic VNC-graphs of square-free order.

**Tetravalent VNC-graphs**

Tan (1996) constructed three families of tetravalent

vertex-transitive non-Cayley graphs which are metacirculant graphs.

**Tetravalent VNC-graphs of order**4p

Recently, we classified all tetravalent VNC-graphs of order 4p for each primep.

**Theorem (Zhou, to appear in J. Graph Theory)**

There are one sporadic and five infinite families of tetravalent VNC-graphs, of which the sporadic one has order 20, and one infinite family exists for every primep>3, two families exist if and only ifp≡1(mod8)and the other two families exist if and only ifp≡1(mod4). For each family there is a unique graph for a given order. (Examples 1-6).

**Tetravalent VNC-graphs of order**4p

**Example 1**

Letp>3 be a prime. The graphVNC_{4p}^{1} has vertex set
Zp×(Z2×Z2)and its edges are defined by

{(i,(x,y)),(i+1,(y,z))} ∈E(VNC_{4p}^{1} )for alli∈Zpand
x,y,z ∈Z2.

**Example 2**

Letpbe a prime and letr ∈Z^{∗}psatisfyr^{4}=−1. The graph
VNC_{4p}^{2} is defined to have vertex set{x_{i}^{j} |i ∈Z4,j∈Zp}and
edge set{{v_{i}^{j},v_{i+1}^{j+r}^{i}},{v_{i}^{j},v_{i+1}^{j−r}^{i}} |i∈Z4,j ∈Zp}.

**Tetravalent VNC-graphs of order**4p

**Example 3**

Letpbe a prime and letr ∈Z^{∗}psatisfyr^{4}=−1. The graph
VNC_{4p}^{3} is defined to have vertex set{x_{i}^{j} |i ∈Z4,j∈Zp}and
edge set{{x_{i−1}^{j} ,x_{i}^{j}},{x_{0}^{j−1},x_{0}^{j}},{x_{1}^{j},x_{1}^{j+r}},

{x_{2}^{j},x_{2}^{j+r}^{2}},{x_{3}^{j},x_{3}^{j+r}^{3}} |i ∈Z4,j∈Zp}.

**Example 4**

Letpbe a prime and lett∈Z^{∗}_{2p} satisfyt^{2}=−1. The graph
VNC_{4p}^{4} is defined to have vertex set{x_{i},y_{i} |i∈Z2p}and edge
set{{x_{i},x_{i+1}},{x_{i},x_{i+p}},{x_{i},y_{i}},{y_{i},y_{i+t}},{y_{i},y_{i+p}} |i ∈Z2p}.

**Tetravalent VNC-graphs of order**4p

**Example 5**

Letpbe a prime and lett∈Z^{∗}_{2p} satisfyt^{2}=−1. The graph
VNC_{4p}^{5} is defined to have vertex set{x_{i},y_{i} |i∈Z2p}and edge
setE ={{x_{i},x_{i+2}},{x_{i},x_{i+p}},{x_{i},y_{i}},

{y_{i},y_{i+2t}},{y_{i},y_{i+p}} |i∈Z2p}.

**Example 6**

LetG=A_{5}be the alternating group of degree 5. Let
H=h(1 2 3)i,d_{1}= (1 4)(2 5)andd_{2}= (1 2)(4 5). Then

Cos(G,H,Hd_{1}H∪Hd_{2})is a connected tetravalent VNC-graph of
order 20, denoted byVNC_{20}^{6} , andAut(VNC_{20}^{6} )∼=S_{5}.

### Thanks!

H.-W. Cheng, A note on cubic symmetric graphs of order 2p^{n},
Austral. J. Combin. (2010) to appear.

Y.-Q. Feng, On vertex-transitive graphs of odd prime-power order, Discrete Math. 248 (2002) 265–269.

Y.-Q. Feng, J.H. Kwak, Cubic symmetric graphs of order twice prime power, J. Austral. Math. Soc. 81 (2006) 153–164.

A. Hassani, M.A. Iranmanesh, C.E. Praeger, On

vertex-imprimitive graphs of order a product of three distinct odd primes, J. Combin. Math. Combin. Comput. 28 (1998) 187–213.

C.H. Li, A. Seress, On vertex-transitive non-Cayley graphs of square-free order, Designs, Codes and Cryptography 34 (2005) 265–281.

D. Marušiˇc, Cayley properties of vertex symmetric graphs, Ars Combin. 16B (1983) 297–302.

D. Marušiˇc, Vertex transitive graphs and digraphs of orderp^{k},
Ann. Discrete Math. 27 (1985) 115–128.

D. Marušiˇc, R. Scapellato, Characterizing vertex-transitive pq-graphs with an imprimitive automorphism subgroup, J. Graph Theory 16 (1992) 375–387.

D. Marušiˇc, R. Scapellato, Classifying vertex-transitive graphs whose order is a product of two primes, Combinatorica 14 (1994) 187–201.

D. Marušiˇc, R. Scapellato, B. Zgrabliˇc, On quasiprimitive pqr-graphs, Algebra Colloq. 2 (1995) 295–314.

B.D. McKay, C.E. Praeger, Vertex-transitive graphs which are not Cayley graphs I, J. Austral. Math. Soc. 56 (1994) 53–63.

B.D. McKay, C.E. Praeger, Vertex-transitive graphs which are not Cayley graphs II, J. Graph Theory 22 (1996) 321–334.

B.D. McKay, G.F. Royle, The transitive graphs with at most 26 vertices, Ars Combin. 30 (1990) 161–176.

B.D. McKay, G.F. Royle, Cubic transitive graphs, http://units.maths.uwa.edu.au

/gordon/remote/cubtrans/index.html.

A.A. Miller, C.E. Praeger, Non-Cayley vertex-transitive graphs of order twice the product of two odd primes, J. Algebraic Combin.

3 (1994) 77–111.

A. Seress, On vertex-transitive non-Cayley graphs of orderpqr, Discrete Math. 182 (1998) 279–292.

G. Sabidussi, On a class of fix-point-free graphs, Proc. Amer.

Math. Soc. 9 (1958) 800–804.

K. Kutnar, D. Marušiˇc, C. Zhang, On cubic non-Cayley vertex-transitive graphs, J. Graph Theory 69 (2012) 77–95.

J.-X. Zhou, Cubic vertex-transitive graphs of order 4p(Chinese), J. Sys. Sci. & Math. Sci. 28 (2008) 1245–1249.

J.-X. Zhou, Cubic vertex-transitive graphs of order 2p^{2}(Chinese),
Advance in Math. 37 (2008) 605–609.

J.-X. Zhou, Tetravalent vertex-transitive graphs of order 4p, J.

Graph Theory, 2011 DOI 10.1002/jgt.20653.

J.-X. Zhou, Y.-Q. Feng, Cubic vertex-transitive graphs of order 2pq, J. Graph Theory, 65 (2010) 285–302.

J.-X. Zhou, Y.-Q. Feng, Cubic vertex-transitive non-Cayley graphs of order 8p, (2011) submitted.