Journal of East China Normal University(Natural Science) >

2015 , Vol. 2015 >Issue 1: 131 - 135

DOI: https://doi.org/10.3969/j.issn.1000-5641.2015.01.016

Article

The linear arboricity of upper-embedded graph and secondary upper-embedded graph

  • 吕Chang-Qing
Expand
  • School of Mathematics and Statistics, Zaozhuang University, Zaozhuang Shandong, 277160, China

Received date: 2014-04-01

  Online published: 2015-03-29

Fold

Abstract

The linear arboricity of a graph $G$ is the minimum number of linear forests which partition the edges of $G$. In the present, it is proved that if a upper-embedded graph $G$ has $\Delta\geqslant 3\sqrt{4-3\varepsilon}$  then its linear arboricity is $\lceil\frac{\Delta}{2}\rceil$\,and if a secondary upper-embedded graph $G$ has $\Delta\geqslant 6\sqrt{1-\varepsilon}$ then its linear arboricity is $\lceil \frac{\Delta}{2}\rceil$, where $\varepsilon\leqslant0$. It improves the bound of the conclusion in [1]. As its application, the linear arboricity of a  triangulation graph on double torus is concluded

Key words： linear arboricity; surface; (secondary) upper-embedded graph; Euler ; characteristic

Cite this article

吕Chang-Qing . The linear arboricity of upper-embedded graph and secondary upper-embedded graph[J]. Journal of East China Normal University(Natural Science), 2015 , 2015(1) : 131 -135 . DOI: 10.3969/j.issn.1000-5641.2015.01.016

References

吕长青. 较大亏格嵌入图的线性荫度 [J]. 华东师范大学学报: 自然科学版, 2013, 1: 7-10.
BONDY J A, MURTY U S R. Graph Theory with Applications [M]. New York: Macmilan Ltd Press, 1976.
MOHAR B, THOMASSEN C. Graphs on Surfaces [M]. Baltimore: Johns Hopkins University Press, 2001: 85-85.
AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs III: Cyclic and acyclic invariants [J]. Math Slovaca, 1980(30): 405-417.
AÏ-DJAFER H. Linear arboricity for graphs with multiple edges [J]. Journal of Graph Theory, 1987(11):135-140.
WU J L. Some path decompositions of Halin graphs [J]. Journal of Shandong Mining Institute, 1998(17): 92-96.
WU J L. The linear arboricity  of series-parallel graphs [J]. Graph and Combinatorics, 2000(16):367-372.
WU J L. The Linear arboricity of graphs on surfaces of negative Euler characteristic [J]. SIAM J Discrete Math, 2008(23):54-58.
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.
WU J L. On the linear arboricity of planar graphs [J]. Journal of Graph Theory, 1999(31): 129-134.
WU J L, LIU G Z, WU Y L. The linear arboricity  of composition graphs [J]. Journal of System Science and Complexity, 2002(15):3 72-375.
AHIYAMA J, EXOO G, HARARY F. Covering and packing in graphs IV: Linear arboricity [J]. Networks, 1981(11): 69-72.
Options
Outlines

/

〈 〉