笛卡尔积图的线性荫度(英文)

Linear arboricity of Cartesian products of graphs

线性森林是指所有分支都是路的森林.图G的线性荫度la(G)是划分G的边集E(G)所需的线性森林的最小数目.图G和H的笛卡尔积图G□H定义为:顶点集V(G□H)={(u,v)u∈V(G),v∈V(H)}.边集E(G□H)={(u,x)(v,y)u=v且xy∈E(H),或uv∈E(G)且x=y}.令Pm与Cm分别表示m个顶点的路和圈,Kn表示n个顶点的完全图.证明了la(Kn□Pm)=(n+1)/2(m≥2),la(Kn□Cm)=(n+2)/2以及la(Kn□Km)=(n+m-1)/2.证明过程给出了将这些图分解成线性森林的方法.进一步的线性荫度猜想对这些图类是成立的.

A linear forest is a forest whose components are paths. The linear arboricity la （G） of a graph G is the minimum number of linear forests which partition the edge set E（G） of G. The Cartesian product G□H of two graphs G and H is defined as the graph with vertex set V（G□H） = {（u, v）｜ u ∈V（G）, v∈V（H） } and edge set E（G□H） = { （ u, x） （ v, Y）｜u=v and xy∈E（H）, or uv∈E（G） and x=y}. Let Pm and Cm,, respectively, denote the path and cycle on m vertices and K, denote the complete graph on n vertices. It is proved that （Km□Pm）=[n＋1/2]for m≥2,la（Km□Cm）=[n＋2/2],and la（Km□Km）=[n＋m-1/2]. The methods to decompose these graphs into linear forests are given in the proofs. Furthermore, the linear arboricity conjecture is true for these classes of graphs.