Halin 图的消圈数及点染色问题的研究

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名

邮箱

手机号码

标题

留言内容

验证码

基金项目:

国家自然科学基金(11171114); 上海市自然科学基金(13dz2260400)

The decycling number and vertex coloring of Halin graphs

1.
Department of Mathematics, East China Normal University, Shanghai 200241, China

摘要: Tutte关于3-连通图的结构定理表明: 每一个3-连通图都可由某个轮图(也是 Halin图)经顶点分裂逐步得到. 这表明了Halin图在图结构研究中的地位和作用. 首先研究得到了近正则Halin图的消圈数的上、下界并证明了上述界是紧的, 接着得到了最大度为k 或最小度为k 的 Halin图的消圈数所满足的界; 此外还研究了Halin图的点染色问题, 给出了它的点色数定理的一个新证明.
- 近正则Halin图 /
- 最小消圈集 /
- 消圈数 /
- 点色数
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.
- nearly regular Halin graph minimum decycling set decycling number number of vertex coloring /

[1]	[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.

点击查看大图