树和路乘积图的线性荫度

The Linear Arboricity of the Product of Tree and Path

1970 年 Harary 提出图的线性荫度的概念, 指的是将图 G 的边集分解成 m 个边不交的线性森林的最小整数 m. 线性森林即每一个连通分支都是路的图. 本文主要对树和路的乘积结构进行讨论, 通过对乘积图中的边进行划分, 证明了树和路的笛卡尔积图、直积图、强积图满足线性荫度猜想。

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.