【作者】 汪定国；

【导师】 康丽英；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2013， 博士

【摘要】 随着时代的进步以及计算机科学的高速发展,图论在实际中的应用越来越广泛,关于图论的研究也就具有重要的现实意义.在图论中,由于受到来自不同领域的实际问题的驱动和对图的结构分析的需要,产生了许多图参数,这些图参数不仅在图的理论研究中占有重要的地位,同时又与图的应用密不可分.因此,图参数的研究始终是图论中最重要的研究内容.本文主要对具有较小度数的正则图,研究了其独立数和团横贯数并刻画了相应的极值图.其次,还讨论了它们的割边、割点和匹配数.其主要结果可以概括如下：·在第二章,我们首先利用数学归纳法对2-连通不含4阶完全子图的无爪4-正则图的独立数给出了一个确定的值；(相关结果发表在《Taiwanese J.Math.》上).然后利用线图的相关知识得到了连通不含4阶完全子图的无爪4-正则图的独立数的下界及极值图的刻画.·在第三章,我们首先对于2-连通不含4阶完全子图的无爪4-正则图的团横贯数呈现了一个确定的值；(相关结果被《Acta Math.Sin.(Engl.Ser.)》录用).接着,我们研究了3-正则图的线图的团横贯数的上界与达到该上界的极值图的刻画,利用这个结果自然而然的得出了连通不含4阶完全子图的无爪4-正则图的团横贯数的上界与极值图的刻画；最后我们研究了连通无三角形的3-正则图的匹配数的下界以及达到该下界的极值图,并根据该结果对连通无三角形的3-正则图的线图的团横贯数给出了一个上界并刻画了达到这个上界的极值图.·在第四章,我们主要研究了正则图的有关最大团横贯数的取值情况.首先对团数为k的k-正则图的最大团横贯数的上界、无爪3-正则图的最大团横贯数的下界以及达到相应界的极值图的刻画进行了讨论；接着讨论了团数至少为3的任意图的符号最大团横贯数的紧的下界、团数为k的k-正则图的符号最大团横贯数的上界与极值图的刻画、无爪3-正则图的符号最大团横贯数的下界与极值图的刻画、不含4阶完全子图的无爪4-正则图的符号最大团横贯数的上界与下界及达到下界的极值图的刻画；(相关结果发表在《Int.J.Comput.Math.》上).最后对团数至少为3的任意图的减最大团横贯数的下界与团数为k的k-正则图的减最大团横贯数的上界进行了讨论.·在第五章,我们主要研究了一般4-正则图、无爪4-正则图、不含4阶完全子图的无爪4正则图的末块数与割点数的上界与极值图的刻画,(相关结果已被《Discuss. Math.Graph Theory》录用).同时,对于无三角形的3-正则图的割边数,我们给出了一个上界并刻画了达到这个上界的极值图.更多还原

【Abstract】 As time progresses and computer science rapidly develop, the graph theory is widely used in practice, and so the study to it has great realistic significance. In graph theory, due to the drive by practical problems from different fields and the need for the structure analysis of the graph, many graph parameters emerged. The graph parameters not only play important role in the theory research of graph, but also go inseparable from the application of graph. Therefore, the research on graph parameters is always the most important research in graph theory.In this thesis, for the regular graph with a smaller degree, we investigate its independence number and clique-transversal number, and we characterize the extremal graphs accordingly. Meanwhile, we study its cut-edges, cut-vertices and matching number. The main results can be generalize as the following:In Chapter2, firstly, we give an exactly value on the independence number for2-connected claw-free4-regular graphs without complete subgraph of order4by applying mathematical induction. Secondly, we get the lower bound and the characterization of extremal graphs achieving the bound on the independence number for connected claw-free4-regular graphs without complete subgraph of order4by applying the related knowledge of line graph.In Chapter3, firstly, we present an exactly value on the clique-transversal number for2-connected claw-free4-regular graphs without complete subgraph of order4. In the following, we investigate the upper bound on the clique-transversal number for the line graphs of cubic graphs and the characterization of extremal graphs achieving the bound. As a natural result, we get the upper bound and the characterization of extremal graphs achieving the bound on the clique-transversal number for connected claw-free4-regular graphs without complete subgraph of or-der4. At last, we investigate the lower bound and the characterization of extremal graphs achieving the bound on the matching number for connected triangle-free cu-bic graphs. By this result, we get an upper bound on the clique-transversal number of the line graphs of connected triangle-free cubic graphs and we characterize the extremal graphs achieving the upper bound.In Chapter4, we consider the range of the maximum-clique transversal num-ber for regular graphs. First, we discuss the upper bound on the maximum-clique transversal number for the k-regular graphs of clique number k, the lower bound on the maximum-clique transversal number for the claw-free cubic graphs and the characterization of extremal graphs. Next, we investigate the tight lower bound on the signed maximum-clique transversal number for arbitrarily graph with the clique number at least3, the upper bound on the signed maximum-clique transver-sal number for the k-regular graphs of clique number k and the characterization of extremal graphs, the lower bound on the signed maximum-clique transversal num-ber for the claw-free cubic graphs and the characterization of extremal graphs, the tight upper bound and the lower bound on the signed maximum-clique transversal number for the claw-free4-regular graphs without complete subgraph of order4and the characterization of extremal graphs achieving the the lower bound. Finally, we discuss the lower bound on the minus maximum-clique transversal number for arbitrarily graph with clique number at least3and the upper bound on the minus maximum-clique transversal number for the k-regular graphs of clique number k.In Chapter5, we investigate the upper bounds on the end-blocks number and cut-vertices number for4-regular graphs, claw-free4-regular graphs, claw-free4-regular graphs without complete subgraph of order4, respectively, and characterize the extremal graphs achieving these bounds. Meanwhile, for the cut-edges number of the triangle-free cubic graphs, we give the upper bound, and characterize the extremal graphs achieving this bound.更多还原