有限双Cayley图的同构问题
|
摘要
在群与图的研究中,图的同构问题一直是一个热门问题.在本毕业论文中,我们主要研究双Cayley图的同构问题和BCI-群的Sylow子群的结构.
二部图是一类很重要的图,而双Cayley图r是具有下列性质的特殊二部图：即图r的全自同构群Aut(r)包含一个在r的二部划分上作用分别正则的子群.事实上,这类图也可以通过群直接构造：设G是一个有限群,而S是群G的一个子集(允许含有群G的单位元),则群G关于子集S的双Cayley图是以G×{0,1}为点集和以{(g,0),(sg,1)}(g∈G,s∈S)为边集的二部图,记作BCay(G,S).
对任一有限群G和G的一个不含单位元的子集S,我们可以如下定义著名的图类Cayley图Γ=Cay(G, S):点集V(r)=G,弧集Arc(Γ)={(g,sg)|g∈G,s∈S}对同一个群G和同一个子集S,所作的Cayley图Ca,y(G,S)和双Cayley图BCay(G,S)有很紧密的联系,例如BCay(G,S)是Cay(G,S)的标准双覆盖.同时Cayley图Cay(G, S)和双Cayley图BCay(G,S)也有很大的不同,例如BCay(G,S)总是无向二部图,而Cay(G,S)是无向图当且仅当S=S-1；Cay(G,S)总是点传递图,而BCay(G,S)可能不点传递,例如[1]构造了边传递但不点传递的3度双Cayley图的无限族的例子.
大家知道,对Cayley图的同构问题研究起步较早,称为Cayley图的CI性,并取得非常丰富的结果.而对双Cayley图同构问题的研究到目前为止结果还很少,因此对双Cayley图的同构问题的研究仍然具有重要意义.类似于Cayley图的CI性,我们可以定义双Cayley图的BCI性,参看定义2.6.
在文献[2]中已经证明了任何有限群G都是1-BCI-群；G是2-BCI-群当且仅当对G中任意一对同阶元s与t, Aut(G)在s与t或t-1之间传递,参看引理2.21.所以本论文主要研究对m≥3的群的m-BCI性.我们知道有限群的Sylow子群的结构的了解对群本身的理解具有重要帮助,所以我们首先决定了3-BCI-群的Sylow子群结构的所有可能性.我们证明对一个3-BCI群G：它的Sylow2-子群要么初等交换,要么循环,要么同构于Qs; Sylow p-子群是齐次循环群,其中p是|G|的一个奇素因子.
其次,作为上述结论的应用,本文决定了所有的有限非交换单3-BCI-群.我们证明一个有限非交换单群G是3-BCI-群当且仅当G是交错群A5.
再次,我们研究有限循环群的m-BCI性,并重点研究了2p阶循环群和循环p-群,其中p是素数.我们证明2p阶循环群是3-BCI-群；循环p-群是(p-1)-BCI-群.
最后,我们决定了所有阶小于9的群的BCI性.除了二面体群D8,循环群Z8和交换群Z4×Z2外,所有的阶小于9的群都是BCI-群.
In algebraic graph theory, the study of isomorphisms of graphs has a long history. In this thesis, we investigate the isomorphism problem for bi-Cayley graphs and also the structures of Sylow subgroups of BCI-groups.
A bipartite graph is a graph which has no odd length cycles. The family of bipartite graphs plays an important role in graph theory. In particular, a bi-Cayley graph Γ is a bipartite graph with the following property:there exists a subgroup of the automorphism group Aut(Γ) which is regular on the two biparts of the vertex set of Γ. In fact, bi-Cayley graphs can also be constructed from groups directly. Let G be a finite group, S be a subset of G (probably contains the identity). Then the bi-Cayley graph of G with respect to S is the bipartite graph with vertex set G x{0,1} and edge set{(g,0),(sg,1)|g∈G,s∈S}, denoted by BCay(G,S).
For a finite group G and a subset S(?)G\{1}, we can define the well-known Cayley graph Γ as the graph with vertex set G and arc set{(g, sg)|g∈G,s∈S}, denoted by Cay(G, S). For Cayley graphs and bi-Cayley graphs, there are con-nections between Cay(G, S) and BCay(G, S). For example, BCay(G, S) is the standard double cover of Cay(G, S). Meanwhile, there are many differences be-tween Cay(G, S) and BCay(G, S). For example, BCay(G, S) is always undirected but Cay(G, S) is undirected if and only if S=S-1; Cay(G, S) is vertex transitive, but BCay(G, S) may be not vertex transitive, see.
The isomorphism problem of Cayley graphs is called the CI property of Cayley graphs. It has been studied extensively. However, the study of the iso- morphism problem of bi-Cayley graphs is a new topic, and there are limit results about it until now, see. Thus it is an interesting question to study the iso-morphism problem of bi-Cayley graphs. Analogous to the CI property of Cayley graphs, we can define the BCI property of bi-Cayley graphs, see definition2.6.
In, it has been proved that every finite group G is a1-BCI-group; G is a2-BCI-groups if and only if for any pair of same order elements a, b, there exists a∈Aut(G) such that a(?)=b or b-1. Thus in this thesis, we will mainly study m-BCI-groups for m≥3.We know that the understanding of the structures of Sylow subgroups of groups are very important for the understanding of the groups themselves, and so we first determine all the possibilities of the Sylow subgroups of3-BCI-groups. We show that for a3-BCI-group G, its Sylow2-subgroup is elementary abelian, cyclic, or the quaternion group Q8; its Sylow p-subgroup is homocyclic where p is an odd prime.
Secondly, as an application of the above result, we decide all non-abelian simple3-BCI-groups. We prove that a non-abelian simple group G is a3-BCI-group if and only if G=A5.
Thirdly, we investigate the m-BCI property for finite cyclic groups where m≥3, in particular, for cyclic groups of order2p and pn where p is a prime and n is a positive integer. We show that cyclic groups of order2p are3-BCI-groups and cyclic groups of order pn are (p-1)-BCI-groups.
Finally, we determine the BCI property of small order groups. It is shown that except for D8, Z8and Z4×Z2, all groups of order less than9are BCI-groups.
二部图是一类很重要的图,而双Cayley图r是具有下列性质的特殊二部图：即图r的全自同构群Aut(r)包含一个在r的二部划分上作用分别正则的子群.事实上,这类图也可以通过群直接构造：设G是一个有限群,而S是群G的一个子集(允许含有群G的单位元),则群G关于子集S的双Cayley图是以G×{0,1}为点集和以{(g,0),(sg,1)}(g∈G,s∈S)为边集的二部图,记作BCay(G,S).
对任一有限群G和G的一个不含单位元的子集S,我们可以如下定义著名的图类Cayley图Γ=Cay(G, S):点集V(r)=G,弧集Arc(Γ)={(g,sg)|g∈G,s∈S}对同一个群G和同一个子集S,所作的Cayley图Ca,y(G,S)和双Cayley图BCay(G,S)有很紧密的联系,例如BCay(G,S)是Cay(G,S)的标准双覆盖.同时Cayley图Cay(G, S)和双Cayley图BCay(G,S)也有很大的不同,例如BCay(G,S)总是无向二部图,而Cay(G,S)是无向图当且仅当S=S-1；Cay(G,S)总是点传递图,而BCay(G,S)可能不点传递,例如[1]构造了边传递但不点传递的3度双Cayley图的无限族的例子.
大家知道,对Cayley图的同构问题研究起步较早,称为Cayley图的CI性,并取得非常丰富的结果.而对双Cayley图同构问题的研究到目前为止结果还很少,因此对双Cayley图的同构问题的研究仍然具有重要意义.类似于Cayley图的CI性,我们可以定义双Cayley图的BCI性,参看定义2.6.
在文献[2]中已经证明了任何有限群G都是1-BCI-群；G是2-BCI-群当且仅当对G中任意一对同阶元s与t, Aut(G)在s与t或t-1之间传递,参看引理2.21.所以本论文主要研究对m≥3的群的m-BCI性.我们知道有限群的Sylow子群的结构的了解对群本身的理解具有重要帮助,所以我们首先决定了3-BCI-群的Sylow子群结构的所有可能性.我们证明对一个3-BCI群G：它的Sylow2-子群要么初等交换,要么循环,要么同构于Qs; Sylow p-子群是齐次循环群,其中p是|G|的一个奇素因子.
其次,作为上述结论的应用,本文决定了所有的有限非交换单3-BCI-群.我们证明一个有限非交换单群G是3-BCI-群当且仅当G是交错群A5.
再次,我们研究有限循环群的m-BCI性,并重点研究了2p阶循环群和循环p-群,其中p是素数.我们证明2p阶循环群是3-BCI-群；循环p-群是(p-1)-BCI-群.
最后,我们决定了所有阶小于9的群的BCI性.除了二面体群D8,循环群Z8和交换群Z4×Z2外,所有的阶小于9的群都是BCI-群.
In algebraic graph theory, the study of isomorphisms of graphs has a long history. In this thesis, we investigate the isomorphism problem for bi-Cayley graphs and also the structures of Sylow subgroups of BCI-groups.
A bipartite graph is a graph which has no odd length cycles. The family of bipartite graphs plays an important role in graph theory. In particular, a bi-Cayley graph Γ is a bipartite graph with the following property:there exists a subgroup of the automorphism group Aut(Γ) which is regular on the two biparts of the vertex set of Γ. In fact, bi-Cayley graphs can also be constructed from groups directly. Let G be a finite group, S be a subset of G (probably contains the identity). Then the bi-Cayley graph of G with respect to S is the bipartite graph with vertex set G x{0,1} and edge set{(g,0),(sg,1)|g∈G,s∈S}, denoted by BCay(G,S).
For a finite group G and a subset S(?)G\{1}, we can define the well-known Cayley graph Γ as the graph with vertex set G and arc set{(g, sg)|g∈G,s∈S}, denoted by Cay(G, S). For Cayley graphs and bi-Cayley graphs, there are con-nections between Cay(G, S) and BCay(G, S). For example, BCay(G, S) is the standard double cover of Cay(G, S). Meanwhile, there are many differences be-tween Cay(G, S) and BCay(G, S). For example, BCay(G, S) is always undirected but Cay(G, S) is undirected if and only if S=S-1; Cay(G, S) is vertex transitive, but BCay(G, S) may be not vertex transitive, see.
The isomorphism problem of Cayley graphs is called the CI property of Cayley graphs. It has been studied extensively. However, the study of the iso- morphism problem of bi-Cayley graphs is a new topic, and there are limit results about it until now, see. Thus it is an interesting question to study the iso-morphism problem of bi-Cayley graphs. Analogous to the CI property of Cayley graphs, we can define the BCI property of bi-Cayley graphs, see definition2.6.
In, it has been proved that every finite group G is a1-BCI-group; G is a2-BCI-groups if and only if for any pair of same order elements a, b, there exists a∈Aut(G) such that a(?)=b or b-1. Thus in this thesis, we will mainly study m-BCI-groups for m≥3.We know that the understanding of the structures of Sylow subgroups of groups are very important for the understanding of the groups themselves, and so we first determine all the possibilities of the Sylow subgroups of3-BCI-groups. We show that for a3-BCI-group G, its Sylow2-subgroup is elementary abelian, cyclic, or the quaternion group Q8; its Sylow p-subgroup is homocyclic where p is an odd prime.
Secondly, as an application of the above result, we decide all non-abelian simple3-BCI-groups. We prove that a non-abelian simple group G is a3-BCI-group if and only if G=A5.
Thirdly, we investigate the m-BCI property for finite cyclic groups where m≥3, in particular, for cyclic groups of order2p and pn where p is a prime and n is a positive integer. We show that cyclic groups of order2p are3-BCI-groups and cyclic groups of order pn are (p-1)-BCI-groups.
Finally, we determine the BCI property of small order groups. It is shown that except for D8, Z8and Z4×Z2, all groups of order less than9are BCI-groups.
引文
[1]Z.P. Lu, C.Q. Wang and M.Y. Xu, Semisymmetric cubic graphs constructed from bi-Cayley graphs of An, Ars Combin.80(2006),177-187.
[2]徐尚进,靳伟,石琴,等.双Cayley图的BCI-性,[J].广西师范大学学报,26(2)(2006),33-36.
[3]H.S.M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, Springer, Berlin, Gottinger,1957.
[4]G.O. Sabidussi, Vertex transitive graphs, Monatsh. Math 68 (1964),426-438.
[5]C.D. Godsil, On Cayley graph isomorphisms, Ars Combin.5 (1983),231-246.
[6]D. Gorenstein, Finite Groups, Second edition. Chelsea Publishing Co., New York, (1980).
[7]D.J.S. Robinson, A Course in the Theory of Groups, second edition, Springer-Verlag, New York,1982.
[8]M. Suzuki, Group Theory I, Springer-Verlag, New York,1982.
[9]M. Suzuki, Group Theory II, Springer-Verlag, New York,1986.
[10]徐明曜,有限群导引(上,下册)[M],北京：科学出版社,第二版1999.
[11]N. Biggs, Algebraic Graph Theory [M], second edition, Cambridge Univer-sity Press, Cambridge,1993.
[12]J.D. Dixon and B. Mortimer, Permutation Groups, Springer, New York, (1996).
[13]H. Wielandt, Finite Permutation Groups, New York:Academic Press (1964).
[14]C.H. Li, On isomorphisms of finite Cayley graphs-a survey, Discrete Math. 256 (2002) 301-334.
[15]X.G. Fang, C.H. Li J. Wang and M.Y. Xu, On cubic Cayley graphs of finite simple groups, Discrete Math.244(2002),67-75.
[16]C.D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981),243-256.
[17]C.H. Li, On isomorphisms of connected Cayley graphs Ⅲ, Bull. Austral. Math. Soc.58 (1998),137-145.
[18]M. Hirasaka, M. Muzychuk, Association schemes with a relation ofvalency two, Discrete Math., to appear.
[19]C.H. Li, Isomorphisms and classification of Cayley graphs of small valencies on finite abelian groups, Australas. J. Combin.12 (1995),3-14.
[20]C.H. Li, On isomorphisms of connected Cayley graphs, Discrete Math.178 (1998),109-122.
[21]M. Muzychuk, Adam's conjecture is true in the square-free case, J. Combin. Theory (A) 72(1995),118-134.
[22]M. Muzychuk, On Adam's conjecture for circulant graphs, Discrete Math. 167/168(1997),497-510.
[23]L. Babai and P. Frankl, Isomorphisms ofCayley graphs I, in:Colloqzeria Mathematica Societatis JNanos Bolyai, Vol.18. Combinatorics, Keszthely, 1976, North-Holland, Amsterdam, (1978),35-52.
[24]L.A. Nowitz, A non-Cayley-invariant Cayley graph of the elementary Abelian group of order 64, Discrete Math.110(1992),223-228.
[25]C.H. Li and C.E. Praeger, Finite groups in which any two elements of the same order are either fused or inverse-fused, Comm. Algebra.25(11) (1997), 3081-3118.
[26]C.H. Li and C.E. Praeger, On the isomorphisms problem for finite Cayley graphs of bounded valency, European J. Combin.20(1999),279-292.
[27]D. Z. Djokovic, Isomorphism problem for a special class of graphs, Acad. Sci. Hungar.21(1970),267-270.
[28]B. Elspas and J. Turner, Graphs with circulant adjacency matrices, J. Com-bin. Theory 9(1970),297-307.
[29]J. Turner, Point symmetric graphs with a prime number of points, J. Com-bin. Theory 3(1967),136-145.
[30]B.D. Mckay, Unpublished computer search for cyclic CI graphs.
[31]L. Babai, Isomorphism problem for a class of point-symmetric structure, Acta Math. Acad. Sci. Hungar 29 (1977),329-336.
[32]C.E. Praeger, Finite transitive permutation groups and finite vertex-transitive graphs, in Graph Symmetry:Algebraic Methods and Applications, NATO ASI Ser. C497 (1997),277-318.
[33]X.G. Fang, C.H. Li and M.Y. Xu, On edge-transitive Cayley graphs of va-lency four, European J. Combin.25(2004),1107-1116.
[34]J.X. Zhou and Y.Q. Feng, Two sufficient conditions for non-normal Caylay graphs and their applications, Sci. China Ser. A (50) (2) 2007,201-216.
[35]C.H. Li, Isomorphisms of finite Cayley graphs, Bull. Austral. Math. Soc.56 (1997),169-172.
[36]C.H. Li, On isomorphisms of connected Cayley graphs, II, J. Combin. Theory Ser. B 74 (1998) 28-34.
[37]M.Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Dis-crete Math.182(1998),309-319.
[38]S. J. Xu, The Nature of Non-weak 3-DCI in Frobenius Group with 3p Order, Guangxi Sci.7(2)(2000),115-117.
[39]方新贵,有限交换2-DCI-群的刻画,数学杂志,8(1988),315-317.
[40]徐尚进,李靖建,靳伟,等.qp阶亚循环群的弱q-DCI性,广西师范大学学报,25(2007),10-13.
[41]S.F. Du and M.Y. Xu, A classification of semi-symmetric graphs of order 2pq, Com. Algebra 25(2004),1107-1116.
[42]C.H. Li and C.E. Praeger, The finite simple groups with at most two fusion classes of every order, Comm. Algebra.24 (1996),3681-3704.
[43]Z.P. Lu, On the automorphism groups of Bi-Cayley graphs, Beijing Daxue Xuebao Ziran Kexue Ban 39(1) (2003),1-5.
[44]路在平,博士学位论文,北京大学,2003.
[45]靳伟,双Cayley图的若干性质,广西大学,2007.
[46]J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker and R.A. Wilson, Atlas of Finite Groups, Clarendon Press, Oxford,1985.
[47]徐尚进,覃建军,邓芸萍,4p阶二面体群的连通三度Cayley图,送审.
[48]C.E. Praeger, Highly arc transitive digraphs, European J. Combin.10 (1989) 281-292.
[49]D. Gorenstein, Finite Simple Groups, Plenum Press, New York,1982.
[2]徐尚进,靳伟,石琴,等.双Cayley图的BCI-性,[J].广西师范大学学报,26(2)(2006),33-36.
[3]H.S.M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, Springer, Berlin, Gottinger,1957.
[4]G.O. Sabidussi, Vertex transitive graphs, Monatsh. Math 68 (1964),426-438.
[5]C.D. Godsil, On Cayley graph isomorphisms, Ars Combin.5 (1983),231-246.
[6]D. Gorenstein, Finite Groups, Second edition. Chelsea Publishing Co., New York, (1980).
[7]D.J.S. Robinson, A Course in the Theory of Groups, second edition, Springer-Verlag, New York,1982.
[8]M. Suzuki, Group Theory I, Springer-Verlag, New York,1982.
[9]M. Suzuki, Group Theory II, Springer-Verlag, New York,1986.
[10]徐明曜,有限群导引(上,下册)[M],北京：科学出版社,第二版1999.
[11]N. Biggs, Algebraic Graph Theory [M], second edition, Cambridge Univer-sity Press, Cambridge,1993.
[12]J.D. Dixon and B. Mortimer, Permutation Groups, Springer, New York, (1996).
[13]H. Wielandt, Finite Permutation Groups, New York:Academic Press (1964).
[14]C.H. Li, On isomorphisms of finite Cayley graphs-a survey, Discrete Math. 256 (2002) 301-334.
[15]X.G. Fang, C.H. Li J. Wang and M.Y. Xu, On cubic Cayley graphs of finite simple groups, Discrete Math.244(2002),67-75.
[16]C.D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981),243-256.
[17]C.H. Li, On isomorphisms of connected Cayley graphs Ⅲ, Bull. Austral. Math. Soc.58 (1998),137-145.
[18]M. Hirasaka, M. Muzychuk, Association schemes with a relation ofvalency two, Discrete Math., to appear.
[19]C.H. Li, Isomorphisms and classification of Cayley graphs of small valencies on finite abelian groups, Australas. J. Combin.12 (1995),3-14.
[20]C.H. Li, On isomorphisms of connected Cayley graphs, Discrete Math.178 (1998),109-122.
[21]M. Muzychuk, Adam's conjecture is true in the square-free case, J. Combin. Theory (A) 72(1995),118-134.
[22]M. Muzychuk, On Adam's conjecture for circulant graphs, Discrete Math. 167/168(1997),497-510.
[23]L. Babai and P. Frankl, Isomorphisms ofCayley graphs I, in:Colloqzeria Mathematica Societatis JNanos Bolyai, Vol.18. Combinatorics, Keszthely, 1976, North-Holland, Amsterdam, (1978),35-52.
[24]L.A. Nowitz, A non-Cayley-invariant Cayley graph of the elementary Abelian group of order 64, Discrete Math.110(1992),223-228.
[25]C.H. Li and C.E. Praeger, Finite groups in which any two elements of the same order are either fused or inverse-fused, Comm. Algebra.25(11) (1997), 3081-3118.
[26]C.H. Li and C.E. Praeger, On the isomorphisms problem for finite Cayley graphs of bounded valency, European J. Combin.20(1999),279-292.
[27]D. Z. Djokovic, Isomorphism problem for a special class of graphs, Acad. Sci. Hungar.21(1970),267-270.
[28]B. Elspas and J. Turner, Graphs with circulant adjacency matrices, J. Com-bin. Theory 9(1970),297-307.
[29]J. Turner, Point symmetric graphs with a prime number of points, J. Com-bin. Theory 3(1967),136-145.
[30]B.D. Mckay, Unpublished computer search for cyclic CI graphs.
[31]L. Babai, Isomorphism problem for a class of point-symmetric structure, Acta Math. Acad. Sci. Hungar 29 (1977),329-336.
[32]C.E. Praeger, Finite transitive permutation groups and finite vertex-transitive graphs, in Graph Symmetry:Algebraic Methods and Applications, NATO ASI Ser. C497 (1997),277-318.
[33]X.G. Fang, C.H. Li and M.Y. Xu, On edge-transitive Cayley graphs of va-lency four, European J. Combin.25(2004),1107-1116.
[34]J.X. Zhou and Y.Q. Feng, Two sufficient conditions for non-normal Caylay graphs and their applications, Sci. China Ser. A (50) (2) 2007,201-216.
[35]C.H. Li, Isomorphisms of finite Cayley graphs, Bull. Austral. Math. Soc.56 (1997),169-172.
[36]C.H. Li, On isomorphisms of connected Cayley graphs, II, J. Combin. Theory Ser. B 74 (1998) 28-34.
[37]M.Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Dis-crete Math.182(1998),309-319.
[38]S. J. Xu, The Nature of Non-weak 3-DCI in Frobenius Group with 3p Order, Guangxi Sci.7(2)(2000),115-117.
[39]方新贵,有限交换2-DCI-群的刻画,数学杂志,8(1988),315-317.
[40]徐尚进,李靖建,靳伟,等.qp阶亚循环群的弱q-DCI性,广西师范大学学报,25(2007),10-13.
[41]S.F. Du and M.Y. Xu, A classification of semi-symmetric graphs of order 2pq, Com. Algebra 25(2004),1107-1116.
[42]C.H. Li and C.E. Praeger, The finite simple groups with at most two fusion classes of every order, Comm. Algebra.24 (1996),3681-3704.
[43]Z.P. Lu, On the automorphism groups of Bi-Cayley graphs, Beijing Daxue Xuebao Ziran Kexue Ban 39(1) (2003),1-5.
[44]路在平,博士学位论文,北京大学,2003.
[45]靳伟,双Cayley图的若干性质,广西大学,2007.
[46]J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker and R.A. Wilson, Atlas of Finite Groups, Clarendon Press, Oxford,1985.
[47]徐尚进,覃建军,邓芸萍,4p阶二面体群的连通三度Cayley图,送审.
[48]C.E. Praeger, Highly arc transitive digraphs, European J. Combin.10 (1989) 281-292.
[49]D. Gorenstein, Finite Simple Groups, Plenum Press, New York,1982.