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 A15 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.
NOTES
#Corresponding author.