华东师范大学学报(自然科学版) ›› 2015, Vol. 2015 ›› Issue (1): 131-135.doi: 10.3969/j.issn.1000-5641.2015.01.016

• 应用数学与基础数学 • 上一篇    下一篇

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

吕长青   

  1. 枣庄学院 数学与统计学院, 山东 枣庄 277160
  • 收稿日期:2014-04-01 出版日期:2015-01-25 发布日期:2015-03-29
  • 通讯作者: 吕长青, 男, 副教授, 研究方向为图论、运筹学. E-mail:cqiqc1999@126.com
  • 基金资助:

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

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

LYU Chang-Qing   

  1. School of Mathematics and Statistics, Zaozhuang University, Zaozhuang Shandong, 277160, China
  • Received:2014-04-01 Online:2015-01-25 Published:2015-03-29

摘要: 通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度\,$\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]\,中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度

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

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

中图分类号: