Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2020, Vol. 49(4): 401-405
研究论文
Halin图的线性$k$-点荫度
The Linear $k$-vertex-arboricity of Halin Graph

黄丹君1,*, 王阳2,**
HUANG Danjun, WANG Yang

浙江师范大学数学系, 金华, 浙江,321004
Department of Mathematics, Zhejiang Normal University, Jinhua, Zhejiang, 321004, P. R. China

收稿日期: 2019-06-05
出版日期: 2020-08-11
2020, Vol. 49(4): 401-405
DOI: 10.11845/sxjz.2019064b


PDF
[256 KB]
69
下载
161
浏览

引用导出
0
    /   /   推荐

摘要 图$G$的线性点荫度$vla(G)$是指$V(G)$的最小划分数,使得每个点划分集的导出子图为线性森林.$G$的线性$k$-点荫度$vla_{k}(G)$是指$V(G)$的最小划分数,使得每个点划分集的导出子图的每个连通分支为长度至多为$k$的路. 1998年,吴建良证明了Halin图的线性点荫度为2. 本文在此基础上,证明了对Halin图$G$, 有$vla_{k}(G)=2$, 其中$k=\max \{{\lceil{\frac{\Delta-2}{2}}\rceil}, 3\}$.
关键词 Halin图线性点荫度线性$k$-点荫度    
Abstract:The linear vertex-arboricity $vla(G)$ of a graph $G$ is the minimum number of subsets into which $V(G)$ can be partitioned so that each subset induces a linear forest. The linear $k$-vertex-arboricity $vla_{k}(G)$ of a graph $G$ is the minimum number of subsets into which $V(G)$ can be partitioned so that the component of the induced subgraph of each subset is a path with length at most $k$. In 1998, Wu proved that the linear vertex-arboricity of Halin graph is at most 2. Based on this result, we prove that for Halin graph $G$, $vla_{k}(G)=2$, where $k=\max \{{\lceil{\frac{\Delta-2}{2}}\rceil},3\}$.
Key wordsHalin graph    linear vertex-arboricity    linear $k$-vertex-arboricity
PACS:  O157.5  
基金资助:浙江省自然科学基金(No.LY18A010014).
通讯作者: E-mail: * hdanjun@zjnu.cn; ** 457412583@qq.com   
[1] Akiyama J., Era H., Gervacio S.V. and Watanabe M., Path chromatic numbers of graphs, J. Graph Theory, 1989, 13(5): 569-575.
[2] Appel, K. and Haken, W., Every planar map is four colorable, part I. Discharging, Illinois J. Math., 1977, 21(3): 429-490.
[3] Appel, K. and Haken, W., Every planar map is four colorable, part II. Reducibility, Illinois J. Math., 1977, 21(3): 491-567.
[4] Axenovich M., Ueckerdt T. and Weiner P., Splitting planar graphs of girth $6$ into two linear forests with short paths, J. Graph Theory, 2017, 85(3): 601-618.
[5] Matsumoto M.,Bounds for the vertex linear arboricity, J. Graph Theory, 1990, 14(1): 117-126.
[6] Poh K.S.,On the linear vertex-arboricity of a planar graph, J. Graph Theory, 1990, 14(1): 73-75.
[7] Wu J.L.,Path decompositions of Halin graph, J. Shandong Mining Institute, 1998, 1: 94-98 (in Chinese).
[1] 于桂海, 侯耀平, 曲慧. 完全图的单钩immanant[J]. 数学进展, 2019, 48(6): 692-698.
[2] 覃荣存, 赵恒明. 通过半循环可分组设计构造变重量光正交码[J]. 数学进展, 2019, 48(6): 699-711.
[3] 卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155.
[4] 任秀秀,杨卫华. 几类特殊有向循环图的核[J]. 数学进展, 2019, 48(2): 137-144.
[5] 石慧苓, 高云澍. 标准多重图中点不交的重边四边形[J]. 数学进展, 2018, 47(3): 348-362.
[6] 卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372.
[7] 邓兴超, 宋贺, 苏贵福, 田润丽. 小直径二连通外平面图的彩虹连通数[J]. 数学进展, 2018, 47(3): 373-382.
[8] 田方. 一类稀疏随机图的距离匹配数[J]. 数学进展, 2018, 47(2): 175-188.
[9] 朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681.
[10] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.
[11] 单治超. 有限随机图上的随机游动和传染病模型[J]. 数学进展, 2017, 46(1): 1-12.
[12] 王力工, 孙丰妹. 单圈图的无符号拉普拉斯埃斯特拉达指数[J]. 数学进展, 2017, 46(1): 47-54.
[13] 冯荣权, 曾丽伟. 有向强正则图及其构造[J]. 数学进展, 2016, 45(6): 817-839.
[14] 崔淑玉,田贵贤. 图的各类矩阵表示的谱半径的界[J]. 数学进展, 2016, 45(5): 711-720.
[15] 李玉萍, 孟吉翔, 孙星红. 极大非正则图的边数[J]. 数学进展, 2016, 45(5): 721-726.
Viewed
Full text


Abstract

Cited

  Discussed   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .