|
|
二部图与完全图的乘积图的线性荫度
|
Abstract:
1970年，Harary首次提出了图的线性荫度这一重要概念。在图论的范畴中，图的线性荫度是指把图G的边集进行划分，分解成为若干个边互不相交的线性森林时，所需线性森林的最少数目。线性森林即每一个连通分支都是路的森林。本文聚焦于二部图和完全图的乘积结构展开讨论，通过对乘积图的边进行分解，证明了二部图与完全图的笛卡尔积图、直积图及乘积图满足线性荫度猜想。
In 1970, Harary first proposed the important concept of the linear arboricity of a graph. In the context of graph theory, the linear arboricity of a graph refers to the minimum number of linear forests required when the edge set of graph G is partitioned and decomposed into several edge-disjoint linear forests. A linear forest refers to a forest where each connected component is a path. This paper focuses on the product structure of bipartite graphs and complete graphs for discussion. By decomposing the edges of the product graphs, it is proved that the Cartesian product graphs, direct product graphs, and product graphs of bipartite graphs and complete graphs satisfy the linear arboricity conjecture.
| [1] | Harary, F. (1970) Covering and Packing in Graphs, I. Annals of the New York Academy of Sciences, 175, 198-205. 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. Math-ematica Slovaca, 30, 405-417. |
| [3] | Enomoto, H. and Péroche, B. (1984) The Linear Arboricity of Some Regular Graphs. Journal of Graph Theory, 8, 309-324. https://doi.org/10.1002/jgt.3190080211 |
| [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. https://doi.org/10.1002/(sici)1097-0118(199906)31:2<129::aid-jgt5>3.0.co;2-a |
| [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. https://doi.org/10.1002/jgt.20305 |
| [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. https://doi.org/10.1016/j.ipl.2014.03.013 |
| [8] | Zhang, X. and Liu, G. (2012) The Structure of Plane Graphs with Independent Crossings and Its Applications to Coloring Problems. Open Mathematics, 11, 308-321. https://doi.org/10.2478/s11533-012-0094-7 |
| [9] | Niu, B. and Zhang, X. (2019) Linear Arboricity of Nic-Planar Graphs. Acta Mathematicae Applicatae Sinica, English Series, 35, 924-934. https://doi.org/10.1007/s10255-019-0865-z |
| [10] | 李萍. 树和路乘积图的线性荫度[J]. 应用数学进展, 2022, 11(3): 1242-1246. |
| [11] | 易思梦. 路和完全图的乘积图的线性荫度[J]. 应用数学进展, 2024, 13(4): 1494-1499. |
