Independent Sets And Clique-Transversal In Regular Graphs

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.