Pentavalent Symmetric Graphs of Order Twice a Prime Square

A classification of pentavalent symmetric graphs of order twice a prime square is given. It is proved that such a graph is a coset graph of Z3.A6 （non-split extension）, or a bi-coset graph of an extra-special group of order 125, or the standard double cover of a specific abelian Cayley digraph of order a prime square.

Pentavalent Symmetric Graphs of Order 16p

A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In this paper, a complete classification of connected pentavalent symmetric graphs of order 16p is given for each prime p. It follows from this result that a connected pentavalent symmetric graph of order 16p exists if and only if p = 2 or 31, and that up to isomorphism, there are three such graphs.

Pentavalent symmetric graphs of order 2p^3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p^3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p^3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p^3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p^3 are all regular covers of the dipole Dip5 with covering transposition groups of order p^3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.

A Note on Two-Generator 2-Group Covers of Cubic Symmetric Graphs of Order 2p

Let p be a prime.In this paper,a complete classification of edge-transitive N-covers of a cubic symmetric graph of order 2p is given for the case when N is a twogenerator 2-group whose derived subgroup is either isomorphic to Z_(2)^(3)or generated by at most two elements.As an application,it is shown that 11 is the smallest value of n for which there exist infinitely many cubic semisymmetric graphs with order of the form 2^(n)p.

Heptavalent Symmetric Graphs with Certain Conditions

A graph Γ is said to be symmetric if its automorphism group Aut(Γ)acts transitively on the arc set of Γ.We show that if Γ is a finite connected heptavalent symmetric graph with solvable stabilizer admitting a vertex-transitive non-abelian simple group G of automorphisms,then either G is normal in Aut(Γ),or Aut(Γ)contains a non-abelian simple normal subgroup T such that G≤T and(G,T)is explicitly given as one of 11 possible exceptional pairs of non-abelian simple groups.If G is arc-transitive,then G is always normal in Aut(Γ),and if G is regular on the vertices of Γ,then the number of possible exceptional pairs(G,T)is reduced to 5.

Heptavalent Symmetric Graphs of Order 16p

A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. We classify connected heptavalent symmetric graphs of order 16p for each prime p. As a result, there are two such sporadic graphs with p=3 and 7, and an infinite family of 1-regular normal Cayley graphs on the group Z23 × D2p with 7｜（p - 1）.

Normal edge-transitive Cayley graphs on a class of non-abelian groups

Let Г=Cay(G,S)be the Cayley graph of a group G with respect to its subset S.The graph is said to be normal edge-transitive if the normalizer of G in the automorphism group Aut(T)of F acts transitively on the edge set of ГIn this paper,we study the structure of normal edge-transitive Cayley graphs on a class of non-abelian groups with order 2p^(2)(p refers to an odd prime).The structure and automorphism groups of the non-abelian groups are first presented,and then the tetravalent normal edge-transitive Cayley graphs on such groups are investigated.Finally,the normal edge-transitive Cayley graphs on group G are characterized and classified.

Semisymmetric Cubic Graphs as Regular Covers of K_(3,3)

A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regularly on its arc-set. In this paper, we give the sufficient and necessary conditions for the existence of one-regular or semisymmetric Zn-Covers of K3,3. Also, an infinite family of semisymmetric Zn×Zn-covers of K3,3 are constructed.

On Symmetric Cayley Graphs of Valency Eleven

A Cayley graph Г=Cay(G,S)is said to be normal if G is normal in Aut Г.In this paper,we investigate the normality problem of the connected 11-valent symmetric Cayley graphs Г of finite nonabelian simple groups G,where the vertex stabilizer A_(u) is soluble for A=Aut Г and v∈∨Г.We prove that either Г is normal or G=A_(5),A_(10),A_(54),A_(274),A_(549) or A_(1099).Further,11-valent symmetric nonnormal Cayley graphs of As,A54 and A274 are constructed.This provides some more examples of nonnormal 11-valent symmetric Cayley graphs of finite nonabelian simple groups after the first graph of this kind(of valency 11)was constructed by Fang,Ma and Wang in 2011.

Normality of Tetravalent Cayley Graphs of Odd Prime-cube Order and Its Application

Let p be an odd prime. In this paper we prove that all tetravalent connected Cayley graphs of order p^3 are normal. As an application, a classification of tetravalent symmetric graphs of odd prime-cube order is given.

（G, s）-Transitive Graphs of Valency 7

Let X be a finite simple undirected graph and G an automorphism group of X. If G is transitive on s-arcs but not on （s ＋ 1）-arcs then X is called （G, s）-transitive. Let X be a connected （G, s）-transitive graph of a prime valency p, and Gv the vertex stabilizer of a vertex v E V（X） in G. For the case p = 3, the exact structure of Gv has been determined by Djokovid and Miller in [Regular groups of automorphisms of cubic graphs, J. Combin. Theory （Ser. B） 29 （1980） 195-230]. For the case p = 5, all the possibilities of Gv have been given by Guo and Feng in [A note on pentavalent s-transitive graphs, Discrete Math. 312 （2012） 2214-2216]. In this paper, we deal with the case p = 7 and determine the exact structure of the vertex stabilizer Gv.

Cubic one-regular graphs of order twice a square-free integer

A graph is one-regular if its automorphism group acts regularly on the set of its arcs. Let n be a square-free integer. In this paper, we show that a cubic one-regular graph of order 2n exists if and only if n = 3 t p 1 p 2···p s ? 13, where t ? 1, s ? 1 and p i ’s are distinct primes such that 3| (p i ? 1). For such an integer n, there are 2 s?1 non-isomorphic cubic one-regular graphs of order 2n, which are all Cayley graphs on the dihedral group of order 2n. As a result, no cubic one-regular graphs of order 4 times an odd square-free integer exist.

Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration

A graph is called a semi-regular graph if its automorphism group action onits ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficientcondition for an automorphism of the graph Γ to be an automorphism of a map with the underlyinggraph Γ is obtained. Using this result, all orientation-preserving automorphisms of maps onsurfaces (orientable and non-orientable) or just orientable surfaces with a given underlyingsemi-regular graph Γ are determined. Formulas for the numbers of non-equivalent embeddings of thiskind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, thenon-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable andgeneral surfaces are enumerated.

On Automorphisms of Distance-Regular Graph with Intersection Array{18,15,9;1,1,10}

Recently,Makhnev and Nirova found intersection arrays of distance-regular graphs withλ=2 and at most 4096 vertices.In the case of primitive graphs of diameter 3 withμ=1 there corresponding arrays are{18,15,9;1,1,10},{33,30,8;1,1,30}or{39,36,4;1,1,36}.In this work,possible orders and subgraphs of fixed points of the hypothetical distance-regular graph with intersection array{18,15,9;1,1,10}are studied.In particular,graph with intersection array{18,15,9;1,1,10}is not vertex symmetric.