On vertex-transitive non-Cayley graphs

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ⁿ}, the inner edges{yi,yi+t |i∈Zⁿ}and the spokes {{xi,yi}, |i∈Zⁿ}.

P(8,3)

xa₁

@

@ q x₂ TT q

x₀ P_Pax₃ a

x₇

PP ^@_@qx₄ qx₆ TT

ax₅

qy₁

%

%

% ay₂ e e e

ay₆ e

e e qy5

%

%

% qy₃ ay₄ q

y7

ya₀

It is known thatP(n,t)is VNC if and only if eithert²≡ −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²≡ −1(mod2p)).

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

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

P(p²,t)(t²≡ −1(modp²)).

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¹₃₀,VN C²₃₀, P(pq,t), wheret²≡ −1(modpq), andAut(VN C¹₃₀)∼=S₅ andAut(VN C²₃₀)∼=A5.

Cubic VNC-graphs of order4times a prime power

Theorem (Kutnar, Maruši ˇc & Zhang, J. Graph Theory, 2012) Every cubic VNC-graphs of order 4p²,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ⁿ− {0}. Thedouble generalized Petersen graph DP(n,t) (DGPG for short) is defined to have vertex set{xi,yi,ui,vi|i∈Zⁿ}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ⁿ}and thespokes{{xi,ui},{yi,vi} |i∈Zⁿ}.

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_Pa3 a

7PP ^@_@q4 q6

TT a5

q1⁰

%

%

% a2⁰ e e e

a6⁰ e

e e q5⁰

%

%

% q3⁰ a4⁰ 7q⁰

0a⁰

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²≡ −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⁰,x_i¹}, and adjacencies x_2i^r ∼x_2i+1^r (i∈Zⁿ,r ∈Z²)andx_2i+1^r ∼x_2i+2^s (i∈Zⁿ;r,s∈Z²).

RemarkNote 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,0andx_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ⁿandr,s,t∈Z²(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 x₁^0,0 x₂^0,0 x₃^0,0 x₄^0,0 x₅^0,0 x₆^0,0 x₇^0,0 x₈^0,0 x₉^0,0 x₀^1,1 x₁^1,1 x₂^1,1 x₃^1,1 x₄^1,1 x₅^1,1 x₆^1,1 x₇^1,1 x₈^1,1 x₉^1,1 x₀^1,0 x₁^1,0 x₂^1,0 x₃^1,0 x₄^1,0 x₅^1,0 x₆^1,0 x₇^1,0 x₈^1,0 x₉^1,0

x₀^0,1 x₁^0,1 x₂^0,1 x₃^0,1 x₄^0,1 x₅^0,1 x₆^0,1 x₇^0,1 x₈^0,1 x₉^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 order8p

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 order4p

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 order4p

Example 1

Letp>3 be a prime. The graphVNC_4p¹ has vertex set Zp×(Z2×Z2)and its edges are defined by

{(i,(x,y)),(i+1,(y,z))} ∈E(VNC_4p¹ )for alli∈Zpand x,y,z ∈Z2.

Example 2

Letpbe a prime and letr ∈Z^∗psatisfyr⁴=−1. The graph VNC_4p² is defined to have vertex set{x_i^j |i ∈Z4,j∈Zp}and edge set{{v_i^j,v_i+1^j+ri},{v_i^j,v_i+1^j−ri} |i∈Z4,j ∈Zp}.

Tetravalent VNC-graphs of order4p

Example 3

Letpbe a prime and letr ∈Z^∗psatisfyr⁴=−1. The graph VNC_4p³ is defined to have vertex set{x_i^j |i ∈Z4,j∈Zp}and edge set{{x_i−1^j ,x_i^j},{x₀^j−1,x₀^j},{x₁^j,x₁^j+r},

{x₂^j,x₂^j+r2},{x₃^j,x₃^j+r3} |i ∈Z4,j∈Zp}.

Example 4

Letpbe a prime and lett∈Z^∗_2p satisfyt²=−1. The graph VNC_4p⁴ 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 order4p

Example 5

Letpbe a prime and lett∈Z^∗_2p satisfyt²=−1. The graph VNC_4p⁵ 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₅be the alternating group of degree 5. Let H=h(1 2 3)i,d₁= (1 4)(2 5)andd₂= (1 2)(4 5). Then

Cos(G,H,Hd₁H∪Hd₂)is a connected tetravalent VNC-graph of order 20, denoted byVNC₂₀⁶ , andAut(VNC₂₀⁶ )∼=S₅.

Thanks!

H.-W. Cheng, A note on cubic symmetric graphs of order 2pⁿ, 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²(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.