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

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2015, Vol. 44(6): 865-870
研究论文
关于2-边连通3正则图荫度的一个注
A Note on Arboricity of 2-edge-connected Cubic Graphs

郝荣霞1, 赖虹建2,3,刘浩洋4
HAO Rongxia1, LAI Hongjian2,3, LIU Haoyang4

1. 北京交通大学数学系, 北京, 100044;
2. 新疆大学数学与系统科学学院, 乌鲁木齐, 新疆, 830046;
3. 西弗吉尼亚大学数学系, 摩根城, WV 26506-6310, 美国;
4. 北京大学数学科学学院, 北京, 100871
1. Department of Mathematics,Beijing Jiaotong University, Beijing, 100044, P. R. China;
2.College of Mathematics and System Sciences, Xinjiang University,Urumqi, Xinjiang, 830046, P. R. China;
3. Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310,USA;
4. School of Mathematical Sciences, Peking University,Beijing, 100871, P. R. China

收稿日期: 2014-04-06
2015, Vol. 44(6): 865-870
DOI: 10.11845/sxjz.2014056b


PDF
[200 KB]
806
下载
546
浏览

引用导出
E-mail这篇文章
E-mail提醒
RSS订阅

摘要 图G的点荫度$a(G)$是$G$的使得每个子集诱导一个森林的顶点划分中子集的最少个数.我们熟知对任何平面图$G$, $a(G)\leq 3$,且对任何直径最大是2的平面图有$a(G)\leq 2$. 文献[ European J.Combin., 2008, 29(4): 1064-1075]中给出下列猜想: 任何没有3-圈的平面图都有一个顶点的划分$(V_1,V_2)$使得$V_1$是独立集, $V_2$诱导一个森林.本文证明了任何2-边连通上可嵌入的3-正则图$G$ ($G\neq K_4$) 都有一个顶点的划分$(V_1,V_2)$使得$V_1$是独立集, $V_2$诱导一个森林.
Abstract:The vertex-arboricity $a(G)$ of a graph $G$ is the minimum number of subsets into which the set of vertices of $G$ can be partitioned so that each subset induces a forest. It is well known that $a(G)\leq 3$ for any planar graph $G$, and that $a(G)\leq 2$ for any planar graph $G$ of diameter at most 2. The conjecture that every planar graph $G$ without 3-cycles has a vertex partition $(V_1,V_2)$ such that $V_1$ is an independent set and $V_2$ induces a forest was given in \emph{European J. Combin.}, 2008, 29(4): 1064-1075]. In this paper, we prove that a 2-edge-connected cubic graph which satisfies some condition has this partition. As a corollary, we get the result that every up-embeddable 2-edge-connected cubic graph $G$ ($G\neq K_4$) has a vertex partition $(V_1,V_2)$ such that $V_1$ is an independent set and $V_2$ induces a forest.
PACS:  O157.5  
[1] Borodin, O.V. and Ivanova, A.O., Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable, J. Graph Theory}, 2009, 62(3): 234-240.
[2] Borodin, O.V., Kostochka, A.V. and Toft, B., Variable degeneracy: extensions of Brooks' and Gallai's theorems, Discrete Math., 2000, 214(1/2/3): 101-112.
[3] Catlin, P.A. and Lai, H.-J., Vertex arboricity and maximum degree, Discrete Math., 1995, 141(1/2/3): 37-46.
[4] Chang, G.J., Chen, C.Y. and Chen, Y.P., Vertex and tree arboricities of graphs, J. Comb. Optim., 2004, 8(3): 295-306.
[5] Chartrand, G. and Kronk, H.V., The point-arboricity of planar graphs, J. Lond. Math. Soc.} (1}), 1969, 44(1): 612-616.
[6] Chartrand, G., Kronk, H.V. and Wall, C.E., The point-arboricity of a graph, Israel J. Math., 1968, 6(2): 169-175.
[7] Chen, Z.Z. and He, X., Parallel complexity of partitioning a planar graph into vertex-induced forests, Discrete Appl. Math., 1996, 69(1/2): 183-198.
[8] Huang, Y.Q. and Liu, Y.P., Extensions on 2-edge connected 3-regular up-embeddable graphs, Acta Math. Appl. Sin.} Engl. Ser.}, 1998, 14(4): 337-346.
[9] Kronk, H.V. and Mitchcm, J., Critical point arboritic graphs, J. Lond. Math. Soc.} (2}), 1975, 9(3): 459-466.
[10] L\"{u}, S.X., On maximum genus and other invariants of graphs, Ph.D. Thesis, Beijing: Beijing Jiaotong University, 2010.
[11] Raspaud, A. and Wang, W.F., On the vertex-arboricity of planar graphs, European J. Combin., 2008, 29(4): 1064-1075.
[12] Roychoudhury, A. and Sur-Kolay, S., Efficient algorithms for vertex arboricity of planar graphs, In: Foundations of Software Technology and Theoretical Computer Science (Thiagarajan, P.S. ed.), Lecture Notes in Comput. Sci., Vol. 1026, 1995, 37-51.
[13] \v{S}krekovski, R., On the critical point-arboricitygraphs, J. Graph Theory}, 2002, 39(1): 50-61.
[14] Yang, A.F. and Yuan, J.J., On the vertex arboricity of planar graphs of diameter two, Discrete Math., 2007, 307(19/20):2438-2447.
[1] 周倩楠, 王力工, 卢勇. 关于哈密顿图和可迹图的一些充分条件[J]. 数学进展, 2018, 47(1): 31-40.
[2] 文飞, 黄琼湘, 马小玲. 一类图的谱半径与特征多项式[J]. 数学进展, 2018, 47(1): 41-50.
[3] 李建喜, 常安. 图的规范拉普拉斯特征值的上界[J]. 数学进展, 2018, 47(1): 51-55.
[4] 潘文华, 徐常青. 无$K_4$-图子式的图的邻和可区别边染色[J]. 数学进展, 2017, 46(6): 839-847.
[5] 刘颖, 沈建. 关于图的规范拉普拉斯特征值和的若干结果[J]. 数学进展, 2017, 46(6): 848-856.
[6] 朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681.
[7] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.
[8] 单治超. 有限随机图上的随机游动和传染病模型[J]. 数学进展, 2017, 46(1): 1-12.
[9] 王力工, 孙丰妹. 单圈图的无符号拉普拉斯埃斯特拉达指数[J]. 数学进展, 2017, 46(1): 47-54.
[10] 冯荣权, 曾丽伟. 有向强正则图及其构造[J]. 数学进展, 2016, 45(6): 817-839.
[11] 崔淑玉,田贵贤. 图的各类矩阵表示的谱半径的界[J]. 数学进展, 2016, 45(5): 711-720.
[12] 李玉萍, 孟吉翔, 孙星红. 极大非正则图的边数[J]. 数学进展, 2016, 45(5): 721-726.
[13] 单治超. 有限图上首达时等随机变量的极限定理[J]. 数学进展, 2016, 45(4): 481-490.
[14] 李晓艳,陈敏,王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499.
[15] 姚京京, 邵泽玲, 徐常青. \mbox{\boldmath $\Delta=3$} 的图的邻和可区别全可选性[J]. 数学进展, 2016, 45(3): 343-348.
Viewed
Full text


Abstract

Cited

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


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