张盼盼, 刘凤霞, 孟吉翔

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

1 引言与预备知识

设图G=(V,E)是阶为n的简单图, 正整数序列λ=(λ1,λ2,…,λp)是一个非递减序列. 如果λ1+λ2+…+λp=n, 则称λ是G的可允许序列. 如果λ是一个可允许序列, 且存在对点集V的一个划分(V1,V2,…,Vp), 使得每个Vi导出一个阶为λi的G的连通子图, 则称λ是G的可实现序列, 且(V1,V2,…,Vp)是序列λ在G中的实现, 每个子图G[Vi]称为图G的λi分支. 如果每个可允许序列都是可实现的, 则称G是任意可分图(简称AP图或AVD图)[1]. 如果图G含一条Hamilton路, 则称图G为可迹图. 显然, 每个可迹图都是任意可分图. 当图G的阶为偶数时,G有完美匹配等价于序列(2,2,…,2)是G的可实现序列； 当图G的阶为奇数时,G有几乎完美匹配等价于序列(1,2,…,2)是G的可实现序列. 因此, 任意可分图一定有完美匹配或几乎完美匹配, 从而一个图有完美匹配或者几乎完美匹配的必要条件是该图为任意可分图.

如果图G的生成树是任意可分图, 则图G是任意可分图. Horňk等[2]证明了如果树T是任意可分的, 则T的最大度至多为6, 并且提出了任意可分树的最大度至多为4的猜想. 该猜想被Barth等[3]证明, 得到了任意可分树的最大度至多为4, 且每个4度顶点与一个叶子点相邻的结论. Cichacz等[4]刻画了4个叶子点的毛毛虫树的任意可分性, 并展示了最大度为3或4的两类任意可分树. Marczyk[5]证明了对阶为n的连通图G, 当独立数至多为n/2, 且任意一对不相邻顶点的度和至少为n-3时, 图G是任意可分图或者同构于两个例外图. Horňk等[6]证明了对阶数n≥20的连通图G, 任意两个不相邻顶点……