一类半传递亚循环图
|
摘要
设Γ为一个图, AutΓ表示Γ的全自同构群。如果AutΓ在Γ的顶点集VΓ和边集EΓ上都是传递的,但在弧集AΓ上不传递,则称图Γ为半传递图。半传递图包含了很多好的性质和例子,吸引了众多学者的关注。例如,徐明耀教授刻画了阶为p3的半传递图[16];D. Maruˇsiˇc刻画了一类正则图和度数为4的半传递图[13];李才恒教授刻画了阶为素数幂的半传递亚循环图[7]。更多的结果参见D. Maruˇsiˇc的综述文章[12]。
设G为一个群,一个图Γ称为群G上的Cayley图,如果存在G的一个非空子集S -G{1},使得VΓ= S且顶点x与y邻接当且仅当yx~(-1)∈S。这个Cayley图记为Cay(G,S)。特别地,亚循环群上的Cayley图称为亚循环图。
本文的主要目的是刻画一类半传递亚循环图,并构造一个半传递亚循环图的无穷类。本文所得的主要定理如下:
定理1.设G = -a,b- = Zr:Zm是一个中心自由群,这里m = p1p2···ps, s≥2,3 < p1 <···< ps < r为素数,设Γ是G上的X-边传递Cayley图,且度数k < 2p1,其中G- < X≤Aut(Γ),则下述之一成立:
(1)Γ是X-局部本原的。
(2)Γ是群G上的正规Cayley图,且X≤Zr:Zr-1是可解的。
定理2.假设群G同定理1,k|(r - 1)且k < p1,则G有阶数为k的自同构σ使得bσ= b, aσ= aj。设Γ= Cay(G,S),则Γ为度数为2k的连通半传递图。
LetΓbe a graph, and let AutΓdenote its full automorphism group. If AutΓis transitive on both the vertex-set VΓand edge-set EΓ, but not transitive on thearc-set AΓ, thenΓis called a half-transitive graph. Characterizing and construct-ing half-transitive graphs have received much attention on the literature, see, forexample, half-transitive graphs of prime-cube order is given by Xu[16]; regular half-transitive graphs of valence 4 is constructed by Maruˇsiˇc[13]. Recently, half-transitivemetacirculant graphs of prime-power is characterized by Li[7]. For more results, seeMaruˇsiˇc[12].
Let G be a group. A graphΓis called a Cayley graph of G, if there is a subsetS - G, with S = S-1 := {g-1 | g∈S}, such that VΓ= G and x is adjacent to y ifand only if yx-1∈S. This Cayley graph is demoted by Cay(G,S). In particular,Cayley graphs of metacyclic groups are called metacirculants.
The main purpose of this thesis is to characterize a class of half-transitivemetacirculants, and to construct an in-nite family of connected half-transitive metacir-culants. The main results are the following two theorems.Theorem 1. Let G = -a,b- = Zr:Zm be a center-free group, where m = p1p2···pswith s≥2 and 3 < p1 <···< ps < r are primes. LetΓbe an X-edge-transitiveCayley graph of G of valency k < 2p1, where G- < X≤AutΓ. Then either
(1)Γis X-locally primitive, or
(2)Γis a normal Cayley graph of G and X≤Zr:Zr-1 is soluble.Theorem 2. Let G be a group as in Theorem 1. Suppose that k|(r - 1), k < p1.Then there existsσ∈Aut(G) such that o(σ) = k, bσ= b and aσ= aj. Let Γ= Cay(G,S), where ThenΓis a connected half-transitive graph of valency 2k.
设G为一个群,一个图Γ称为群G上的Cayley图,如果存在G的一个非空子集S -G{1},使得VΓ= S且顶点x与y邻接当且仅当yx~(-1)∈S。这个Cayley图记为Cay(G,S)。特别地,亚循环群上的Cayley图称为亚循环图。
本文的主要目的是刻画一类半传递亚循环图,并构造一个半传递亚循环图的无穷类。本文所得的主要定理如下:
定理1.设G = -a,b- = Zr:Zm是一个中心自由群,这里m = p1p2···ps, s≥2,3 < p1 <···< ps < r为素数,设Γ是G上的X-边传递Cayley图,且度数k < 2p1,其中G- < X≤Aut(Γ),则下述之一成立:
(1)Γ是X-局部本原的。
(2)Γ是群G上的正规Cayley图,且X≤Zr:Zr-1是可解的。
定理2.假设群G同定理1,k|(r - 1)且k < p1,则G有阶数为k的自同构σ使得bσ= b, aσ= aj。设Γ= Cay(G,S),则Γ为度数为2k的连通半传递图。
LetΓbe a graph, and let AutΓdenote its full automorphism group. If AutΓis transitive on both the vertex-set VΓand edge-set EΓ, but not transitive on thearc-set AΓ, thenΓis called a half-transitive graph. Characterizing and construct-ing half-transitive graphs have received much attention on the literature, see, forexample, half-transitive graphs of prime-cube order is given by Xu[16]; regular half-transitive graphs of valence 4 is constructed by Maruˇsiˇc[13]. Recently, half-transitivemetacirculant graphs of prime-power is characterized by Li[7]. For more results, seeMaruˇsiˇc[12].
Let G be a group. A graphΓis called a Cayley graph of G, if there is a subsetS - G, with S = S-1 := {g-1 | g∈S}, such that VΓ= G and x is adjacent to y ifand only if yx-1∈S. This Cayley graph is demoted by Cay(G,S). In particular,Cayley graphs of metacyclic groups are called metacirculants.
The main purpose of this thesis is to characterize a class of half-transitivemetacirculants, and to construct an in-nite family of connected half-transitive metacir-culants. The main results are the following two theorems.Theorem 1. Let G = -a,b- = Zr:Zm be a center-free group, where m = p1p2···pswith s≥2 and 3 < p1 <···< ps < r are primes. LetΓbe an X-edge-transitiveCayley graph of G of valency k < 2p1, where G- < X≤AutΓ. Then either
(1)Γis X-locally primitive, or
(2)Γis a normal Cayley graph of G and X≤Zr:Zr-1 is soluble.Theorem 2. Let G be a group as in Theorem 1. Suppose that k|(r - 1), k < p1.Then there existsσ∈Aut(G) such that o(σ) = k, bσ= b and aσ= aj. Let Γ= Cay(G,S), where ThenΓis a connected half-transitive graph of valency 2k.
引文
[1] E. Condre, 1/2-transitive graphs of order 3p, J. Algebraic Combin. 3(1994): 347-355.
[2] I. Z. Bouwer, vertex and edge-transitive nut not 1-transitive graphs, Canad. Math.Bull. 13(1970): 231-237.
[3] J. D. Dixon, B. Mortimer, Permutation groups, Springer Verlag, 1996.
[4] H. Dietrich, B. Eick, On the groups of cube-free order, J. Algebra, 292(2005), 122-137.
[5] C. D. Godsil, On the full automorphism group of a graph, Combinatorial 1 (1981),243-256.
[6] W. Feit, J. G. Thompson, Solvability of groups of odd order, Pacific J. Math 13(1963),775-1029.
[7] C. H. Li, Hyo-Seob Sim, On half-transitive metacirculant graphs of prime-power order,J. Combin. Theorey, Ser B, 81(2001): 45-57.
[8] D. Gorenstein, Finite Simple Groups, Plenum Press, 1982, New York.
[9] B. Huppert, Finite Groups, Springer-Verlag, 1967, Berlin.
[10] C. H. Li, Z. P. Lu, Edge-transitive Cayley graphs of square-free order, submitted.
[11] C. H. Li, Finite s-arc transitive graphs of prime-power order, Bull. London Math.Soc. 33(2001), 129-137.
[12] D. Maruˇsiˇc, Recent developments in half-transitive graphs, Discrete Math. 182(1998), 219-231.
[13] D. Maruˇsiˇc, R. Medela, Maps, one regular graphs and half-transitive graphs of valency4, Europ. J. Combin 19(1998), 345-354.
[14] W. T. Tutte, Connectivity in graphs, University of Toronto Press, Toronto, 1966.
[15] C. H. Li, Serres, The primitive permutation groups of square-free order.
[16] M. Y. Xu, Half-transitive graphs of prime-cube order, J. Algebraic Combin. 1(1992):275-282.
[17] S. Du, D. Malnic?, D. Marus?ic?, A classification of 2-arc transitive dihedrants, J. Com-bin. Theory Ser. B.
[18] J. Pan, Locally primitive Cayley graphs of metacyclic, J. Combin, 16(2009), R 96.
[19] C. H. Li, J. Pan, Locally primitive graphs of prime-power order[J], J. Australia Math.Soc. 86(2009), 111-122.
[20] C. H. Li, J. Pan, Finite 2-arc transitive abelian Cayley graphs, Europ. J. Combin.29(2008), 148-158.
[21] C. E. Praeger, The inclusion problem for finite primitive permution groups, Proc.London Math. Soc.(3) 60 1990, 68-88.
[22] C. E. Praeger, On O’Nan-Scott Theory for finite quasiprimitive permutation groupsand application to 2-arc transitive graphs, J. London Math. Soc. (2)47 (1992), 227-239.
[23] G. Sabidussi, Vertex-transitive graphs,Monatsh. Math. 68(1964), 426-438.
[24] W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11(1959), 61-64.
[25] B. Alspach and T. D. Parsons, A construction for vertex-transitive graphs, Canad. J.Math. 34 (1982), 307-318.
[26] C. E. Praeger, Finite normal edge-transitive Cayley graphs, Bull. Austral. Math. Soc.60(1999), 207-220.
[27]徐明曜,有限群导引[M],北京:科学出版社, 1999.
[28]张远达,有限群构造[M],北京:科学出版社, 1982.
[29] M. Y. Xu, Automorphism groups and isomorphisms of Caylay graphs, Discrete Math.182(1998),309-320.
[30] M. Sˇajna, half-transitive of some metacirculants, Discrete Math. 185(1998), 117-136.
[2] I. Z. Bouwer, vertex and edge-transitive nut not 1-transitive graphs, Canad. Math.Bull. 13(1970): 231-237.
[3] J. D. Dixon, B. Mortimer, Permutation groups, Springer Verlag, 1996.
[4] H. Dietrich, B. Eick, On the groups of cube-free order, J. Algebra, 292(2005), 122-137.
[5] C. D. Godsil, On the full automorphism group of a graph, Combinatorial 1 (1981),243-256.
[6] W. Feit, J. G. Thompson, Solvability of groups of odd order, Pacific J. Math 13(1963),775-1029.
[7] C. H. Li, Hyo-Seob Sim, On half-transitive metacirculant graphs of prime-power order,J. Combin. Theorey, Ser B, 81(2001): 45-57.
[8] D. Gorenstein, Finite Simple Groups, Plenum Press, 1982, New York.
[9] B. Huppert, Finite Groups, Springer-Verlag, 1967, Berlin.
[10] C. H. Li, Z. P. Lu, Edge-transitive Cayley graphs of square-free order, submitted.
[11] C. H. Li, Finite s-arc transitive graphs of prime-power order, Bull. London Math.Soc. 33(2001), 129-137.
[12] D. Maruˇsiˇc, Recent developments in half-transitive graphs, Discrete Math. 182(1998), 219-231.
[13] D. Maruˇsiˇc, R. Medela, Maps, one regular graphs and half-transitive graphs of valency4, Europ. J. Combin 19(1998), 345-354.
[14] W. T. Tutte, Connectivity in graphs, University of Toronto Press, Toronto, 1966.
[15] C. H. Li, Serres, The primitive permutation groups of square-free order.
[16] M. Y. Xu, Half-transitive graphs of prime-cube order, J. Algebraic Combin. 1(1992):275-282.
[17] S. Du, D. Malnic?, D. Marus?ic?, A classification of 2-arc transitive dihedrants, J. Com-bin. Theory Ser. B.
[18] J. Pan, Locally primitive Cayley graphs of metacyclic, J. Combin, 16(2009), R 96.
[19] C. H. Li, J. Pan, Locally primitive graphs of prime-power order[J], J. Australia Math.Soc. 86(2009), 111-122.
[20] C. H. Li, J. Pan, Finite 2-arc transitive abelian Cayley graphs, Europ. J. Combin.29(2008), 148-158.
[21] C. E. Praeger, The inclusion problem for finite primitive permution groups, Proc.London Math. Soc.(3) 60 1990, 68-88.
[22] C. E. Praeger, On O’Nan-Scott Theory for finite quasiprimitive permutation groupsand application to 2-arc transitive graphs, J. London Math. Soc. (2)47 (1992), 227-239.
[23] G. Sabidussi, Vertex-transitive graphs,Monatsh. Math. 68(1964), 426-438.
[24] W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11(1959), 61-64.
[25] B. Alspach and T. D. Parsons, A construction for vertex-transitive graphs, Canad. J.Math. 34 (1982), 307-318.
[26] C. E. Praeger, Finite normal edge-transitive Cayley graphs, Bull. Austral. Math. Soc.60(1999), 207-220.
[27]徐明曜,有限群导引[M],北京:科学出版社, 1999.
[28]张远达,有限群构造[M],北京:科学出版社, 1982.
[29] M. Y. Xu, Automorphism groups and isomorphisms of Caylay graphs, Discrete Math.182(1998),309-320.
[30] M. Sˇajna, half-transitive of some metacirculants, Discrete Math. 185(1998), 117-136.