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

摘要

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