# On vertex-transitive non-Cayley graphs

N/A
N/A
Protected

Share "On vertex-transitive non-Cayley graphs"

Copied!
34
0
0

Full text

(1)

### On vertex-transitive non-Cayley graphs

Jin-Xin Zhou

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

SODO, Queenstown, 2012

(2)

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.

(3)

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.

(4)

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.

(5)

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.

(6)

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.

(7)

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.

(8)

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.

(9)

Interesting cases in classification

Cubic VNC-graphs.

Tetravalent VNC-graphs.

(10)

A well-known class of graphs Generalized Petersen graphs

Letn3 and 1t<n/2. Thegeneralized Petersen graphP(n,t)is the graph with vertex set{xi,yi|iZn}and edge set the union the out edges {{xi,xi+1} |iZn}, the inner edges{yi,yi+t |iZn}and the spokes {{xi,yi}, |iZn}.

P(8,3)

xa1

@

@ q x2 TT q

x0 PPax3 a

x7

PP @@qx4 qx6 TT

ax5

qy1

%

%

% ay2 e e e

ay6 e

e e qy5

%

%

% qy3 ay4 q

y7

ya0

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

(11)

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)(k2≡ −1(mod2p)).

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

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

P(p2,t)(t2≡ −1(modp2)).

(12)

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 C130,VN C230, P(pq,t), wheret2≡ −1(modpq), andAut(VN C130)∼=S5 andAut(VN C230)∼=A5.

(13)

Cubic VNC-graphs of order4times a prime power

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

(14)

A question

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

(15)

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

Letn3 andtZn− {0}. Thedouble generalized Petersen graph DP(n,t) (DGPG for short) is defined to have vertex set{xi,yi,ui,vi|iZn}and edge set the union of theout edges{{xi,xi+1},{yi,yi+1} |iZn}, theinner edges {{ui,vi+t},{vi,ui+t} |iZn}and thespokes{{xi,ui},{yi,vi} |iZn}.

(16)

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

7PP @@q4 q6

TT a5

q10

%

%

% a20 e e e

a60 e

e e q50

%

%

% q30 a40 7q0

0a0

(17)

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.

(18)

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 ofx2≡ −1(modp)inZ2p..

(19)

The second family Definition 1

For integern2, letX(n,2)be the graph of order 4nand valency 3 with vertex setV0V1. . .V2n−2V2n−1, whereVi={xi0,xi1}, and adjacencies x2ir x2i+1r (iZn,r Z2)andx2i+1r x2i+2s (iZn;r,sZ2).

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

(20)

The second family

The second family

LetEX(n,2)be the graph obtained fromX(n,2)by blowing up each vertexxir into two verticesxir,0andxir,1. The adjacencies are as the following:

x2ir,sx2i+1r,t andx2i+1r,s x2i+2s,r , whereiZnandr,s,tZ2(see Fig. 1 for EX(5,2)).

(21)

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

x00,0 x10,0 x20,0 x30,0 x40,0 x50,0 x60,0 x70,0 x80,0 x90,0 x01,1 x11,1 x21,1 x31,1 x41,1 x51,1 x61,1 x71,1 x81,1 x91,1 x01,0 x11,0 x21,0 x31,0 x41,0 x51,0 x61,0 x71,0 x81,0 x91,0

x00,1 x10,1 x20,1 x30,1 x40,1 x50,1 x60,1 x70,1 x80,1 x90,1

Figure:The graphEX(5,2)

(22)

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.

(23)

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).

(24)

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.

(25)

Tetravalent VNC-graphs

Tan (1996) constructed three families of tetravalent

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

(26)

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).

(27)

Tetravalent VNC-graphs of order4p

Example 1

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

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

Example 2

Letpbe a prime and letr ∈Zpsatisfyr4=−1. The graph VNC4p2 is defined to have vertex set{xij |i ∈Z4,j∈Zp}and edge set{{vij,vi+1j+ri},{vij,vi+1j−ri} |i∈Z4,j ∈Zp}.

(28)

Tetravalent VNC-graphs of order4p

Example 3

Letpbe a prime and letr ∈Zpsatisfyr4=−1. The graph VNC4p3 is defined to have vertex set{xij |i ∈Z4,j∈Zp}and edge set{{xi−1j ,xij},{x0j−1,x0j},{x1j,x1j+r},

{x2j,x2j+r2},{x3j,x3j+r3} |i ∈Z4,j∈Zp}.

Example 4

Letpbe a prime and lett∈Z2p satisfyt2=−1. The graph VNC4p4 is defined to have vertex set{xi,yi |i∈Z2p}and edge set{{xi,xi+1},{xi,xi+p},{xi,yi},{yi,yi+t},{yi,yi+p} |i ∈Z2p}.

(29)

Tetravalent VNC-graphs of order4p

Example 5

Letpbe a prime and lett∈Z2p satisfyt2=−1. The graph VNC4p5 is defined to have vertex set{xi,yi |i∈Z2p}and edge setE ={{xi,xi+2},{xi,xi+p},{xi,yi},

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

Example 6

LetG=A5be the alternating group of degree 5. Let H=h(1 2 3)i,d1= (1 4)(2 5)andd2= (1 2)(4 5). Then

Cos(G,H,Hd1H∪Hd2)is a connected tetravalent VNC-graph of order 20, denoted byVNC206 , andAut(VNC206 )∼=S5.

(30)

### Thanks!

(31)

H.-W. Cheng, A note on cubic symmetric graphs of order 2pn, 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 orderpk, Ann. Discrete Math. 27 (1985) 115–128.

(32)

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.

(33)

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 2p2(Chinese), Advance in Math. 37 (2008) 605–609.

(34)

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.

References

Related documents

The result has only one feasible (profitable) solution as shown in Figure 3. Figure 3: P-graph solution of the case study. To improve the approximation of the non-linear

36 Interpreting column &amp; dot plot graphs / Creating a column graph /.. Creating a dot plot graph

• An equivalence class of vertices in a directed graph under the equivalence relation of “in the same connected component” is the vertex set of a connected component!... To

(ii) a shift to the right by one position in the first occurrence of m in the product (the other

 For studying Cayley graphs we want to decide existence of regular subgroups maybe in primitive groups – but a graph has a 2-transitive automorphism group only if it is empty

There is a large body of work regarding the existence of Hamilton cycles in cubic graphs, in particular what combinations of graph-theoretical properties guarantee that a cubic

•  The ants move from vertex to vertex along the edges of the construction graph exploiting information provided by the pheromone values and incrementally building a solution..

For any even integer r ≥ 4, there exist infinitely many odd primes p such that there is a second-kind Frobenius graph (connected generalized Paley graph) of order p 2 and valency r

Cayely map: A Cayley map CM(G, X, σ) is a 2-cell embedding of the Cayley graph C(G, X) into an orientable surface with the same local rotation induced by the permutation σ at

There will be more vertex-transitive graphs, but essentially we may repeat the same line of arguments to compute the automorphisms. Instead of using full automorphims group we have

You should prove for yourself the vertex form of Menger’s Theorem for undirected graphs.. 8.2

For the remainder of this section we formally define the graph families k –Vertex Cover , where k is an upper bound on the vertex cover size, and what it means to characterize them by

By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, so it suﬃces to find all 4-valent arc-transitive graphs

Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type).. Once we have the graphs, we still have to do a

In such a case, we cannot use the transitive collapse, as the definition in Theorem 14 below shows. from the view of the universe) is non-standard (for interest, non-standard models

In practice: associate a graph to the combinatorial objects, apply canonical labeling to the graph, and only keep an augmented graph if the newly appended vertex gets smallest

Hence for every positive integer k, the group G 1 4 has a quotient G 1 4 /N k of order 336k 8 that is the automorphism group of a 4-regular cubic graph of order 14k 8

That makes Γ a Cayley graph C (G , S ), with inverse-closed connection set S Difficulty: Any group automorphism of G leaving the connection set S invariant induces an extra

Form appropriate 4 element generating sets and build corresponding Cayley graphs. Take only those graphs that are connected

More generally, G with large abelian factor group may have Cayley graphs with diameter proportional to |G|... The diameter

The abelian normal quotient method: look for a nontrivial, abelian, minimal normal subgroup N and consider quotients until you reach a semisimple group.. Note that if N is

A regular graph X of valency k and order v is called strongly regular graph (SRG) with parameters (v , k, λ, µ) if any two adjacent vertices have λ common vertices and any two

Frelih-Kutnar (2013): A cubic arc-transitive tetracirculant is one of 17 sporadic examples or in one of two infinite families.. Frelih-Kutnar (2013): A cubic