1. 引言
是无向,有限阶的简单图。对于G的任意一点v,
是指G中相邻的点集,
是指G中与v关联的边的数目。用
表示G的顶点的最小度,用
表示G的连通度,且用
表示G的边连通度。对于任意点集
,用
和
分别表示S和
的导出子图,并且用
表示
的分支个数。设S和T是G的子图或者
的子集,用
表示在
中与T中点相邻的点集,用
表示S与T之间的边集。
定义1.1:设G是一个非完全连通图,其坚韧度定义为:
如果G是完全图,则其坚韧度
;如果G不连通,则其坚韧度
。
定义1.2:如果G的坚韧度为
,那么称G是t-坚韧的。若G的割集S满足
,则称S是G的坚韧集。
Chvátal [1] 在1973年首次提出坚韧度的定义,并提出了一个著名的猜想:存在正实数
,使得每个
-坚韧图都是哈密顿图。之后,很多学者开始研究图的坚韧度和哈密顿图的关系。Thomassen给出了一个坚韧度为3/2的非哈密顿图:选择一个3-正则,3-连通且不存在哈密顿路的图G (Bermond [2] 证明了这样的图是存在的),将图中的每个点都替换成三角形后得到图H,Chvátal [3] 证明了
,因此满足
Chvátal猜想的
。之后,Bauer等在 [1] 中证明了,任给
,都存在一个
-坚韧,不包含哈
密顿路的图,因此
。在一些特殊的图类中,我们可以确定
的值。例如,10-坚韧弦图 [4] 和3/2-坚韧分离图 [5] 是哈密顿图;4-坚韧,2k-连通
-free图 [6] 是哈密顿图;2-坚韧,
-free图 [7] 是哈密顿图;7-坚韧,
-free图 [8] 是哈密顿图。此外,有些学者开始研究图的坚韧度和k-因子的关系 [9]。Enomoto等 [10] 给出了k-坚韧图有一个k-因子的充分条件是
是偶数。Bauer等 [1] 证明了每个3/2-坚韧,5-弦图都有一个2-因子。1999年,Broersma [11] 在研究2-坚韧图的哈密顿性的过程中给出了极小t-坚韧图的定义。
定义1.3:如果G的坚韧度为t,且对于任意一条边
都有
,则称G是极小t-坚韧的。
由坚韧度的定义可知每个t-坚韧非完全图都是2t-连通的,因此t-坚韧图的最小度至少是
。在 [12] 中,Mader [13] 证明了极小k-连通图的最小度为k。据此,Kriesell [7] 针对极小1-坚韧图提出了以下猜想。后来,Katona [12] 推广了他的猜想。
猜想1.4: [14] 每个极小1-坚韧图都有一个2度顶点。
猜想1.5: [12] 每个极小t-坚韧图都有一个
度顶点。
目前为止Kriesell的猜想还未被证明。2018年,Katona [12] 等给出了一个极小1-坚韧图最小度的上界,这是现在得到的最好的结果。虽然现在还没有证明Kriesell的猜想在所有图类上都成立,但是可以证明这个猜想在一些特殊图上成立,例如:Katona [12] 证明了极小1-坚韧,
-free图的最小度是2。同样,推广的Kriesell猜想也被证明在一些特殊图类中成立。例如: [15] 中证明了极小t-坚韧弦图,分离图和
-free图的最小度为1,其中
。
定理1.6: [12] 每个极小1-坚韧图最小度不超过
。
根据极小t-坚韧图的定义,可以得到下面的命题。
命题1.7: [15] 设G是极小t-坚韧图,其中t是正实数。对于G的任意一条边e,
1) e是G的一条割边,或
2) 存在一个点集
满足:
和
,且e是
的割边。
在第一种情况下,我们定义
。
本文主要研究t-坚韧,
-free图的性质,并证明推广的Kriesell猜想在极小
-坚韧,
-free图上成立。下面我们给出了
-free图的定义。
定义1.8:如果G不包含
包含作为它的导出子图,则称G是
-free图。
2. 主要结论及其证明
2.1. t-坚韧,
-Free图的连通度
在这一节中,我们研究t-坚韧,
-free图的连通度。Matthews等 [16] 证明了
-free图的坚韧度和连通度有以下关系。
定理2.1: [16] 如果G是非完全
-free图,那么
。
设
。对于
-free图,上述定理中的等式不成立。例如:
的坚韧度是1,但其连通度是
,但其连通度是
。下面我们给出了一个t-坚韧,
-free图的连通度的上界。
定理2.2:设G是非完全
-free图,其中
。下面的结论成立。
(i)
。
(ii) 如果
且
,那么
或者对于G的坚韧集S,
的每个分支在S中有且仅有三个邻点,且S中的每个点都与
的每个分支相邻。
证明:由坚韧度的定义知,图G中存在割集S满足
。将
的每个分支都收缩到一个点,用S表示这些点的集合,并将S与T之间的重边删掉。由于G是
-free图,所以S中的每个点都与T中的最多
个邻点相邻,从而
。另一方面,由于T中的每个点在S中至少有
个邻点,所以可以得到
。因此
,从而
。
由上面的证明知,当
且
时,有
。如果
,由
知
。这时
的每个分支在S中有且仅有三个邻点,且S中的每个点都与
的每个分支相邻。
由上面的定理知,坚韧度为1的
-free图的连通度不一定为2,若Kriesell的猜想正确,则极小1-坚韧,
-free图的连通度是2。
定理2.3:极小1-坚韧,
-free图的连通度是2。
证明:设G是极小1-坚韧,
-free图。假设
,由
知中G没有割边。
任给边
,设
是满足命题1.6的点集。由于e不是割边,所以
且
。这时
,否则
或
是G的一个二点割,这与
矛盾。因此
,即
是G的坚韧集。设
是
中包含边e的分支,且
和
分别表示
中包含u和v的分支。由定理2.2 (ii)知,可设
。若
,由
,容易得到
且
。再由
,可得
。不妨设
。根据引理2.2 (ii),点
和
中除
外的另外两个分支相邻。显然,
中包含一个
子图,与G是
-free图矛盾。因此
。同理,
。由于
,我们可以设
且
。
令
。设
是满足定理1.6的点集。类似于
的讨论,我们可以证明
也是G的坚韧集。显然,
。由定理2.2 (ii)知,点v与
的三个分支相邻。而
,所以
,这与
矛盾。
因此
。再由
知
。
2.2. 极小
-坚韧,
-Free图
在这一节中,我们将研究极小
-坚韧,
-free图的最小度。Katona等在 [4] [10] 中给出了极小1/2-坚韧和极小1-坚韧,
-free图的结构。
定理2.4: [15] 极小1/2-坚韧,
free图可以用下面的方式构造。
1) 任取一颗最大度为3的树,且树中所有3度点和1度点组成的点集是独立集。
2) 删掉每个度为3的点v,然后将v在树中每个邻点用一个三角形连接起来。
定理2.5: [12] 点数大于3的极小1-坚韧,
-free图都是圈。
由上面的定理知,对于极小1/2-坚韧和极小1-坚韧,
-free图,Kriesell的猜想是正确的。下面我们将研究,当
时,极小
-坚韧,
-free图的最小度。由极小
-坚韧,
-free图G的定义,容易得到以下引理。任给边
,令
。
引理2.6:设G是极小
-坚韧,
-free图。对于G的任意一条非割边e,
(i)
。
(ii) 有且仅有一个圈包含边e,且圈长为3。
证明:对于G的任意一条非割边e,由命题1.6知存在一个非空点集
满足
。
这时
。
将
的每个分支都收缩到一个点,用T表示这些点的集合,并将
与T之间的重边删掉。由于G是
-free图,所以S中的每个点都与T中的最多
个邻点相邻,从而
。另一方面,由G是连通图知T中的每个点在
中至少有1个邻点,所以
。故有
。
由
知
。因此
的每个分支在
中有且仅有一个邻点,且
中的每个点都与
的
个分支相邻。
设
是
中包含边e的分支,令
。因为在
中与
相邻的
个分支不与
中的点相邻,所以
。不难看出
是满足命题1.6的点集,所以
(见图1)。
由于e是非割边,所以G中至少有一个圈包含边e。再由
知包含边e的圈一定包含
。设e的两个端点分别是u和v。因为
与
的
个分支相邻且G是
-free的,所以
,即e只包含在三角形
中。
定理2.7:设
。极小
-坚韧,
-free图的最小度是1。
证明:设G是极小
-坚韧,
-free图。对于G的每个三角形,删掉三角形的三条边,然后增加一个点,将每个点与原来三角形的三个点连边。把G经过上述操作后得到的图记为H。由引理2.6 (ii)知G中的所有圈都是三角形,因此H是树。
下面我们将证明H中的每个叶子节点都是G中的1度点。假设H中存在一个叶子节点s不是G中的1度点。由H的构造过程知G中有且仅有一个三角形包含点s且
,设这个三角形的点集为
。令
,设
是满足命题1.6的点集,且
。由引理2.6 (i)知
。由命题1.6知
。由G是连通图且
,所以
,矛盾。
3. 结论
根据坚韧度的定义,我们可以得到t-坚韧图的连通度是2t-连通的,但是其连通度不一定为2t。对于一些特殊图类,我们可以确定图的坚韧度和连通度的关系。Matthews等 [16] 证明了坚韧度为t的
-free图的连通度是2t。由本文的定理2.2 (i)知,坚韧度小于2/3的
-free图的连通度为1,坚韧度大于等于2/3且小于1的
-free图的连通度是2且坚韧度为1的
-free图的连通度不超过3。Kriesell [14] 猜想极小1-坚韧图的最小度为2。由
知,如果Kriesell的猜想正确,容易推知极小1-坚韧图的连通度是2。本文证明了极小1-坚韧,
-free图的连通度为2。Katona [12] 将Kriesell的猜想推广到了2t上。本文证明了对于极小
-坚韧,
-free图,推广的Kriesell的猜想是正确的。
基金项目
山西省基础研究项目(20210302123097)。
NOTES
*通讯作者。