广义太阳图与路的笛卡儿积图的任意可分性∗

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

(新疆大学 数学与系统科学学院，新疆 乌鲁木齐 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有完美匹配或几乎完美匹配.从而一个图含有完美匹配或几乎完美匹配的必要条件是一个图是任意可分图.Liu[5]等人证明了团数为2的2K2-free图是任意可分图当且仅当此图含有完美匹配或几乎完美匹配.Horňák[6]等人证明了对于一个顶点数至少为20的连通图G，如果图G有完美匹配或几乎完美匹配，并且任意两个不相邻的顶点度数之和至少为n−5，则图G是任意可分的.

如果图G有任意可分的生成子图，则此图是任意可分图，而树是最简单的生成子图.因此，自从2002年提出任意可分图的定义后，在过去的几年里有很多有关任意可分树的结论.Horňák和Wo´zniak[7]证明了任意可分树的最大度至多为6，并且提出了猜想如果树T的最大度至少为5，则T不是任意可分的.此猜想被Barth和Fournier[8]证明了，且他们证明了一个任意可分树T的最大度至多为4，并且每个4-度点与一个叶子点相邻.Cichacz[9]等人完全刻画了四个叶子点的任意可分毛毛虫图.

星型树S(a1,a2,…,at,b1,b2,…,bs)（简记为S）是一个同态于星K1,k的树.K1,k的每一条边分别被长度为a1,a2,…,at,b1,b2,…,bs的路替换而得的图，其中ai(1 ≤i ≤t)是奇数，bl(1 ≤l ≤s)是偶数，且Δ(S)=k=t+s ≥2.

广义太阳图是一个圈Cn上的某些顶点悬挂星型树的单圈图.圈Cn上的顶点称为中心点，用u1,u2,…,un来表示.我们用S∗∗=S(n;k1,k2,…,kn)来记d(ui)≥4(1 ≤i ≤n)，且S(n;k1,k2,…,kn)−E(Cn)=S1∪S2∪…∪Sn是广义太阳图，其中Si=S(a1i,a2i,…,ati,b1i,b2i,…,bsi)是Δ(Si)=ki=ti+si≥2(1 ≤i ≤n)的星型树，且Δ(S∗∗)=（如图1）.

图1 广义太阳图S∗∗Fig 1 Generalized Sun-like graph S∗∗

在这篇文章中，我们主要研究广义太阳图和路的笛卡儿积的任意可分性.首先按m的奇偶性分类，给出了G∗∗=S∗∗□Pm是任意可分图的一些充分条件，然后结合Tutte’s定理，给出了G∗∗=S∗∗□Pm不是任意可分图的一些充分条件.

1 S∗∗□Pm的任意可分性

图3 图S(5;4,3,4,4,3)的拷贝分Fig 3 The copies of graph S(5;4,3,4,4,3)

2 结论

文中我们给出了图G∗∗=S∗∗□Pm是可迹图，且是任意可分图的充分条件.并且结合Tutte’s定理给出了图G∗∗=S∗∗□Pm不是任意可分图的充分条件.