ABSTRACT

Let be a connected Cayley graph of group G, then Γ is called normal if the right regular representation of G is a normal subgroup of, the full automorphism group of Γ. For the case where G is a finite nonabelian simple group and Γ is symmetric cubic Cayley graph, Caiheng Li and Shangjin Xu proved that Γ is normal with only two exceptions. Since then, the normality of nonsymmetric cubic Cayley graph of nonabelian simple group aroused strong interest of people. So far such graphs which have been known are all normal. Then people conjecture that all of such graphs are either normal or the Cayley subset consists of involutions. In this paper we give an negative answer by two counterexamples. As far as we know these are the first examples for the non-normal cubic nonsymmetric Cayley graphs of finite nonabelian simple groups.

1. Introduction

All graphs in this paper are assumed to be finite, simple, connected and undirected.

Let be a graph and denote, , and the vertex set, edge set, arc set and full automorphism group respectively. Denote the valency of. Then is said to be X-vertex-transitive, Xedge-transitive and X-arc-transitive if acts transitively on, , and respectively. And further is simply called vertex-transitive, edgetransitive and arc-transitive when. Sometimes arc-transitive graph is simply called symmetric graph.

A graph is a Cayley graph of a group if there is a subset with

such that and

.

Bydefinition, has valency, and it is connected if and only if. Moreover, can be viewed as a regular subgroup of by right multiplication action on V(G). For convenience, we still denote this regular subgroup by G. Then a Cayley graph is vertextransitive. On the contrary a vertex-transitive graph is a Cayley graph of a group G if and only if contains a subgroup that is regular on and isomorphic to G (see [1, Proposition 16.3]). If G is a normal subgroup of, then is called a normal Cayley graph of G. The is said to be core-free (with respect to G) if G is core-free in some

that is,

.

Let X be an arbitrary finite group with a core-free subgroup H and let D be a union of several double cosets of satisfying. The coset graph is the graph with vertex set

such that and are adjacent if and only if. Consider the action of X on by right multiplication on right cosets. Note this action is faithful and preserves the adjacency of the coset graph, thus we identify X with a subgroup of. Obviously, is connected if and only if. The valency of is. Let be the set of vertices of, which are adjacent with H. It is easy to check that H has n orbits on if and only if D is the union of n double cosets of H. Further, the properties stated in the following lemma are well-known, its proof can be found in [2-4].

Proposition 1.1 Let be defined as above.

1) If is a X-symmetric graph of valency at least 3, then there exists an element satisfying and. Furthermore, we may choose g to be a 2-element;

2) Let be a Cayley graph and. Let be the stabilizer of in X. We have;

3) Let be a coset graph and G be a complement of H in X. Denote. Then the Cayley graph is isomorphic to

, and hence. In particular, S contains an involution of G if the valency of is odd.

Tutte [5,6] proved that every finite connected cubic symmetric graph is -regular for some. Since Tutte’s seminal work, the study of s-arc-transitive graphs, aiming at constructing and characterizing such graphs, has received considerable attention in the literature, see [7-12] for example, and now there is an extensive body of knowledge on such graphs. Fang, Li, Wang and Xu [13] proved that for most finite nonabelian simple groups, the corresponding connected cubic Cayley graphs are normal. Caiheng Li [14] and Shangjin Xu [15] proved that every cubic symmetric Cayley graph of finite nonabelian simple group is normal except two 5-arc transitive graphs of the alternating group (up to isomorphic). Then it arises a natural problem: whether each of the cubic non-symmetric Cayley graph of finite nonabelian simple group is normal? This problem has become the topics of greatest concern after the results of Li and Xu. Based on past experience, people conjure that if there exist some normal graphs, then the Cayley subsets of them must be consist of involutions. However, there have no any answer to the problem until now.

To answer this problem, by studying cubic nonsymmetric Cayley graphs, we give a negative answer. In the present paper, we give two non-normal examples which subsets are not consist of involutions. It’s worth noting that these are the first examples for the non-normal cubic nonsymmetric Cayley graphs of finite nonabelian simple groups.

In the rest of this section, we assume that

is a cubic nonsymmetric Cayley graph with. Denote H the vertex stabilizer of X on. Note is cubic nonsymmetric, then H must be 2-group. Let N be the maximal one among normal subgroups of X contained in G, that is, is the core of G in X.

2. Main Results

In this section, we construct some examples of cubic nonnormal nonsymmetric Cayley graphs on finite nonableian simple groups.

Example 2.1 Let be the alternating group A₁₅ and set, where

Let, then is cubic nonsymmetric connected Cayley graph, which is not normal.

Let be a connected graph, where

and with

It is easy to see with 1 and 5 being in different orbits, which follows. On the other hand, and lead to

.

Simple computation shows and , i.e.,. Then the valency of is, and moreover is nonsymmetric since. Since is connected, so.

Let. Clearly acts transitively on, which follows X acts 2-transitively onand hence primitively, on. Let. Then

and X contains a 5-cycle

. Noting that every generator of X is even permutation, by [16, Theorem 3.3E]. Then the stabilizer. On the other hand H acts regularly on leads to that acts regularly on. Simple computation shows. Hence by Proposition 1.1, and furthermore is connected by the connectivity of. Namely, which leads to. However, which changes 1. Thus, i.e., G is not normal in X.

Example 2.2 Let G be the alternating group.

Set, where

Let, then is cubic nonsymmetric connected Cayley graph, which is not normal.

Let be a connect vertex-transitive graph, where and with

It is trivial for us to get with 1, 5 and 9 being in different orbits, then. By simple checking, we find and. It follows

.

Note that and, then

. Namely the valency of is. However, thus is nonsymmetric. Notice that is connected, i.e.,

.

Set. Clearly acts transitively on, and then X acts 2-transitively on

, and hence primitively, on. Let.

Then and X contains a 17-cycle

.

Note that all generators of X are even permutations, then by [16, Theorem 3.3E]. Then the stabilizer. Noting H acts regularly on,

acts regularly on. It is shown, by computing, that. That is by Proposition 1.1. And moreover the connectivity of leads to is also connected. Hence, i.e.,. However

which changes 1. Thus, i.e., is not normal in X.

REFERENCES

NOTES

^*The project sponsored by the scientific research foundation of Guangxi University (Grant No. XBZ110328), the fund of Yunnan University (No. 2012CG015), the National Natural Science Foundation of China (No. 11126343) and (No. 11171292), and NSF of Guangxi (No. 2012- GXNSFBA053010).

^#Corresponding author.