English

运筹学学报 >

2019 , Vol. 23 >Issue 2: 113 - 119

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.02.011

运筹学

6-圈至多含一弦平面图的线性荫度

展开
  • 昌吉学院数学系, 新疆昌吉 831100

收稿日期: 2017-03-09

  网络出版日期: 2019-06-15

基金资助

新疆维吾尔自治区自然科学基金（Nos.2016D01C005，2016D01C012），新疆高校科研计划重点项目（No.XJEDU2014I046）

收起

The linear aboricity of planar graphs with 6-cycles containing at most one chord

Expand
  • Department of Mathematics, Changji University, Changji 831100, Xinjiang, China

Received date: 2017-03-09

  Online published: 2019-06-15

Fold

摘要

线性森林是指每个连通分支都是路的图.图G的线性荫度la（G）等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了，若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图，则la（G）=「△（G）/2」.

关键词： 圈; 平面图; 线性荫度; 权转移方法

本文引用格式

罗朝阳, 孙林 . 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019 , 23(2) : 113 -119 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.011

Abstract

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, using the discharging method, it is proved that for a planar graph G, la(G)=「△(G)/2」 if △(G) > 7 and every 6-cycle of G contains at most one chord.

Key words： cycle; planar graph; linear arboricity; discharging method

参考文献

[1] Bondy J A, Murty U S R. Graphs Theory with Applications[M]. London:Macmillan Press Ltd, 1979.
[2] Akiyama J, Exoo G, Harary F. Covering and packing in graphs Ⅲ:cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30:405-417.
[3] Péroche B. Complexity of the linear arboricity of a graph[J]. RAIRO Operations Research, 1982, 16:125-129.
[4] Enomoto H, Péroche B. The linear arboricity of some regular graphs[J]. Journal of Graph Theory, 1984, 8:309-324.
[5] Guldan F. The linear arboricity of 10-regular graphs[J]. Mathematica Slovaca, 1986, 36:225- 228.
[6] Guldan F. Some results on linear arboricity[J]. Journal of Graph Theory, 1986, 10:505-509.
[7] Wu J L. The linear arboricity of series-parallel graphs[J]. Graphs and Combinatorics, 2000, 16:367-372.
[8] Wu J L, Liu G Z, Wu Y L. The linear arboricity of composition graphs[J]. Journal of Systems Science and Complexity, 2002, 15:372-375.
[9] Harary F. Covering and packing in graphs I[J]. Annals New York Academy of Sciences, 1970, 175:198-205.
[10] Wu J L, Hou J F, Sun X Y. A note on the linear arboricity of planar graphs without 4- cycles[C]//The Eighth International Symposium on Operations Research and Its Applications (ISORA.09), Zhangjiajie:Hunan University, 2009:174-178.
[11] Chen H Y, Qi J M. The linear arboricity of planar graphs with maximum degree at least 5[J]. Information Processing Letters, 2012, 112:767-771.
[12] Cygan M, Hou J F, Kowalik L, et al. A planar linear arboricity conjecture[J]. Journal of Graph Theory, 2012, 60:403-425.
[13] Tan X, Chen H Y, Wu J L. The linear arboricity of planar graphs with maximum degree at least five[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2011, 34:541-552.
[14] Tan X, Chen H Y, Wu J L. The linear arboricity of planar graphs without 5-cycles and 6-cycles[J]. Ars Combinatoria, 2010, 97A:367-375.
[15] Wu J L. On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 1999, 31:129-134.
[16] Wu J L, Wu Y W. The linear arboricity of planar graphs of maximum degree seven is four[J]. Journal of Graph Theory, 2008, 58:210-220.
[17] Wu J L, Hou J F, Liu G Z. The linear of planar graphs with no short cycles[J]. Theoretical Computer Science, 2007, 381:230-233.
[18] Wang H J, Liu B, Wu J L. The linear arboricity of planar graphs without chordal short cycles[J]. Utilitas Mathematica, 2012, 87:255-263.
[19] Chen H Y, Tan X, Wu J L, et al. The linear arboricity of planar graphs without 5-, 6-cycles with chords[J]. Graphs and Combinatorics, 2013, 29:373-385.
[20] Chen X L, Wu J L. The linear arboricity of planar graphs without 5-cycles with two chords[J]. Filomat, 2016, 30:1134-1142.
Options
文章导航

/

〈 〉