首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 171 毫秒
1.
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.  相似文献   

2.
t Let F = Cay(G, S), R(G) be the right regular representation of G. The graph Г is called normal with respect to G, if R(G) is normal in the full automorphism group Aut(F) of F. Г is called a bi-normal with respect to G if R(G) is not normal in Aut(Г), but R(G) contains a subgroup of index 2 which is normal in Aut(F). In this paper, we prove that connected tetravalent edge-transitive Cayley graphs on PGL(2,p) are either normal or bi-normal when p ≠ 11 is a prime.  相似文献   

3.
A graph is one-regular if its automorphism group acts regularly on the set of its arcs.Let n be a square-free integer.In this paper,we show that a cubic one-regular graph of order 2n exists if and only if n=3~tp1p2…p_s≥13,where t≤1,s≥1 and p_i's are distinct primes such that 3|(P_i—1). For such an integer n,there are 2~(s-1) non-isomorphic cubic one-regular graphs of order 2n,which are all Cayley graphs on the dihedral group of order 2n.As a result,no cubic one-regular graphs of order 4 times an odd square-free integer exist.  相似文献   

4.
Let G be a finite group. A Cayley graph over G is a simple graph whose automorphism group has a regular subgroup isomorphic to G. A Cayley graph is called a CI-graph(Cayley isomorphism) if its isomorphic images are induced by automorphisms of G. A well-known result of Babai states that a Cayley graph Γ of G is a CI-graph if and only if all regular subgroups of Aut(Γ) isomorphic to G are conjugate in Aut(Γ). A semi-Cayley graph(also called bi-Cayley graph by some authors) over G is a simple graph whose automorphism group has a semiregular subgroup isomorphic to G with two orbits(of equal size). In this paper, we introduce the concept of SCI-graph(semi-Cayley isomorphism)and prove a Babai type theorem for semi-Cayley graphs. We prove that every semi-Cayley graph of a finite group G is an SCI-graph if and only if G is cyclic of order 3. Also, we study the isomorphism problem of a special class of semi-Cayley graphs.  相似文献   

5.
A covering p from a Cayley graph Cay(G, X) onto another Cay(H, Y) is called typical Frobenius if G is a Frobenius group with H as a Frobenius complement and the map p : G →H is a group epimorphism. In this paper, we emphasize on the typical Frobenius coverings of Cay(H, Y). We show that any typical Frobenius covering Cay(G, X) of Cay(H, Y) can be derived from an epimorphism /from G to H which is determined by an automorphism f of H. If Cay(G, X1) and Cay(G, X2) are two isomorphic typical Frobenius coverings under a graph isomorphism Ф, some properties satisfied by Фare given.  相似文献   

6.
A Cayley graph F = Cay(G, S) of a group G with respect to S is called a circulant digraph of order pk if G is a cyclic group of the same order. Investigated in this paper are the normality conditions for arc-transitive circulant (di)graphs of order p^2 and the classification of all such graphs. It is proved that any connected arc-transitive circulant digraph of order p^2 is, up to a graph isomorphism, either Kp2, G(p^2,r), or G(p,r)[pK1], where r|p- 1.  相似文献   

7.
We investigate the family of vertex-transitive graphs with diameter 2. Let Γ be such a graph.Suppose that its automorphism group is transitive on the set of ordered non-adjacent vertex pairs. Then either Γ is distance-transitive or Γ has girth at most 4. Moreover, if Γ has valency 2, then Γ≌ C4 or C5; and for any integer n ≥ 3, there exist such graphs Γ of valency n such that its automorphism group is not transitive on the set of arcs. Also, we determine this family of grap...  相似文献   

8.
Enumerating the isomorphism or equivalence classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory.A covering projection p from a Cayley graph Cay(Г,X)onto another Cayley graph Cay(Q,y)is called typical if the function p:Г→Q on the vertex sets is a group epimorphism.A typical covering is called abelian(or circulant,respectively)if its covering graph is a Cayley graph on an abelism(or a cyclic,respectively)group.Recently,the equivalence classes of connected abelian typical prime-fold coverings of a circulant graph are enumerated.As a continuation of this work,we enumerate the equivalence classes of connected abelian typical cube-free fold coverings of a circulant graph.  相似文献   

9.
A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p~3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p~3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p~3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p~3 are all regular covers of the dipole Dip5 with covering transposition groups of order p~3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.  相似文献   

10.
A graph is called a semi-regular graph if its automorphism group action on its ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficient condition for an automorphism of the graph F to be an automorphism of a map with the underlying graph F is obtained. Using this result, all orientation-preserving automorphisms of maps on surfaces (orientable and non-orientable) or just orientable surfaces with a given underlying semi-regular graph F are determined. Formulas for the numbers of non-equivalent embeddings of this kind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, the non-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable and general surfaces are enumerated.  相似文献   

11.
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 2 (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  相似文献   

12.
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 A6 are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory  相似文献   

13.
A graph Г is said to be G-locally primitive, where G is a subgroup of automorphisms of Г, if the stabiliser Ga 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Ω 8 + (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.  相似文献   

14.
 Let G be a finite group and let Cay() be a Cayley graph of G. The graph Cay() is called a CI-graph of G if, for any for some Aut(G) only when CayCay(). In this paper, we study the isomorphism problem of connected Cayley graphs: to determine the groups G (or the types of Cayley graphs for a given group G) for which all connected Cayley graphs for G are CI-graphs.  相似文献   

15.
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≅ℤ4×ℤ2 orGQ 8×ℤ 2 r (r⩾0) and that every finite group has a normal Cayley digraph, where Zm is the cyclic group of orderm and Q8 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.  相似文献   

16.
We point out a countable set of pairwise nonisomorphic Cayley graphs of the group ℤ4 that are limit for finite minimal vertex-primitive graphs admitting a vertex-primitive automorphism group containing a regular Abelian normal subgroup. Supported by RFBR grant No. 06-01-00378. __________ Translated from Algebra i Logika, Vol. 47, No. 2, pp. 203–214, March–April, 2008.  相似文献   

17.
 A Cayley graph or digraph Cay(G,S) is called a CI-graph of G if, for any TG, Cay(G,S)≅Cay(G,T) if and only if S σ=T for some σ∈Aut(G). The aim of this paper is to characterize finite abelian groups for which all minimal Cayley graphs and digraphs are CI-graphs. Received: February 13, 1998 Final version received: May 7, 1999  相似文献   

18.
《代数通讯》2013,41(3):1201-1211
Abstract

For a group G and a subset S of G which does not contain the identity of G, the Cayley digraph Cay(G, S) is called normal if R(G) is normal in Aut(Γ). In this paper, we investigate the normality of Cayley digraphs of finite simple groups with out-valency 2 and 3. We give several sufficient conditions for such Cayley digraphs to be normal. By using this result, we consider the digraphical regular representations of finite simple groups.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号