树和路乘积图的线性荫度
The Linear Arboricity of the Product of Tree and Path
DOI: 10.12677/AAM.2022.113134, PDF, HTML,  被引量 下载: 217  浏览: 362 
作者: 李 萍：浙江师范大学，数学与计算机科学学院，浙江 金华
关键词: 线性荫度猜想；笛卡尔积图；直积图；强积图；Linear Arboricity Conjecture； The Cartesian Product of Graphs； The Direct Product of Graphs； The Strong Product of Graphs
摘要: 1970 年 Harary 提出图的线性荫度的概念, 指的是将图 G 的边集分解成 m 个边不交的线性森林的最小整数 m. 线性森林即每一个连通分支都是路的图. 本文主要对树和路的乘积结构进行讨论, 通过对乘积图中的边进行划分, 证明了树和路的笛卡尔积图、直积图、强积图满足线性荫度猜想。
Abstract: Harary introduced the concept of linear arboricity in 1970. The linear arboricity is the minimum integer m such that G can be decomposed into m edge-disjoint linear forests. A linear forest is a graph in which every connected component is a path. We discuss the product structure of tree and path, divide the edges in the product graph and prove that the linear arboricity conjecture holds for the cartesian product, the direct product, the strong product of tree and path.
文章引用：李萍. 树和路乘积图的线性荫度[J]. 应用数学进展, 2022, 11(3): 1242-1246. https://doi.org/10.12677/AAM.2022.113134

参考文献

[1] Harary, F. (1970) Covering and Packing in Graphs. Annals of the New York Academy of Sciences, 175, 198-215.
https://doi.org/10.1111/j.1749-6632.1970.tb56470.x
[2] Akiyama, J., Exoo, G. and Harary, F. (1980) Covering and Packing in Graphs III: Cyclic and Acyclic Invariants. Mathematica Slovaca, 30, 405-417.
[3] Akiyama, J., Exoo, G. and Harary, F. (1981) Covering and Packing in Graphs IV: Linear Arboricity. Networks, 11, 69-72.
https://doi.org/10.1002/net.3230110108
[4] Tomasta, P. (1982) Note on Linear Arboricity. Mathematica Slovaca, 32, 239-242.
[5] Enomoto, H. and P´eroche, B. (1984) The Linear Arboricity of Some Regular Graphs. Journal of Graph Theory, 8, 309-324.
https://doi.org/10.1002/jgt.3190080211
[6] Guldan, F. (1986) The Linear Arboricity of 10-Regular Graphs. Mathematica Slovaca, 36, 225-228.
https://doi.org/10.1002/jgt.3190100408
[7] Wu, J. (1999) On the Linear Arboricity of Planar Graphs. Journal of Graph Theory, 31, 129-134.
https://doi.org/10.1002/(SICI)1097-0118(199906)31:2(129::AID-JGT5〉3.0.CO;2-A
[8] Wu, J. and Wu, Y. (2008) The Linear Arboricity of Planar Graphs of Maximum Degree Seven Is Four. Journal of Graph Theory, 58, 210-220.
https://doi.org/10.1002/jgt.20305

为你推荐