On the extendability of certain semi-Cayley graphs of finite abelian groups

A connected graph Γ with at least 2n+2 vertices is said to be n-extendable if every matching of size n in Γ can be extended to a perfect matching. The aim of this paper is to study the 1-extendability and 2-extendability of certain semi-Cayley graphs of finite abelian groups, and the classification of connected 2-extendable semi-Cayley graphs of finite abelian groups is given. Thus the 1-extendability and 2-extendability of Cayley graphs of non-abelian groups which can be realized as such semi-Cayley graphs of abelian groups can be deduced. In particular, the 1-extendability and 2-extendability of connected Cayley graphs of generalized dicyclic groups and generalized dihedral groups are characterized.     

Locally primitive Cayley graphs of finite simple groups

A graph Г is said to be G-locally primitive, where G is a subgroup of automorphisms of Г, if the stabiliser G_a of a vertex α acts primitively on the set Г( α ) of vertices of Г adjacent to α. For a finite non-abelian simple group L and a Cayley subset S of L, suppose that L ⊴ G ⩽ Aut( L), and the Cayley graph Г = Cay ( L, S) is G-locally primitive. In this paper we prove that L is a simple group of Lie type, and either the valency of Г is an add prine divisor of |Out(L)|, orL =PΩ ₈ ⁺ (q) and Г has valency 4. In either cases, it is proved that the full automorphism group of Г is also almost simple with the same socle L.     

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

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.     

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.     

二面体群D_(2n)的4度正规Cayley图

设G是有限群,S是G的不包含单位元1的非空子集．定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}． Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规．图X称为1-正则的如果它的全自同构群在它的弧集上正则作用．本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类．     

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 finite edge transitive graphs and rotary maps

It is shown that every connected vertex and edge transitive graph has a normal multicover that is a connected normal edge transitive Cayley graph. Moreover, every chiral or regular map has a normal cover that is a balanced chiral or regular Cayley map, respectively. As an application, a new family of half-transitive graphs is constructed as 2-fold covers of a family of 2-arc transitive graphs admitting Suzuki groups.     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.     

K3,3-free intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper we classify all finite groups whose intersection graphs are K_3,3-free.     

Connectivity of intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper, we classify finite solvable groups whose intersection graphs are not 2-connected and finite nilpotent groups whose intersection graphs are not 3-connected. Our methods are elementary.     

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.     

Two sufficient conditions for non-normal Cayley graphs and their applications

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 the full automorphism group of Cay(G, S). In this paper, two sufficient conditions for non-normal Cayley graphs are given and by using the conditions, five infinite families of connected non-normal Cayley graphs are constructed. As an application, all connected non-normal Cayley graphs of valency 5 on A5 are determined, which generalizes a result about the normality of Cayley graphs of valency 3 or 4 on A5 determined by Xu and Xu. Further, we classify all non-CI Cayley graphs of valency 5 on A5, while Xu et al. have proved that As is a 4-CI group.     

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     

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.     

Split non-threshold Laplacian integral graphs

The aim of this article is to answer a question posed by Merris in European Journal of Combinatorics, 24 (2003) pp. 413 ? 430, about the possibility of finding split non-threshold graphs that are Laplacian integral, i.e. graphs for which the eigenvalues of the corresponding Laplacian matrix are integers. Using Kronecker products, balanced incomplete block designs, and solutions to certain Diophantine equations, we show how to build infinite families of these graphs.