The Decycling Number And Coloring Of Halin Graphs

The applications of graph in circuit design and in the prevention of deadlock in operating systems lead to the research on the problem of destroying all cycles in a graph by deleting a set of vertices and the edges which are adjacent to them. Because the decycling numbe is closely related to the size of the largest induced forest and the size of the biggest independent set, it is of great importance in graph theory. The research on the decycling number helps a lot to understand the properties and the structure of a graph.The coloring of graphs originated from the four-color theorem. There are several kinds of coloring of graphs such as proper vertex coloring, proper edge coloring, etc. The coloring of graphs is also of great importance in graph theory, because it is closely related to many practical problems, one of which is the task allocation, such as the allocation of goods.The two problems above are very important in graph theory, but it is a pity that people make little progress with general graphs, so more and more people begin their researches on special kinds of graphs and have made some progresses.According to the structural theorem of 3-connected graphs by Tutte:Every 3-connected graph can be obtained by splitting vertices of some wheel which is Halin graph. Thus, the study of the structure of Halin graph is very important.In this paper, we deal with the decycling number of the nearly κ-regular Halin graph, we get the bidirectional inequality that the decycling numbers of nearly regular Halin graphs must satisfy. Next, through structuring we prove the boundaries above are tight. Then we get the decycling number and the method to find out a specific minimum decycling set of two certain kinds of Halin graphs. At last, we give a new proof to the theorem about the (vertex) coloring of Halin graph[1] to which we apply the technique of the longest road.