文摘

我们定义了一个新的不变量由两部分构成的图形,类似于韧性我们给予的充分条件存在的因素在由两部分构成的图形。我们还表明,这些结果是锋利的。

1。介绍

韧性连接一样,是一个重要的不变量在图。有广泛的工作韧性的调查(见[1)自1973年Chvatal介绍了概念(2]。的韧性的图的最小值,在那里是一个适当的子集的顶点和删除后是连接组件的数量吗从。(如果是一个完整的图,这样吗总是等于1呢将)。也就是说,对于任何整数,不能分成通过消除小于连接组件顶点。我们也说是艰难的。Chvatal了一些推测在2),包括著名的2-tough推测说,每一个2-tough图都有哈密顿循环。激励了许多有趣的结果,显示2-tough猜想本身是假鲍尔等人于2000年(3]。

的子图的被称为因素的如果是一个生成子图的。一个重要的因素- - - - - -因素,也叫普通程度的因素,每个顶点有学位在。(注意,一个完美的匹配是一个1-factor和哈密顿循环是一个连接因子)。有广泛的工作存在的条件图的各种因素。许多结果可以发现在最新的调查显示,普卢默(4]。

很自然的认为韧性,另一个衡量的连接图,应该涉及的存在在图形因素。榎本失败等。5- - - - - -7]证明了每一个艰难的图包含一个因素,如果它满足微不足道的必要条件,有艰难的图表对任何不包含因素。考虑一个两偶图 在哪里是一个分区和边的吗每个边都有一个结束和其他。Katerinis [8]证明了每个1-tough两偶图的因子。回想一下,偶图的韧性最多是1,因为删除从(假设在一个独立的组)的结果。因此,不可能使用韧性预测的存在因素在平衡双方的任何图表。

1.1。一式两份的韧性

在本文中,我们介绍一式两份的韧性类似于韧性的概念,但反映出的分为两部分。一式两份的韧性两偶图的的最小值,在那里是一个适当的子集或和删除后是连接组件的数量吗从。我们设置完全由两部分构成的图,就像完整的图形。

两偶图可以只有一个正则度因素。因此,在本文的其余部分,我们认为只有一个平衡两偶图与。的一个子集的,我们使用来表示一组至少有一个顶点在相邻的顶点。有两个不相交的子集和的,我们使用站边的数量有一个结束和其他。其他术语和符号用于本文遵循[9)和其他引用。

一式两份的韧性措施比韧性两偶图的连通性所做的事。与韧性最多1两偶图,可以任意大。例如,在一个完整的两偶图边删除,这方法,就像在一个完全图边删除。有趣的是,更好的不变量预测的存在因素在平衡双方的图表,对任何。此外,通过他们的定义,计算在两偶图比计算简单因为一个是其他的子任务。

1.2。我们的研究结果

让平衡两偶图和是一个整数。在本文中,我们证明以下三个定理。

定理1.1。让。如果,然后1-factor。

定理1.2。为和,如果,然后有一个因素。

定理1.3。为,如果,然后有一个因素。

这些定理给出一个锋利的为有一个因素,。(见图1。请注意,当和是奇怪的;和当)。

的绑定尖锐的感觉。

(一)对定理1.1,让和建立一个平衡两偶图如下。让和,在那里,,。让是由所有可能的边缘之间和和所有可能的边缘之间和。如果是偶数,那么我们加入吗之间的一个边缘和。在这里,所以,通过引理2。1下面,没有1-factor。另一方面,它不是很难验证在这个建设。因此,是一把锋利的。(b)对定理1.2为整数和,建立一个平衡两偶图如下。让和,在那里,,。让是由所有可能的边缘之间和,所有可能的边缘之间和,1-factor之间和。在这里,所以,通过引理2。1下面,没有因素。另一方面,它不是很难验证在。因此,是一把锋利的。(c)对定理1.3。让和是一个整数。很明显,。建立一个平衡的两偶图如下。让和在哪里,,。让是由所有可能的边缘之间和,所有可能的边缘之间和和一个因素之间和。然后。再次,通过引理2。1下面,没有因素。此外,不难验证。因此,也是一个锋利的束缚。

榎本失败也值得提及,与et al。著名的结果艰难的图有因素,在我们的结果的约束远小于实际上大部分时间小于2(见图1)。这看起来是违反直觉的,但由于(不太好)的特点。虽然能的方法,大部分时间并没有明显增加与边缘连接或最低程度。例如,如果,有最低程度(比如在顶点),然后删除所有顶点除了会分裂成组件。所以即使高达。

2。定理的证明

需要以下引理的证明定理。

引理2.1。让是一个平衡两偶图,,让是一个整数。然后以下三个语句是等价的:
(我) 有一个因素;(2) 有edge-disjoint为1的因子;(3)对于任何和,证明。(i)和(ii): Konig-Hall定理(后9定理5.2和引理5.2),普通学位两偶图的完美匹配。因此,一个两偶图的因子可以分割成一组吗edge-disjoint完美的匹配(为1的因子)。(2)(我)是微不足道的。
(我)和(iii):等价的(i)和(3)可以推导出的最大流min-cut定理(10,11]。转换通过网络(a)添加一个源点与multiedges之间和每个顶点;(b)添加一个顶点与multiedges之间和每个顶点;和(c)定位成一个有向弧从边缘来,从来,或从来(见图2)。很明显,有一个因素网络上有一个流式的来任何减少之间的网络和至少包含边缘。对于任何和,考虑到减少图中虚线所示2,我们有 这

证明。假设没有因素和,我们将推断。根据引理2。1,存在和这样。让和。然后 很明显,。我们可以进一步的假设 因为,如果,那么我们可以让和并有,,。通过对称,这种转换的情况。
然后,我们要考虑两种情况。案例1。
如果,然后由(2。3)。通过和(2。4),我们有,在那里。因此 这就完成了定理的证明1.1。(注意,当,我们只有情况1需要考虑。)

证明。现在假设,(2。5),我们有。让。然后由(2。3),。让。然后和。因此,
例2。如果,那么我们就有。由(2。4)和(2。7),
例2。如果,那么我们就有。由(2。5)和(2。7), 例2。
让是唯一的整数令人满意 由(2.10),。由(2。3)和(2.11),有一个顶点这是毗邻顶点的。让所以和。由(2。4)和(2.11),我们有。因此, 定义一个函数。很容易验证的假设,。自是一个凸函数,它遵循了吗为。由(2.12),
这就完成了定理的证明1.2。

证明。事实上,我们将证明定理的结果1.3适用于所有。的条件在定理1.3只是因为,不是一样紧约束当。
假设没有因素,我们将推断。根据引理2。1,存在和这样 在哪里和。在定理的证明1.1和1.2,我们仍然可以认为(2。4)。
假设顶点在相邻的最少(用)的顶点。由(2.14),我们有。然后用(2。4),我们进一步。让,然后和。因此,
这就完成了定理的证明1.3。

3所示。结论和未来的工作

我们定义了一个新的不变量在由两部分构成的图形称为双边的韧性和提供了一个尖锐的一个平衡两偶图因素,从1到。我们认为这是一个很大的改进使用韧性预测因素在由两部分构成的图形,作为两偶图的韧性是最多1和它不能预测因素对任何。

也有研究韧性的计算复杂度。一般来说,识别图的韧性是np困难(12]。此外,1-tough图也是np难的13),甚至1-tough由两部分构成的图形是np难14]。在claw-free韧性(无)图15),1-tough分割图(14),在分割图和韧性16)所示P。在未来,这将是非常有趣的,以确定双方的韧性的复杂性。

承认

第一作者的工作部分是由中国国家自然科学基金国家自然科学基金委10871119。