西日尼阿依·努尔麦麦提，张盼盼，刘凤霞，孟吉翔

(新疆大学 数学与系统科学学院，新疆 乌鲁木齐 830046)

0 引言

设G=(V,E)是个简单的，无向的，n个顶点的图.如果序列τ=(n1,n2,…,nk)满足n=，则称序列τ在图G中是可允许的.如果τ=(n1,n2,…,nk)是图G的可允许序列且存在顶点集V(G)的一个划分(V1,V2,…,Vk)，满足|Vi|=ni对于所有的1 ≤i ≤k成立，且Vi导出的子图G[Vi]是连通的，则称这个可允许的序列τ是可实现的，并且称图G是τ-可分的.如果图G的每个可允许序列在图G中可实现，则我们把图G称为任意可分图（简称为AP图或AVD图）.如果图G对于每个至多是k部分的划分τ都是τ-可分的,则称这个图G是k-可分的.如果一个图是2-可分的，则这个图的性质跟限制连通性是有关的，有关限制连通性的研究见文献[1,2].

两个图G和H的笛卡儿积记为G□H，其顶点集为V(G)×V(H)，G□H的两个顶点(v1,u1)，(v2,u2)相邻当且仅当v1=v2且u1u2∈E(H)或者u1=u2且v1v2∈E(G).

如果图G含有一条哈密尔顿路，则此图称为可迹图.路和可迹图G都是任意可分的.Baudon[3]等人提出了猜想任意可分图G和可迹图H的笛卡儿积图是任意可分的，并且他们证明了图H是顶点数至多为4的可迹图时猜想成立.众所周知，如果两个图G和H都是可迹图，则它们的笛卡儿积也是可迹图.Liu[4]等人证明了T是最大度至多为n+1的树，如果树T中有一条包含T中所有度为n+1的顶点的路，则T□Cn是任意可分图.

与经典问题完美匹配结合是任意可分图的重要研究方向.若一个图G是任意可分图，则可允许序列(2,2,…,2)或(1,2,2,…,2)一定是可实现的，即G有完美匹配或几乎完美匹配.从而一个图含有完美匹配或几乎完美匹配……