【作者】 周垂香；

【导师】 冯衍全；

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

【摘要】 本文的主要内容分为两部分，前半部分是对4度半弧传递图的研究，后半部分是对整数流的研究。这两部分内容都与群论有密切的关系。半弧传递图与整数流理论这两个研究课题同为国际著名数学家Tutte（英国皇家学会会员）所开创。第一章引言中我们系统地介绍了群与图之间的联系。详细的描述了s-弧传递图（尤其是半弧传递图）的概念及研究进展。接下来我们对整数流的概念、问题的由来、著名的三大猜想以及一些已知的结论进行简单的阐述。半弧传递图的研究是由Tutte在1966年提出的，从此，4度半弧传递图的构造和刻画成为代数图论的一个活跃分支。4度半弧传递图方面的内容主要是借助群论的一些知识来构造半弧传递图并在某些条件下，给出4度半弧传递图的分类。这一部分内容主要集中在第二章至第四章。第二章主要构造了一类4度半弧传递图。本章的主要内容是把覆盖的理论作为工具，研究K_4，4的正则覆盖，并构造出一类无限族的4度半弧传递图。这类半弧传递图的半径为偶数且紧相关，它们不属于前人构造的任何一类4度半弧传递图。第三章给出了当保纤维自同构群包含一个半弧传递子群而且覆盖变换群为素数幂阶循环群时，K_4，4的4度半弧传递正则覆盖的分类。通过这种分类，我们构造了两类无限族的4度半弧传递图，它们是目前已知仅有的2幂阶4度半传递图无限类。第四章给出了4p阶4度半弧传递图的分类，同时，我们还证明：4p阶半弧传递图一定不是Cayley图。后五章主要围绕整数流理论，确切地说围绕Tutte的3-流猜想展开研究。Tutte3-流猜想已有五十多年历史，至今没有解决。本文考虑满足某些条件的三大类图，证明3-流猜想对这三类图成立。第五章给出了三角连通图的3-流存在性以及Z₃-流可收缩性的完全刻画。三角连通图是任意两条边均有连续的三角形相连的一类图。有了这个完全刻画的结果，很多已知结果的证明都可以大大简化。第六章刻画了在Ore-条件下3-流的存在性，除了六个特殊的图外，其它的图在Ore-条件下都能保证3-流的存在性。第七章则是应用第五章的成果来研究度数和与3-流存在性以及Z₃-流可收缩性的关系，并且得到一个图的每条边的两个端点度数和不小于顶点数时3-流存在的一个充要条件。当上面条件中的顶点数改为顶点数加2时这个条件则是保证Z₃-流可收缩性的一个充要条件（K₄除外）。第八章应用同样的方法研究最小度与3-流存在性的关系。事实上，从第七章的结论就可知如果一个图的最小度不小于顶点数的一半时，除了个别图外，都存在非零3-流。这里我们减弱了对最小度的要求，允许有两个点的度数小于顶点数的一半。除了八个小阶数的图之外，所有满足这一弱条件的图都有非零3-流。更多还原

【Abstract】 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.更多还原