较大亏格曲面嵌入图的线性荫度

吕长青; 房永磊

较大亏格曲面嵌入图的线性荫度

1.
枣庄学院~~数学与统计学院, 山东~~枣庄 277160

详细信息

中图分类号: O157.5
计量
- 文章访问数: 1755
- HTML全文浏览量: 19
- PDF下载量: 1502
- 被引次数: 0
出版历程
- 收稿日期: 2012-04-01
- 修回日期: 2012-07-01
- 刊出日期: 2013-01-25

Linear arboricity of an embedded graph on a surface of large genus

1.
School of Mathematics and Statistics, Zaozhuang University, Zaozhuang Shandong 277160, China

摘要

摘要: 通过度再分配的方法研究嵌入到曲面上图的线性荫度. 给定较大亏格曲面\,$\Sigma$\,上嵌入图\,$G$, 如果最大度\, $\Delta(G)\geq (\sqrt{45-45\varepsilon}+10)$\,且不含\,4-圈, 则其线性荫度为\,$\lceil \frac{\Delta}{2}\rceil$, 其中若\,$\Sigma$\, 是亏格为\,$h(h1)$\,的可定向曲面时 $\varepsilon=2-2h$, 若\, $\Sigma$\,是亏格为\,$k(k2)$\,的不可定向曲面时 $\varepsilon=2-k$. 改进了吴建良的结果, 作为应用证明了边数较少图的线形荫度.
- 线性荫度 /
- 曲面 /
- 嵌入图 /
- 欧拉示性数
Abstract: The linear arboricity of a graph $G$ is the minimum number of linear forests which partition the edges of $G$. This paper proved that if $G$ can be embedded on a surface of large genus without 4-cycle and $\Delta(G)\geq (\sqrt{45-45\varepsilon}+10)$, then its linear arboricity is $\lceil \frac{\Delta}{2}\rceil$, where $\varepsilon=2-2h$ if the orientable surface with genus \,$h(h1)$\,or $\varepsilon=2-k$ if the nonorientable surface with genus \,$k(k2)$. It improves the bound obtained by J. L. Wu. As an application, the linear arboricity of a graph with fewer edges were concluded.
- linear arboricity /
- surface /
- embedded graph /
- Euler characteristic

HTML全文

参考文献(1)

[1]

{1}

WU J L. The linear arboricity of graphs on surfaces of negative

Euler characteristic[J]. SIAM J Discrete Math 2008, 23: 54-58.

{2}

BONDY J A, MURTY U S R. Graph Theory with Applications[M].

New York: Macmilan Ltd Press, 1976.
{3}

MOHAR B, THOMASSEN C. Graphs on Surfaces[M]. Baltimore: Johns

Hopkins University Press, 2001: 85-85

{4}

AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs III:

Cyclic and acyclic invariants[J]. Math Slovaca, 1980, 30: 405-417.

{5}

A\"{I}-DJAFER H. Linear arboricity for graphs with multiple

edges[J]. J Graph Theory 1987, 11: 135-140.

{6}

WU J L, WU Y W. The linear arboricity of planar graphs of maximum

degree seven are four[J] J Graph Theory,
{7}

WU J L. On the linear arboricity of planar graphs[J]. J Graph

Theory, 1999, 31: 129-134.
{8}

WU J L. Some path decompositions of Halin graphs[J]. J Shandong

Mining Institute, 1998, 17: 92-96. (in Chinese).
{9}

WU J L. The linear arboricity of series-parallel graphs[J]. Graph

and Combinatorics, 2000, 16: 367-372.
{10}

WU J L, LIU G Z, WU Y L. The linear arboricity of composition

graphs[J]. Journal of System Science and Complexity, 2002, 15(4):

372-375.
{11}

AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs IV:

Linear arboricity[J]. Networks, 1981, 11: 69-72.

施引文献

资源附件(0)

访问统计