路和完全图的乘积图的线性荫度  

The Linear Arboricity of the Product of Path and Complete Graph

作　　者：易思梦 

机构地区：[1]浙江师范大学数学科学学院,浙江 金华

出　　处：《应用数学进展》2024年第4期1494-1499,共6页Advances in Applied Mathematics

摘　　要：1970年,Harary提出了图的线性荫度概念,它指的是把图G的边集分解成边不交的线性森林的最少数目。线性森林是指每个连通分支都是路的森林。本文通过对路和完全图的笛卡尔积图、直积图进行边分解,证明了路和完全图的笛卡尔积图、直积图符合线性荫度猜想,进而证明了路和完全图的乘积图满足线性荫度猜想。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.

关 键 词：线性荫度猜想 乘积图 笛卡尔积图 直积图 

分 类 号：G63[文化科学—教育学]