二部图与完全图的乘积图的线性荫度

The Linear Arboricity of the Product Graph of Bipartite Graph and Complete Graph

摘要: 1970年，Harary首次提出了图的线性荫度这一重要概念。在图论的范畴中，图的线性荫度是指把图G的边集进行划分，分解成为若干个边互不相交的线性森林时，所需线性森林的最少数目。线性森林即每一个连通分支都是路的森林。本文聚焦于二部图和完全图的乘积结构展开讨论，通过对乘积图的边进行分解，证明了二部图与完全图的笛卡尔积图、直积图及乘积图满足线性荫度猜想。

Abstract: 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.