The Half-arc-transitive Graphs And Integer Flows

In this thesis, we concentrate on two subjects relating to group theory: tetravalent half-arc-transitive graphs and integer flows in graphs. These two fields are all initiated by the famous mathematician-Tutte (the member of Royal Society).In the first chapter, we introduce some definitions of group theory related to graphs, and give a brief introduction to the research of s-arc-transitive graphs (especially, half-arc-transitive graphs). Then we give an introduction to integer flows, and present some elementary properties of integer flows, together with some known results related to the famous flow conjectures of Tutte.The investigation of half-arc-transitive graphs was initiated by Tutte in 1966. Since then, constructing and characterizing tetravalent half-arc-transitive graphs has been an active topic in algebraic graph theory. In the next tree chapters, with tools from group theory, we construct some infinite families of tetravalent half-arc-transitive graphs, and under certain conditions, characterize tetravalent half-arc-transitive graphs.In the second chapter, by using covering theory, we construct an infinite family of tetravalent half-arc-transitive graphs, which are regular coverings of the complete bipartite graph K_4,4. Moreover, these graphs are tightly attached with even radius and do not belong to any previously known families of half-arc-transitive graphs.In the third chapter, we classify the connected half-arc-transitive regular coverings of the complete bipartite graph K_4,4, in which the covering transformation group is cyclic of prime-power order and the fibre-preserving group contains a half-arc-transitive subgroup. As a result, we obtain two new infinite families of tetravalent half-arc-transitive graphs of 2-power orders. These are the first known such graphs of 2-power orders, in which the smallest one has order 2⁷. Furthermore, these graphs are also tightly attached with even radius.In the forth chapter, we finish the classification of the tetravalent half-arc-transitive graphs of order 4p. Furthermore, it is shown that a half-arc-transitive graph of order 4p cannot be a Cayley graph.The last five chapters are devoted to the study of integer flows, more precisely, to the existence of nowhere-zero 3-flows in some classes of graphs. Tutte's 3-flow conjecture is still open and believed to be very difficult. We shall focus on Tutte's 3-flow conjecture for some graphs that satisfy certain conditions.In the fifth chapter, we completely characterize the triangularly connected graphs which are Z₃-flow contractible or have a nowhere-zero 3-flow. With these characterizations, we simplify the proofs of several known results. It was conjectured that a 4-edge-connected graph with every edge in a triangle has a nowhere-zero 3-flow. Our result is a significant step towards a proof of the conjecture.In the sixth chapter, we show that with six exceptions, all the graphs on n vertices, in which d(x) + d(y) ≥ n for every pair of nonadjacent vertices x and y, have a nowhere-zero 3-flow.In the seventh chapter, we prove that with completely described exceptions, all the graphs on n vertices, in which d(x) + d(y) ≥ n for every edge xy, have a nowhere-zero 3-flow. We also study the Z₃-flow contractibility, and prove that if G is a graph on n vertices, in which d(x) + d(y) ≥ n + 2 for every edge xy, then G is Z₃-flow contractible, unless G is K₄.In the eighth chapter, we continue our study of the connection between the degrees of a graph and the existence of nowhere-zero 3-flows. By refining previous arguments, we relax the degree requirements to allow at most two vertices in the graph to have small degrees.