收稿日期: 2015-07-06
网络出版日期: 2017-01-13
基金资助
国家自然科学基金(11171114); 上海市自然科学基金(13dz2260400)
The decycling number and vertex coloring of Halin graphs
Received date: 2015-07-06
Online published: 2017-01-13
王永强 , 任韩 . Halin 图的消圈数及点染色问题的研究[J]. 华东师范大学学报(自然科学版), 2016 , 2016(6) : 65 -70 . DOI: 10.3969/j.issn.1000-5641.2016.06.006
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.
[1]BONDY J A, MURTY U S R. Graph Theory with Applications [M]. New York: Macmillan Press Ltd, 1976.
[2] 李鸿祥, 张忠辅, 张建勋. Halin图的色性[J]. 上海铁道学院学报,1994(1): 19-24.
[3] 庄翠花. 几类图的消圈数问题[D]. 上海: 华东师范大学数学系, 2014.
/
〈 |
|
〉 |