The linear arboricity of upper-embedded graph and secondary upper-embedded graph
-
摘要: 通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度\,$\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
-
[1] 吕长青. 较大亏格嵌入图的线性荫度 [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. -
点击查看大图
计量
- 文章访问数: 854
- HTML全文浏览量: 11
- PDF下载量: 1090
- 被引次数: 0
下载: