On Semisymmetric Graphs That Admits Primitive Groups

This thesis is a contribution to the study of semisymmetric graphs.Classifying and constructing graphs with various transitive properties, such as the vertex-transitivity, edge-transitivity and arc-transitivity etc., is a very im-portant and active topic in algebraic graph theory. In the present thesis, we investigate edge-transitive graphs, especially those graphs which are regular and not vertex-transitive, called semisymmetric graphs. The class of semisymmetric graphs was introduced by Folkman. In1967, he constructed several infinite fam-ilies of such graphs and proposed eight open problems. These problems received considerable attentions and lots of researchers began to work on this kind of graphs. In the past few decades, many meaningful results had been found, main-ly related to the classification problem under certain restrictions, the structure of the stabilizer and the construction of new graphs, etc..Our main purpose is to classify semisymmetric graphs under some given con-ditions and construct new examples. Of course, for both of them, one key problem is to determine whether or not an edge-transitive graph is vertex-transitive. This problem is associated with the major project of our work. Therefore, to a great extent, one of our main tasks is to solve this problem under certain restrictions.The corpus part of this thesis includes four chapters except Chapters1and2. In the first chapter, we give some background information on the study of semisymmetric graphs and an overview of the main results achieved in this thesis. For convenience, we collect in Chapter2some concepts, terminologies, symbols and necessary group-theoretical results that are closely related to our research.In Chapter3, we analyze edge-transitive bipartite graphs that admit a quasiprim-itive group. Let Γ be a connected G-semisymmetric graph with bipartition sub-sets U and W, where G≤AutΓ. Assume that G induces a quasiprimitive permutation group on U, and that Γ is not a complete bipartite graph. By an easy observation, we can conclude that G is faithful on W. If G is also faithful on U, then Γ is isomorphic to a bicoset graph of G, and we can get all possible candidates for Γ by analyzing the orbits of the stabilizer in G of a given vertex acting on the other part of Γ. In this case, using group-theoretical methods or some combinatorial techniques, we may determine whether or not there is an au-tomorphism of Γ which interchanges two parts of Γ. This is one of the main ideas that will be used in our work. Especially when GU is of affine type, we prove that Γ is semisymmetric if and only if the socle soc(G) is intransitive on W. Using this result, we give a new construction of semisymmetric graphs from affine primitive graphs, and then lots of new examples of semisymmetric graphs. In addition, this method also leads to an interesting fact. We find that some complete bipartite graphs have edge-disjoint factorizations into semisymmetric graphs, which also attracted us and will become a focus of our future work. For the case where G is faithful on W but not on U, we prove that Γ is semisymmetric if GU is primitive. This leads to another way to construct semisymmetric graphs from primitive per-mutation groups. In particular, we find a great number of semisymmetric graphs can be constructed from the subdivisions of edge-primitive graphs. The above analysis and results provide us with some effective theoretical tools and methods for the classification of semisymmetric graphs under certain restrictions.For the classification problem of semisymmetric graphs, one feasible way is to restrict the order or the valency of the graphs. The last three chapters provide us with a solid theoretical foundation to classify semisymmetric graphs of order2pqr in the near future.Constructing new examples of semisymmetric graphs is a question of interest to us. Employing the results and methods given in Chapter3, we construct a number of new semisymmetric graphs in Chapter4. In chapter5, we firstly give a classification of primitive groups of degree pqr, where p, q and r are primes (not necessarily different). Then basing on the results in Chapter3, we give a classification of the semisymmetric graphs arising from primitive groups of degree pqr, which include9infinite families and a certain number of sporadic examples. In chapter6, we concentrate our attention on analyzing the locally primitive graphs of order18p. Using the results given in Chapter5and the technique of taking quotient graphs, we prove that the graph Γ is either arc-transitive or isomorphic to one of the Gray graphs and the Tutte12-cage.