华东师范大学学报（自然科学版） >

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

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

应用数学与基础数学

上可嵌入图与次上可嵌入图的线性荫度

  • 吕长青
展开
  • 枣庄学院 数学与统计学院, 山东 枣庄 277160

收稿日期: 2014-04-01

  网络出版日期: 2015-03-29

基金资助

国家自然科学基金(11101357, 61075033)

收起

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

摘要

通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度\,$\Delta$\,不小于\,$3\sqrt{4-3\varepsilon}$\,且欧拉示性数\,$\varepsilon\leqslant0$\,的上可嵌入图其线性荫度为\,$\lceil\frac{\Delta}{2}\rceil$\,.对于次上可嵌入图, 如果最大度\,$\Delta\geqslant3\sqrt{4-3\varepsilon}$\,且\,$\varepsilon\leqslant0$, 则其线性荫度为\,$\lceil \frac{\Delta}{2}\rceil$. 改进了文献\,[1]\,中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度

关键词： 线性荫度; 曲面; (次)上可嵌入图; 欧拉示性数

本文引用格式

吕长青 . 上可嵌入图与次上可嵌入图的线性荫度[J]. 华东师范大学学报（自然科学版）, 2015 , 2015(1) : 131 -135 . DOI: 10.3969/j.issn.1000-5641.2015.01.016

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

参考文献

吕长青. 较大亏格嵌入图的线性荫度 [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
文章导航

/

〈 〉