【作者】 周进鑫；

【导师】 冯衍全；

【作者基本信息】 北京交通大学 ， 运筹学与控制论， 2008， 博士

【摘要】 本文主要研究群论在图论中的应用，内容主要涉及到代数图论（第二章至第八章）和拓扑图论（第九章至第十一章）两个研究领域．第一章是引言部分，主要介绍本文所要用到的一些有关群和图的基本概念，以及本文将要研究的问题、相关的背景知识和本文取得的相关成果．在第二章，我们给出了5度非正规Cayley图的两个充分条件．由此，构造了一些连通的5度非正规Cayley图的无限类，其中三类为非交换单群上的Cayley图．另外，我们还决定了A₅的所有连通5度非正规Cayley图，从而推广了徐明曜和徐尚进[Science in China A，47（2004）593-604]的关于A₅的连通3、4度Cayley图正规性结果．应用该结果，我们还决定了A₅的所有5度非CI Cayley图，而徐明曜等[Science in China A，44（2001）1503-1508]则证明A₅为4-CI群．在第三章，我们首先给出了阶为二倍的两个不同的奇素数乘积的连通3度对称图的分类，该结果和Feng等[J．Combin．Theory B，97（2007）627-646；J．Austral．Math．Soc．A，81（2006）153-164]的结果一起完成了阶为三个素因子的乘积的连通3度对称图的分类；其次，我们还给出了阶为三个素因子的乘积连通3度点传递的非Cayley图的分类；最后，通过决定2pq阶连通3度Cayley图的正规性，我们给出了2pq阶连通3度非对称Cayley图的分类，其中p，q为两个不同的奇素数．这样，本章完成了2pq阶连通3度点传递图的分类．在第四章，我们分类了M（o|¨）bius-Kantor图（即广义Petersen图GP（8，3））的边传递循环正则覆盖．作为应用，给出了16p阶3度对称图的分类，其中p为任一素数．第五、六、七章是关于具有某种对称性质的小度数图的分类的．第五章给出了二倍无平方因子阶的3度1-正则图的分类．第六章给出了2pq阶4度1-正则图的分类，其中p，q为任意素数．第七章给出了p⁴阶4度半传递图的分类．在第八章，我们研究了5度对称图的点稳定子群．给定图X，设G≤Aut（X），s≥1为整数．若G在X的s-弧集合上传递但在（s+1）-弧集合上非传递，则称图X为（G，s）-传递的；特别地，称（Aut（X），s）-传递图X为s-传递图．对任一连通5度（G，s）-传递图X，令G_v为顶点v∈V（X）在G中的点稳定子群．Weiss在文献[Math．Proc．Camb．Phil．Soc．，85（1979）43-48]中证明若G_v可解，则s≤3．在第八章，我们进一步证明当s=1时，G_v同构于Z₅，D₁₀或D₂₀；当s=2时，G_v同构于Frobenius群F₂₀或F₂₀×Z₂；当s=3时，G_v同构于F₂₀×Z₄．利用该结果，我们还证明了所有非交换单群上的连通5度1-传递Cayley图都是正规的．第九章是关于正则地图的．设p和q为素数，Du等在文献[J．AlgebraicCombin．，19（2004）123-141]中分类了以pq阶简单图为基图的正则地图．在第九章，我们分类了以4p阶简单图为基图的正则地图．这些地图包括12个零散的地图和六个无限类，其中两个无限类为以完全二部图K_2p,2p为基图的正则地图，另外四个无限类分别为群Z_4p，Z₂²×Z_p和D_4p上的正则平衡Cayley地图．最后两章是关于地图计数的．Mull等在文献[Proc．Amer．Math．Soc．，103（1988）321-330]中给出了一个地图的同构类的计数方法．利用该方法，他们计算了以完全图和轮图为基图的地图的同构类的个数．Mull在文献[J．Graph Theory，30（1999）77-90]中进一步发展了这个方法，并得到了以完全二部图为基图的地图的同构类的计数公式．在第十章，我们将Mull等的方法推广到允许有环和重边的连通图上，并给出了以两类著名图类：环束和双极图为基图的地图同构类的计数公式．称地图M为可反射的，若它同构于它的镜面影象．在第十一章，我们给出了可反射地图的同构类的一个计数方法，并将该方法应用到了完全图、环束、双极图和轮图等著名图类中．进一步，我们还证明了这些图的地图‘几乎’都是非可反射的，即为手性的（当顶点个数无限增长时）．更多还原

【Abstract】 This paper mainly investigates the application of group theory to graph theory. Some results related to algebraic graph theory （Chapters 2-8） and topological graph theory （Chapters 9-11） are obtained.In Chapter 1, some basic definitions in group theory and graph theory are first given. Then we introduce some research problems and the background regarding these problems, and the main work in this paper are also briefly introduced.In Chapter 2, two sufficient conditions for non-normal Cayley graphs are given and by using the conditions, several infinite families of non-normal Cayley graphs are constructed, of which three are Cayley graphs on the finite non-abelian simple groups. As an application, all connected non-normal Cayley graphs of valency 5 on A₅ are determined, which generalizes a result about the normality of Cayley graphs of valency 3 or 4 on A₅ determined by M.Y. Xu and S.J. Xu [Science in China A, 47 （2004） 593-604]. Further, we classify all non-CI Cayley graphs of valency 5 on A₅, while M.Y. Xu et al. [Science in China A, 44 （2001） 1503-1508] proved that A₅ is a 4-CI group.In Chapter 3, the classification of cubic symmetric graphs of order twice a product of two distinct odd primes is first given, and this together with Feng et al. [J. Combin. Theory B, 97 （2007） 627-646; J. Austral. Math. Soc. A, 81 （2006） 153-164] complete the classification of cubic symmetric graphs of order a product of three primes. In addition, all the connected cubic vertex-transitive non-Cayley graphs of order a product of three primes are also classified. At last, by determining the normality of connected cubic Cayley graphs of order 2pq, all the cubic non-symmetric Cayley graphs of order 2pq are classified, where p, q are two distinct odd primes. As a result, all the connected cubic vertex-transitive graphs of order 2pq are classified.In Chapter 4, the edge-transitive cyclic regular coverings of M（o|¨）bius-Kantor graph, that is, the generalized Petersen graph GP（8,3）, are classified and using this, we classify cubic symmetric graphs of order 16p, where p is a prime number.In Chapters 5-7, the small valent graphs with some symmetric properties are considered. Chapter 5 gives a classification of cubic one-regular graphs of order twice a squaxe free integer. Chapter 6 classifies all tetravalent one-regular graphs of order 2pq for any primes p and q. Chapter 7 gives a classification of tetravalent half-transitive graphs of order p⁴ for each prime p.In Chapter 8, the vertex stabilizers of symmetric graphs of valency 5 are considered. A graph X, with a subgroup G≤Aut（X）, is said to be （G,s）-transitive, for some s≥1, if G is transitive on s-arcs but not on （s+1）-arcs, and s-transitive if it is （Aut（X）,s）-transitive. For a connected （G, s）-transitive graph X of valency 5, let G_v be the stabilizer of a vertex v∈V（X） in G. Weiss [Math. Proc. Camb. Phil. Soc., 85 （1979） 43-48] proved that if G_v is solvable then s≤3 and in Chapter 8, it is proved that G_v is isomorphic to the cyclic group Z₅, the dihedral group D₁₀ or the dihedral group D₂₀ for s = 1, the Frobenius group F₂₀ or F₂₀×Z₂ for s = 2, or F₂₀×Z₄ for s=3. Using this, we prove that every connected 1-transitive Cayley graph of valency 5 on a non-abelian simple group is normal.Chapter 9 is about the regular maps. For two primes p and q, Du et al. [J. Algebraic Combin., 19 （2004） 123-141] classified the regular maps of graphs of order pq. In Chapter 9, all pairwise non-isomorphic regular maps of graphs of order 4p are constructed explicitly and the genera of such regular maps are computed. As a result, there are twelve sporadic and six infinite families of regular maps of graphs of order 4p; two infinite families are regular maps with the complete bipartite graphs K_2p,2p as underlying graphs and the other four infinite families are regular balanced Cayley maps on the groups Z_4p, Z₂²×Z_p and D_4p.The last two chapters are about the enumeration of maps. Mull et al. [Proc. Amer. Math. Soc., 103 （1988） 321-330] developed an approach for enumerating the isomorphism classes of maps of graphs, and by using this, they enumerated the isomorphism classes of maps of the complete graphs and the wheel graphs. The approach was further developed by Mull [J. Graph Theory, 30 （1999） 77-90] to obtain a formula for enumerating the isomorphism classes of maps of complete bipartite graphs. In Chapter 10, Mull et al.’s approach is generalized to any con-nected graph with loops or multiple edges, and by using this method, we enumerate the isomorphism classes of maps of a bouquet of circles and a dipole.A map is reflexible if it is isomorphic to its mirror image. In Chapter 11, we introduce a method for enumerating the isomorphism classes of reflexible maps of connected graphs, and apply it to the complete graphs, the bouquets of circles, the dipoles and the wheel graphs to count their isomorphism classes of reflexible or non-reflexible （called chiral） maps. Furthermore, it is proved that ’almost all’ maps of these graphs are chiral （when the number of vertices is growing）.更多还原