Abstract:

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, which indicates that the study of the structure of Halin graph is important in graph structures. In this paper, firstly we dealt with the decycling number of the nearly k-regular Halin graphs, and we got the bidirectional inequality that the decycling numbers of nearly regular Halin graphs must satisfy, then we proved that the boundaries above are tight and got the boundaries of Halin graphs with the most biggest degree or the least degree k. At last, we gave a new proof to the theorem about the (vertex) coloring of Halin graphs.

Key words: nearly regular Halin graph, minimum decycling set, decycling number, number of vertex coloring