最大平均度不超过4的图的线性2-荫度

doi:10.6040/j.issn.1671-9352.0.2017.286

山东大学学报（理学版） ›› 2018, Vol. 53 ›› Issue (6): 7-10.doi: 10.6040/j.issn.1671-9352.0.2017.286

最大平均度不超过4的图的线性2-荫度

张江悦,徐常青^*

河北工业大学理学院, 天津 300401

收稿日期:2017-06-06 出版日期:2018-06-20 发布日期:2018-06-13
作者简介:张江悦(1994— ), 女, 硕士研究生, 研究方向为图论. E-mail:jyzhyuer@163.com*通信作者简介:徐常青(1970— ), 女, 教授, 硕士生导师, 研究方向为图论. E-mail:chqxu@hebut.edu.cn
基金资助:
国家自然科学基金资助项目(11671232);河北省自然科学基金资助项目(A2015202301);河北省高等学校科学技术研究重点项目(ZD2015106)

Linear 2-arboricity of graphs with maximum average degree at most 4

ZHANG Jiang-yue, XU Chang-qing^*

School of Science, Hebei University of Technology, Tianjin 300401, China

Received:2017-06-06 Online:2018-06-20 Published:2018-06-13

摘要/Abstract

摘要： 一个2-线性森林是指每个分支均为长至多为2的路的图。将图G的边集合划分为m个线性2-森林的最小整数m,称为图G的线性2-荫度,记作la₂(G)。确定了mad(G)≤4的图的线性2-荫度的上界,若图G为mad(G)≤4的图,则la₂(G)≤「Δ(G)/2+5(Δ(G)≡1,2(mod 4)); la₂(G)≤「Δ(G)/2+4(Δ(G)≡0,3(mod 4))。

关键词: 最大平均度, 线性2-荫度, 线性森林

Abstract: A linear 2-forest is a graph whose components are paths of length at most 2. The linear 2-arboricity of a graph G is the least integer m such that G can be partitioned into m linear 2-forests, denoted by la2(G). The upper bound of the linear 2-arboricity of graph G with mad(G)≤4 is determined and if G is a graph with mad(G)≤4, then la₂(G)≤「Δ(G)/2+5 if Δ(G)≡1,2(mod 4)and la₂(G)≤「Δ(G)/2+4 if Δ(G)≡0,3(mod 4).

Key words: maximum average degree, linear forest, linear 2-arboricity

中图分类号:

O157

张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报（理学版）, 2018, 53(6): 7-10.

ZHANG Jiang-yue, XU Chang-qing. Linear 2-arboricity of graphs with maximum average degree at most 4[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 7-10.

参考文献

[1] AKIYAMA J. Three developing topics in graph theory[D]. Tokyo: University of Tokyo, 1980.
[2] AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs. III: Cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30(4):405-417.
[3] AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs IV: Linear arboricity[J]. Networks, 1981, 11(1):69-72.
[4] ENOMOTO H, PÉROCHE B. The linear arboricity of some regular graphs[J]. Journal of Graph Theory, 2010, 8(2):309-324.
[5] GULDAN F. The linear arboricity of 10-regular graphs[J]. Mathematica Slovaca, 1986, 36(3):225-228.
[6] WU J L. On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 2015, 31(2):129-134.
[7] LIH K W, TONG L D, WANG W F. The linear 2-arboricity of planar graphs[J]. Graphs & Combinatorics, 2003, 19(2):241-248.
[8] 徐常青,安丽莎,杜亚涛.平面图线性2-荫度的一个上界[J]. 山东大学学报(理学版), 2014, 49(4): 38-40. XU Changqing, AN Lisha, DU Yatao. An upper bound on the linear 2-arboricity of planar graph[J]. Journal of Shandong University(Natural Science), 2014, 49(4):38-40.
[9] WANG Y Q. Improved upper bound on the linear 2-arboricity of planar graphs[J]. Discrete in Mathematics, 2016, 339(1):39-45.
[10] XU C Q, CHANG J J. The linear 2-arboricity of some planar graphs[J]. Ars Combinatoria, 2014, 114:223-227.
[11] 吴建良. 图的最大平均度与线性萌度的关系[J]. 山东大学学报(理学版),2005,40(6):27-30. WU Jianliang. The relationship between the maximum average degree and the linear arboricity of a graph[J]. Journal of Shandong University(Natural Science), 2005, 40(6):27-30.
[12] CHEN B L, FU H L, HUANG K C, et al. Decomposing graphs into forests of paths with size less than three[J]. Australasian Journal of Combinatorics, 1991, 3:55-73.
[13] BERMOND J C, FOUQUET J L, HABIB M, et al. On linear k-arboricity[J]. Discrete Mathematics, 1984, 52(2):123-132.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

最大平均度不超过4的图的线性2-荫度

Linear 2-arboricity of graphs with maximum average degree at most 4

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

多维度评价

本文评价

推荐阅读 0

[1]	潘文华,徐常青. 一类稀疏图的邻和可区别边色数[J]. 山东大学学报（理学版）, 2017, 52(8): 94-99.
[2]	陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[3]	姚京京, 徐常青. 最大度为3或4的图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2015, 50(02): 9-13.
[4]	陈宏宇1, 张丽2. 不含弦5-圈和弦6-圈的平面图的线性2荫度[J]. 山东大学学报（理学版）, 2014, 49(06): 26-30.
[5]	徐常青1,安丽莎1,杜亚涛2. 平面图线性2-荫度的一个上界[J]. 山东大学学报（理学版）, 2014, 49(04): 38-40.
[6]	张欣1,徐兰2，刘桂真1. 稀疏图的k-森林染色[J]. J4, 2011, 46(4): 1-3.