关于4p~n阶3度对称图
|
摘要
一个图是对称的,如果它的自同构群作用在它的弧集上是传递的.设p为素数,n为正整数.本文主要研究了4pn阶3度对称图.在[J. Combin. TheoryB,97(2007)627-646.]中,Feng和Kwak利用图覆盖理论给出了4p2阶3度对称图的分类,本文通过分析图的自同构群给出了它分类的新证明.最近,在[Ars Combin., in press.]中,Zhou分类了4p3阶3度对称图,而本文刻画了4p4阶3度对称图的分类.作为结论,我们知道如果这样的图存在当且仅当p=2,5或者7.并且本文给出了4p4阶3度对称Cayley图的分类.最后,本文证明了当p≠5,7时,每一个4pn阶3度对称图都是Cayley图.
A graph is said to be symmetric if its automorphism group acts transitively on its arcs. Let p be a prime. In the thesis, we aim to investigate the cubic symmetric graph of order 4pn with n a positive integer. In [J. Combin. Theory B,97 (2007) 627-646.], by using graph covering theory, Feng and Kwak have classified cubic symmetric graphs of order 4p2. In this thesis, we give a new proof of this result by analyzing the automorphism groups of graphs. Recently, in [Ars Combin., in press.], Zhou classified cubic symmetric graph of order 4p3, and in this thesis, we give a characterization of cubic symmetric graphs of order 4p4. As a result, we know that such graph exist only when p= 2,5 or 7. Also, the classification of cubic symmetric Cayley graphs of order 4p4 is given. At last, we prove that if p≠5,7 then every cubic symmetric graph of order 4pn is a Cayley graph.
A graph is said to be symmetric if its automorphism group acts transitively on its arcs. Let p be a prime. In the thesis, we aim to investigate the cubic symmetric graph of order 4pn with n a positive integer. In [J. Combin. Theory B,97 (2007) 627-646.], by using graph covering theory, Feng and Kwak have classified cubic symmetric graphs of order 4p2. In this thesis, we give a new proof of this result by analyzing the automorphism groups of graphs. Recently, in [Ars Combin., in press.], Zhou classified cubic symmetric graph of order 4p3, and in this thesis, we give a characterization of cubic symmetric graphs of order 4p4. As a result, we know that such graph exist only when p= 2,5 or 7. Also, the classification of cubic symmetric Cayley graphs of order 4p4 is given. At last, we prove that if p≠5,7 then every cubic symmetric graph of order 4pn is a Cayley graph.
引文
[1]N. Biggs, Three remarkable graphs, Canad. J. Math.,25 (1973) 397-411.
[2]C.Y. Chao, On the classification of symmetric graphs with a prime number of vertices, Trans. Amer. Math. Soc.,158 (1971) 247-256.
[3]Y. Cheng, J. Oxley, On weakly symmetric graphs of order twice a prime, J. Combin. Theory Ser. B,42 (1987) 196-211.
[4]成会文,关于4p阶3度对称图的一点注记,科学技术与工程,9(2009)2073-2074.
[5]Hui-Wen Cheng, Note on cubic symmetric graphs of order 2pn, Austral. J. Combin.,47 (2010) 205-210.
[6]M. Conder, P. Dobcsanyi, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput.,40 (2002) 41-63.
[7]M.D.E. Conder, C.E. Praeger, Remarks on path-transitivity in finite graphs, European J. Combin.,17 (1996) 371-378.
[8]D.Z. Djokovic, G.L. Miller, Regular groups of automorphisms of cubic graphs, J. Combin. Theory B,29 (1980) 195-230.
[9]Y.-Q. Feng, J.H. Kwak, Classifying cubic symmetric graphs of order 10p or 10p2, Science in China A,49 (2006) 300-319.
[10]Y.-Q. Feng, J.H. Kwak, Cubic symmetric graphs of order twice an odd prime power, J. Austral. Math. Soc.,81 (2006) 153-164.
[11]Y.-Q. Feng, J.H. Kwak, Cubic symmetric graphs of order a small number times a prime or a prime square, J. Combin. Theory B,97 (2007) 627-646.
[12]Y.-Q. Feng, J.H. Kwak, K.S. Wang, Classifying cubic symmetric graphs of order 8p or 8p2, European J. Combin.,26 (2005) 1033-1052.
[13]Y.-Q. Feng, J.H. Kwak, M.X. Xu, Cubic s-regular graphs of order 2p3, J. Graph Theory,4 (2006) 341-352.
[14]贝.胡佩特,有限群论第一卷(第一分册),姜豪,俞曙霞译,福建人民出版社,1992.
[15]P. Lorimer, Vertex-transitive graphs:Symmetric graphs of prime valency, J. Graph Theory., 8 (1984) 55-68.
[16]R.C. Miller, The trivalent symmetric graphs of girth at most six, J. Combin Theory B,10 (1971) 163-182.
[17]J.M. Oh, A classification of cubic s-regular graphs of order 16p, Discrete Math.,309 (2009) 3150-3155.
[18]J.M. Oh, A classification of cubic s-regular graphs of order 14p, Discrete Math.,309 (2009) 2712-2726.
[19]C.E. Praeger, R.J. Wang, M.Y. Xu, Symmetric graphs of order a product of two distinct primes, J. Combin. Theory Ser. B,58 (1993) 299-318.
[20]C.E. Praeger, M.Y. Xu, Vertex-primitive graphs of order a product of two distinct primes, J. Combin. Theory Ser. B,59 (1993) 245-266.
[21]W.T. Tutte, A family of cubical graphs, Proc. Camb. Phil. Soc.,43 (1947) 621-624.
[22]W.T. Tutte, On the symmetry of cubic graphs, Canad. J. Math.,11 (1959) 621-624.
[23]W.T. Tutte, A non-Hamiltonian graph, Canad. Math. Bull.,3 (1960) 1-5.
[24]M.E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory,6 (1969) 152-164.
[25]J. Wang, The primitive permutation groups with an orbital of length 4, Communication in Algebral,20 (1992) 889-921.
[26]R.J. Wang, M.Y. Xu, A classification of symmetric graphs of order 3p, J. Combin. Theory Ser. B,58 (1993) 197-216.
[27]徐明曜,有限群导引(上,下册),第二版,北京,科学出版社,1999.
[28]J.X. Zhou, Cubic symmetric graphs of order 4p3, Ars Combin., in press.
[2]C.Y. Chao, On the classification of symmetric graphs with a prime number of vertices, Trans. Amer. Math. Soc.,158 (1971) 247-256.
[3]Y. Cheng, J. Oxley, On weakly symmetric graphs of order twice a prime, J. Combin. Theory Ser. B,42 (1987) 196-211.
[4]成会文,关于4p阶3度对称图的一点注记,科学技术与工程,9(2009)2073-2074.
[5]Hui-Wen Cheng, Note on cubic symmetric graphs of order 2pn, Austral. J. Combin.,47 (2010) 205-210.
[6]M. Conder, P. Dobcsanyi, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput.,40 (2002) 41-63.
[7]M.D.E. Conder, C.E. Praeger, Remarks on path-transitivity in finite graphs, European J. Combin.,17 (1996) 371-378.
[8]D.Z. Djokovic, G.L. Miller, Regular groups of automorphisms of cubic graphs, J. Combin. Theory B,29 (1980) 195-230.
[9]Y.-Q. Feng, J.H. Kwak, Classifying cubic symmetric graphs of order 10p or 10p2, Science in China A,49 (2006) 300-319.
[10]Y.-Q. Feng, J.H. Kwak, Cubic symmetric graphs of order twice an odd prime power, J. Austral. Math. Soc.,81 (2006) 153-164.
[11]Y.-Q. Feng, J.H. Kwak, Cubic symmetric graphs of order a small number times a prime or a prime square, J. Combin. Theory B,97 (2007) 627-646.
[12]Y.-Q. Feng, J.H. Kwak, K.S. Wang, Classifying cubic symmetric graphs of order 8p or 8p2, European J. Combin.,26 (2005) 1033-1052.
[13]Y.-Q. Feng, J.H. Kwak, M.X. Xu, Cubic s-regular graphs of order 2p3, J. Graph Theory,4 (2006) 341-352.
[14]贝.胡佩特,有限群论第一卷(第一分册),姜豪,俞曙霞译,福建人民出版社,1992.
[15]P. Lorimer, Vertex-transitive graphs:Symmetric graphs of prime valency, J. Graph Theory., 8 (1984) 55-68.
[16]R.C. Miller, The trivalent symmetric graphs of girth at most six, J. Combin Theory B,10 (1971) 163-182.
[17]J.M. Oh, A classification of cubic s-regular graphs of order 16p, Discrete Math.,309 (2009) 3150-3155.
[18]J.M. Oh, A classification of cubic s-regular graphs of order 14p, Discrete Math.,309 (2009) 2712-2726.
[19]C.E. Praeger, R.J. Wang, M.Y. Xu, Symmetric graphs of order a product of two distinct primes, J. Combin. Theory Ser. B,58 (1993) 299-318.
[20]C.E. Praeger, M.Y. Xu, Vertex-primitive graphs of order a product of two distinct primes, J. Combin. Theory Ser. B,59 (1993) 245-266.
[21]W.T. Tutte, A family of cubical graphs, Proc. Camb. Phil. Soc.,43 (1947) 621-624.
[22]W.T. Tutte, On the symmetry of cubic graphs, Canad. J. Math.,11 (1959) 621-624.
[23]W.T. Tutte, A non-Hamiltonian graph, Canad. Math. Bull.,3 (1960) 1-5.
[24]M.E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory,6 (1969) 152-164.
[25]J. Wang, The primitive permutation groups with an orbital of length 4, Communication in Algebral,20 (1992) 889-921.
[26]R.J. Wang, M.Y. Xu, A classification of symmetric graphs of order 3p, J. Combin. Theory Ser. B,58 (1993) 197-216.
[27]徐明曜,有限群导引(上,下册),第二版,北京,科学出版社,1999.
[28]J.X. Zhou, Cubic symmetric graphs of order 4p3, Ars Combin., in press.