K_(1,7)与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))-可分的。

似星树与路的乘积图的任意可分性

设似星树S=S(a 1,a 2,…,a t,b 1,b 2,…,b s),其中a i(1≤i≤t)是奇数,bj(1≤j≤s)是偶数.首先,讨论似星树S与路Pl的乘积图S■P l在t和s不同取值下是否为任意可分图,并用图不含完美匹配的方法和反证法给出其不是任意可分图的充分条件;其次,分析图S■P l的Hamilton性,并用似星树的任意可分性给出图为任意可分图的充分条件.结果表明,当t=1且s≤2时,图S■P l是任意可分图;当t≥2或t=0,或者t=1,s≥3,b 1=b 2=…=b s,t+s≥l+2时,图S■P l均不是任意可分图.

星样树与路的笛卡尔积图的任意可分性

一个图G称为是任意可分的(简记AP),如果对于正整数|V(G)|的任一满足∑p i=1 ni=|V(G)|的划分τ=(n1,n2,⋯,np),总是存在顶点集V的一个划分(V1,V2,⋯,Vp)满足|Vi|=ni,i=1,2,⋯,p,使得每个Vi导出的图是图G的一个连通子图.记S(a1,a2,⋯,at,b1,b2,⋯,bl)是最大度Δ(S)=t+l的星样树,其中ai是奇数,bj是偶数且a1≤a2≤⋯≤at,b1≤b2≤⋯≤bl.我们证明了对于一个大于等于2的偶数n,当Δ(S)≤n+1时,如果t≤2,或t≥3且a3>1,则笛卡尔积图S◻Pn是AP的.对于一个大于2的奇数n,如果Δ(S)≤n+1且t≤2,则S◻Pn是AP的;如果Δ(S)≤n+1且t≥3,则S◻Pn不是AP的.