One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

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.     

On the extendability of Bi-Cayley graphs of finite abelian groups

Let G be a finite group and A a nonempty subset (possibly containing the identity element) of G. The Bi-Cayley graph X=BC(G,A) of G with respect to A is defined as the bipartite graph with vertex set G×{0,1} and edge set {{(g,0),(sg,1)}∣g∈G,s∈A}. A graph Γ admitting a perfect matching is called n-extendable if ∣V(Γ)∣≥2n+2 and every matching of size n in Γ can be extended to a perfect matching of Γ. In this paper, the extendability of Bi-Cayley graphs of finite abelian groups is explored. In particular, 2-extendable and 3-extendable Bi-Cayley graphs of finite abelian groups are characterized.     

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.     

Shifts in Cayley graphs

An automorphism of an undirected simple graph is called a shift if it maps every vertex to an adjacent one. For all finite groups G, we determine the minimum nonzero valency of a Cayley graph on G that does not admit a shift. We also get a classification of groups with all involutions central and such that for every pair a,b of elements of the group, one of ab=ba, aba⁻¹=b⁻¹, bab⁻¹=a⁻¹ or a²=b^±2 holds.     

Hamiltonian decomposition of Cayley graphs of ordersp 2 andpq

In this paper, it is proved that any connected Cayley graph on an abelian group of order pq orp ² has a hamiltonian decomposition, wherep andq are odd primes. This result answers partially a conjecture of Alspach concerning hamiltonian decomposition of 2k-regular connected Cayley graphs on abelian groups.     

On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

Isomorphisms of Cayley graphs of a free Abelian group

A group G is called a CI-group provided that the existence of some automorphism σ ∈ Aut(G) such that σ(A) = B follows from an isomorphism Cay(G, A) ? = Cay (G, B) between Cayley graphs, where A and B are two systems of generators for G. We prove that every finitely generated abelian group is a CI-group.     

The Cayley graphs of ℤ<Superscript>d</Superscript> and the limits of vertex-primitive graphs of <Emphasis Type="Italic">HA</Emphasis>-type

We study the limits of the finite graphs that admit some vertex-primitive group of automorphisms with a regular abelian normal subgroup. It was shown in [1] that these limits are Cayley graphs of the groups ?^d. In this article we prove that for each d > 1 the set of Cayley graphs of ?^d presenting the limits of finite graphs with vertex-primitive and edge-transitive groups of automorphisms is countable (in fact, we explicitly give countable subsets of these limit graphs). In addition, for d < 4 we list all Cayley graphs of ?^d that are limits of minimal vertex-primitive graphs. The proofs rely on a connection of the automorphism groups of Cayley graphs of ?^d with crystallographic groups.     

Strongly Regular Semi-Cayley Graphs

We consider strongly regular graphs = (V, E) on an even number, say 2n, of vertices which admit an automorphism group G of order n which has two orbits on V. Such graphs will be called strongly regular semi-Cayley graphs. For instance, the Petersen graph, the Hoffman–Singleton graph, and the triangular graphs T(q) with q 5 mod 8 provide examples which cannot be obtained as Cayley graphs. We give a representation of strongly regular semi-Cayley graphs in terms of suitable triples of elements in the group ring Z G. By applying characters of G, this approach allows us to obtain interesting nonexistence results if G is Abelian, in particular, if G is cyclic. For instance, if G is cyclic and n is odd, then all examples must have parameters of the form 2n = 4s ² + 4s + 2, k = 2s ² + s, = s ² – 1, and = s ²; examples are known only for s = 1, 2, and 4 (together with a noncyclic example for s = 3). We also apply our results to obtain new conditions for the existence of strongly regular Cayley graphs on an even number of vertices when the underlying group H has an Abelian normal subgroup of index 2. In particular, we show the nonexistence of nontrivial strongly regular Cayley graphs over dihedral and generalized quaternion groups, as well as over two series of non-Abelian 2-groups. Up to now these have been the only general nonexistence results for strongly regular Cayley graphs over non-Abelian groups; only the first of these cases was previously known.     

Cayley digraphs with normal adjacency matrices

In this paper we give a criterion for the adjacency matrix of a Cayley digraph to be normal in terms of the Cayley subset S. It is shown with the use of this result that the adjacency matrix of every Cayley digraph on a finite group G is normal iff G is either abelian or has the form for some non-negative integer n, where Q₈ is the quaternion group and is the abelian group of order 2ⁿ and exponent 2.     

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 Family of Nonnormal Cayley Digraphs

We call a Cayley digraph Γ = Cay(G, S) normal for G if G _R , the right regular representation of G, is a normal subgroup of the full automorphism group Aut(Γ) of Γ. In this paper we determine the normality of Cayley digraphs of valency 2 on nonabelian groups of order 2p ² (p odd prime). As a result, a family of nonnormal Cayley digraphs is found. Received February 23, 1998, Revised September 25, 1998, Accepted October 27, 1998     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

On finite groups with the cayley isomorphism property

Let G be a finite group, and let Cay(G, S) be a Cayley digraph of G. If, for all T ⊂ G, Cay(G, S) ≅ Cay(G, T) implies S^α = T for some α ∈ Aut(G), then Cay(G, S) is called a CI-graph of G. For a group G, if all Cayley digraphs of valency m are CI-graphs, then G is said to have the m-DCI property; if all Cayley graphs of valency m are CI-graphs, then G is said to have the m-CI property. It is shown that every finite group of order greater than 2 has a nontrivial CI-graph, and all finite groups with the m-CI property and with the m-DCI property are characterized for small values of m. A general investigation is made of the structure of Sylow subgroups of finite groups with the m-DCI property and with the m-CI property for large values of m. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 21–31, 1998     

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

Conjecture of Li and Praeger concerning the isomorphisms of Cayley graphs of A5

LetG be a finite group, andS a subset ofG \ |1| withS =S ⁻¹. We useX = Cay(G,S) to denote the Cayley graph ofG with respect toS. We callS a Cl-subset ofG, if for any isomorphism Cay(G,S) ≈ Cay(G,T) there is an α∈ Aut(G) such thatS ^α =T. Assume that m is a positive integer.G is called anm-Cl-group if every subsetS ofG withS =S ⁻¹ and | S | ≤m is Cl. In this paper we prove that the alternating groupA ₅ is a 4-Cl-group, which was a conjecture posed by Li and Praeger.     

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.     

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.