路和完全图的乘积图的线性荫度
The Linear Arboricity of the Product of Path and Complete Graph
摘要: 1970年，Harary提出了图的线性荫度概念，它指的是把图G的边集分解成边不交的线性森林的最少数目。线性森林是指每个连通分支都是路的森林。本文通过对路和完全图的笛卡尔积图、直积图进行边分解，证明了路和完全图的笛卡尔积图、直积图符合线性荫度猜想，进而证明了路和完全图的乘积图满足线性荫度猜想。
Abstract: In 1970, Haray proposed the concept of linear arboricity of a graph, which refers to decomposing the edge set of graph G into the minimum number of linear forests with non intersecting edges. A linear forest is a forest where each connected component is a path. This article proves that the Cartesian product graph and direct product graph of a path and a complete graph satisfy the linear arboricity conjecture by performing edge decomposition on them. Furthermore, it proves that the strong product graph of a path and a complete graph satisfies the linear arboricity conjecture.
文章引用：易思梦. 路和完全图的乘积图的线性荫度[J]. 应用数学进展, 2024, 13(4): 1494-1499. https://doi.org/10.12677/aam.2024.134140

参考文献

[1] Harary, F. (1970) Covering and Packing in Graphs. Annals of the New York Academy of Sciences, 175, 198-215. [Google Scholar] [CrossRef] 
[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] Enomoto, H. and Peroche, B. (1984) The Linear Arboricity of Some Regular Graphs. Journal of Graph Theory, 8, 309-324. [Google Scholar] [CrossRef] 
[4] Guldan, F. (1986) The Linear Arboricity of 10-Regular Graphs. Mathematica Slovaca, 36, 225-228.
[5] Wu, J. (1999) On the Linear Arboricity of Planar Graphs. Journal of Graph Theory, 31, 129-134. [Google Scholar] [CrossRef] 
[6] 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. [Google Scholar] [CrossRef] 
[7] Wang, H., Wu, J., Liu, B. and Chen, H. (2014) On the Linear Arboricity of Graphs Embeddable in Surfaces. Information Processing Letters, 114, 475-479. [Google Scholar] [CrossRef] 
[8] Zhang, X. and Liu, G. (2013) The Structure of Plane Graphs with Independent Crossings and Its Applications to Coloring Problems. Central European Journal of Mathematics, 11, 308-321. [Google Scholar] [CrossRef] 
[9] Niu, B. and Zhang, X. (2019) Linear Arboricity of NIC-Planar Graphs. Acta Mathematicae Applicatae Sinica, English Series, 35, 924-934. [Google Scholar] [CrossRef] 
[10] 李萍. 树和路乘积图的线性荫度[J]. 应用数学进展, 2022, 11(3): 1242-1246. [Google Scholar] [CrossRef] 

为你推荐