Regular Cayley maps for finite abelian groups

A regular Cayley map for a finite group A is an orientable map whose orientation-preserving automorphism group G acts regularly on the directed edge set and has a subgroup isomorphic to A that acts regularly on the vertex set. This paper considers the problem of determining which abelian groups have regular Cayley maps. The analysis is purely algebraic, involving the structure of the canonical form for A. The case when A is normal in G involves the relationship between the rank of A and the exponent of the automorphism group of A, and the general case uses Ito's theorem to analyze the factorization G = AY, where Y is the (cyclic) stabilizer of a vertex. Supported in part by the N.Z. Marsden Fund (grant no. UOA0124).     

Bipancyclic properties of Cayley graphs generated by transpositions

Cycle is one of the most fundamental graph classes. For a given graph, it is interesting to find cycles of various lengths as subgraphs in the graph. The Cayley graph on the symmetric group has an important role for the study of Cayley graphs as interconnection networks. In this paper, we show that the Cayley graph generated by a transposition set is vertex-bipancyclic if and only if it is not the star graph. We also provide a necessary and sufficient condition for to be edge-bipancyclic.     

On Cayley graphs of rectangular groups

In this paper, we first give a characterization of Cayley graphs of rectangular groups. Then, vertex-transitivity of Cayley graphs of rectangular groups is considered. Further, it is shown that Cayley graphs Cay(S,C) which are automorphism-vertex-transitive, are in fact Cayley graphs of rectangular groups, if the subsemigroup generated by C is an orthodox semigroup. Finally, a characterization of vertex-transitive graphs which are Cayley graphs of finite semigroups is concluded.     

Pentavalent symmetric graphs admitting transitive non-abelian characteristically simple groups

Let $\Gamma$ be a graph and let $G$ be a group of automorphisms of $\Gamma$. The graph $\Gamma$ is called $G$-normal if $G$ is normal in the automorphism group of $\Gamma$. Let $T$ be a finite non-abelian simple group and let $G=T^l$ with $l\ge 1$. In this paper we prove that if every connected pentavalent symmetric $T$-vertex-transitive graph is $T$-normal, then every connected pentavalent symmetric $G$-vertex-transitive graph is $G$-normal. This result, among others, implies that every connected pentavalent symmetric $G$-vertex-transitive graph is $G$-normal except $T$ is one of 57 simple groups. Furthermore, every connected pentavalent symmetric $G$-regular graph is $G$-normal except $T$ is one of 20 simple groups, and every connected pentavalent $G$-symmetric graph is $G$-normal except $T$ is one of 17 simple groups.     

Orthogonal double covers of Cayley graphs

Let X and G be graphs, such that G is isomorphic to a subgraph of X.An orthogonal double cover (ODC) of X by G is a collection of subgraphs of X, all isomorphic with G, such that (i) every edge of X occurs in exactly two members of and (ii) and share an edge if and only if x and y are adjacent in X. The main question is: given the pair (X,G), is there an ODC of X by G? An obvious necessary condition is that X is regular.A technique to construct ODCs for Cayley graphs is introduced. It is shown that for all (X,G) where X is a 3-regular Cayley graph on an abelian group there is an ODC, a few well known exceptions apart.     

Subgroup regular sets in Cayley graphs

Let Γ be a graph with vertex set V, and let a and b be nonnegative integers. A subset C of V is called an $(a,b)$-regular set in Γ if every vertex in C has exactly a neighbors in C and every vertex in $V?C$ has exactly b neighbors in C. In particular, $(0,1)$-regular sets and $(1,1)$-regular sets in Γ are called perfect codes and total perfect codes in Γ, respectively. A subset C of a group G is said to be an $(a,b)$-regular set of G if there exists a Cayley graph of G which admits C as an $(a,b)$-regular set. In this paper we prove that, for any generalized dihedral group G or any group G of order 4p or pq for some primes p and q, if a nontrivial subgroup H of G is a $(0,1)$-regular set of G, then it must also be an $(a,b)$-regular set of G for any $0?a?|H|?1$ and $0?b?|H|$ such that a is even when $|H|$ is odd. A similar result involving $(1,1)$-regular sets of such groups is also obtained in the paper.     

On distance-regular Cayley graphs of generalized dicyclic groups

Let G be a generalized dicyclic group with identity 1. An inverse closed subset S of $G?\{1\}$ is called minimal if $〈S〉=G$ and there exists some $s\in S$ such that $〈S?\{s,s^{?1}\}〉\ne G$. In this paper, we characterize distance-regular Cayley graphs $\mathrm{Cay}(G,S)$ of G under the condition that S is minimal.     

Normal Cayley graphs of finite groups

LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ◃A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG≅ℤ₄×ℤ₂ orG≅Q ₈×ℤ ₂ ^r (r⩾0) and that every finite group has a normal Cayley digraph, where Z_m is the cyclic group of orderm and Q₈ is the quaternion group of order 8. Project supported by the National Natural Science Foundation of China (Grant No. 10231060) and the Doctorial Program Foundation of Institutions of Higher Education of China.     

Bubble-sort图和Modified Bubble-sort图的自同构群

Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群.     

On locally primitive Cayley graphs of finite simple groups

In this paper we investigate locally primitive Cayley graphs of finite nonabelian simple groups. First, we prove that, for any valency d for which the Weiss conjecture holds (for example, d?20 or d is a prime number by Conder, Li and Praeger (2000) [1]), there exists a finite list of groups such that if G is a finite nonabelian simple group not in this list, then every locally primitive Cayley graph of valency d on G is normal. Next we construct an infinite family of p-valent non-normal locally primitive Cayley graph of the alternating group for all prime p?5. Finally, we consider locally primitive Cayley graphs of finite simple groups with valency 5 and determine all possible candidates of finite nonabelian simple groups G such that the Cayley graph Cay(G,S) might be non-normal.     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two suffcient and necessary conditions for such graphs to be 1- or 2-arc-regular are given and based on the conditions, several infinite families of 1-or 2-arc-regular cubic Cayley graphs of alternating groups are constructed.     

Edge-primitive Cayley graphs on abelian groups and dihedral groups

A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In 1973, Weiss (1973) determined all edge-primitive graphs of valency three, and recently Guo et al. (2013,2015) classified edge-primitive graphs of valencies four and five. In this paper, we determine all edge-primitive Cayley graphs on abelian groups and dihedral groups.     

A note on the automorphism groups of cubic Cayley graphs of finite simple groups

For a finite group G, a Cayley graph on G is said to be normal if . In this note, we prove that connected cubic non-symmetric Cayley graphs of the ten finite non-abelian simple groups G in the list of non-normal candidates given in [X.G. Fang, C.H. Li, J. Wang, M.Y. Xu, On cubic Cayley graphs of finite simple groups, Discrete Math. 244 (2002) 67-75] are normal.     

A class of Hamiltonian and edge symmetric Cayley graphs on symmetric groups

Abstract. Let Sn be the symmetric group