几类半笛卡尔积图的线性荫度

Linear Arboricity of Several Classes of Semi-Cartesian Product of Graphs

摘要: 一个线性森林是指每个连通分支都是路的森林。图G的线性荫度是指使得G的边集E(G)可以分解成n个线性森林的最小整数n，用la(G)表示。本文对路和路、路和圈、圈和圈以及路和树的半笛卡尔积结构进行讨论，通过对这几类图中的边进行划分，得到了路和路，路和圈，圈和圈以及路和树的半笛卡尔积的线性荫度的确切值并且证明这几类图满足线性荫度猜想。

Abstract: A linear forest is a forest whose components are paths. The linear arboricity la(G) of a G is the minimum number n of linear forests that is the partition of the edge set E(G) of G. In this paper, we discuss the structure of Semi-Cartesian product path and path, path and cycle, cycle and cycle, and path and tree. By dividing the edges of these kinds of graphs, we show that the exact values of the linear arboricity of Semi-Cartesian products of path and path, path and cycle, cycle and cycle, path and tree and these values match up the linear arboricity conjecture.