K_(1,7)与P_(6)的强积图的任意可分性

Partitioning the Strong Product of K_(1,7)and P_(6)

设G=(V,E)是n个顶点的简单图。序列λ=(λ_(1),λ_(2),·,λ_(p))满足λ_(1)+λ_(2)+·+λ_(p)=n,则序列λ被称为是可允许的序列。如果图G的顶点集V的一个划分(V_(1),V_(2),·,V_(p))满足|V_(i)|=λ_(i),i=1,2,·,p,且G[V_(i)]是连通的,则这个可允许的序列λ被称为是可表示的,并且称图G是λ-可分的。记K1,t是最大度为t的星,K1,t■Pn为星与路的强积图,图K1,7■P6是(1,λ_(2),·,λ_(p))-可分的。

A graph G is calledλ-partitionable if for a sequenceλ=(λ_(1),λ_(2),·,λ_(p))of positive integers adding up to|V(G)|,there is a partition(V_(1),V_(2),·,V_(p))of the vertex set of G such that:(i)|V_(i)|=λ_(i),i=1,2,·,p(ii)each V_(i)induces a connected subgraph in G.Let K1,tbe a star with maximum degree t.We show that if t=7,n=6,then the strong product K1,7■P6is(1,λ_(2),·,λ_(p))-partitionable.