Symmetry Of Graphs And Embeddings Of Graphs Into Surfaces

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).