本文只讨论有限无向简单图. 设$ G $是一个图, 其顶点集和边集分别表示为$ V(G) $和$ E(G) $. 记$ d_{G}(v) $和$ N_{G}(v) $ (简记为$ d(v) $和$ N(v) $)为图$ G $中顶点$ v $的度和邻域, $ \delta(G) $是图$ G $的最小度, $ G[S] $表示由$ S\subseteq V(G) $导出的子图. 设$ i(G) $为图$ G $中孤立点的数量, $ G_{1}\vee G_{2} $表示将每一对来自$ G_{1} $ 和$ G_{2} $的顶点通过边相连. 其他相关符号和标记可参考[1].
设$ a, b, k $为正整数满足$ 1\le a\le b $, $ h: E(G)\to[0, 1] $是定义在边集上的示性函数. 分数$ [a, b] $-因子是由边集$ E_{h}=\{e\in E(G)|h(e) > 0\} $决定的生成图, 对任意$ v\in V(G) $满足$ a\le \sum_{v'\in N(v)}h(vv')\le b $. 图$ G $存在分数$ [a, b] $-因子是指满足上述条件的示性函数$ h $存在. 若$ a=b=k $, 则分数$ [a, b] $-因子退化为分数$ k $-因子.
文献[2]引入孤立韧度的概念, 对于非完全图定义为
对于完全图则规定$ I(G)=+\infty $.
近20年来, 关于孤立韧度和分数因子的关系, 得到了丰富的结果. [3]指出图$ G $存在分数$ k $-因子若$ \delta(G)\ge k $且$ I(G)\ge k $. [4]给出了图存在分数$ [a, b] $-因子的一个孤立韧度条件, 并说明结论在一定意义下是"最好"的. 最近, [5]得到了在删除任意$ n $个顶点条件下依然存在分数$ k $-因子的孤立韧度条件, 同时说明该条件是紧的.
本文的主要贡献在于给出一个图存在分数$ [a, b] $-因子的孤立韧度条件, 并且通过反例说明该条件是最好的. 本文的组织结构如下: 首先对[4]中的结果证明, 反例及猜想进行分析; 其次, 给出分数$ [a, b] $-因子存在性的紧孤立韧度条件, 结果的最好性通过反例说明; 然后, 对本文主要结果给出详细证明.
首先, 我们对文献[4]中存在的问题进行分析. 文献[4]给出如下结论:
定理2.1[4] 设$ G $是一个图, $ a, b $都是正整数, 且$ 2\le a < b $. 若$ G $的孤立韧度与最小度满足$ \delta(G)\ge I(G)\ge a-1+\frac{a-1}{b} $, 则$ G $有分数$ [a, b] $-因子.
作者对孤立韧度的"最好性"用下面的例子来阐述: $ a\ge2 $, $ V(G)=V(K_{n(a-1)})\cup V((nb+1)K_{1})\cup V(K_{(nb+1)(a-1)}) $. 令$ V((nb+1)K_{1})=\{v_{1}, v_{2}, \cdots, v_{nb+1}\} $, $ \{u_{1}, u_{2}, \cdots, u_{nb+1}\}\subseteq V(K_{(nb+1)(a-1)}) $. $ E(G)=E(K_{n(a-1)})\cup E(K_{(nb+1)(a-1)})\cup\{u_{i}v_{i}: i=1, \cdots, nb+1\}\cup\{xy: x\in V(K_{n(a-1)}), y\in(nb+1)K_{1}\} $.
此外, 文献[4]还给出如下猜想:
猜想2.2[4] 定理1.1对$ a=b $也成立. 即当整数$ k\ge2 $时, 对于图$ G $, 若图$ G $的孤立韧度和最小度满足$ \delta(G)\ge I(G)\ge k-\frac{1}{k} $, 则$ G $有分数$ k $-因子.
通过对文献[4]的深入分析, 我们给出如下几个注记:
(1) 在文献[4]中, 对定理2.1的证明忽略了对$ T $中只有$ K_{a} $的情况讨论. 事实上, 通过本文主要定理的证明和反例选取, 会发现真正孤立韧度的界和反例恰好出现在$ T $中只有$ K_{a} $的情况.
(2) 在定理2.1孤立韧度界最好性的说明中, 作者认为在上述所给的例子中令$ S=V(K_{n(a-1)})\cup V(K_{(nb+1)(a-1)}) $, 就有
进而当$ n\to\infty $时有$ I(G)\to a-1+\frac{a-1}{b} $.
这里关于$ I(G) $的计算是一个明显的错误. 因为根据图$ G $的构造, $ K_{(nb+1)(a-1)} $中只有
这部分顶点与$ (nb+1)K_{1} $相邻, 因此, 只要删除$ V(K_{n(a-1)}) $和$ \{u_{1}, u_{2}, \cdots, u_{nb+1}\} $就可以得到$ nb+1 $个孤立顶点. 从而图$ G $的真实孤立韧度值应该为$ I(G)=\frac{n(a-1)+nb+1}{nb+1}=1+\frac{n(a-1)}{nb+1} $且$ \lim_{n\to\infty}=1+\frac{a-1}{b} $. 由此可知, [4]中的反例无法说明定理2.1中孤立韧度是紧的.
(3) 关于分数$ k $-因子孤立韧度条件的猜想2.2是不成立的. 事实上, [3]中已经给出了$ G $存在分数$ k $-因子的紧孤立韧度条件, 即: 若$ \delta(G)\ge k $且$ I(G)\ge k $, 则$ G $存在分数$ k $-因子. 虽然我们发现[3]中关于$ I(G)\ge k $最好性解释的反例也存在漏洞, 但文献[5]中对此作了补充解释, 给出了正确反例.
基于如上的分析, 可知关于分数$ [a, b] $-因子的紧孤立韧度条件至今没有得到解决, 依然是个开问题. 这引导我们去深入思考到底图中存在分数$ [a, b] $-因子的最好孤立条件是什么. 本文的贡献在于解答这个问题, 给出关于分数$ [a, b] $-因子的孤立韧度下界, 并且通过反例来说明新给出的界是紧的.
本文主要结论如下:
定理3.1 设$ G $是一个图, $ a, b $都是正整数, 且$ 2\le a\le b $. 若$ \delta(G)\ge a $且$ I(G)\ge a-1+\frac{a}{b} $, 则$ G $存在分数$ [a, b] $-因子.
根据分数$ [a, b] $-因子的定义, 最小度条件$ \delta(G)\ge a $显然是紧的. 下面通过实例来解释定理3.1中的孤立韧度也是紧的. 设$ G=K_{\lfloor\frac{al-1}{b}\rfloor}\vee(lK_{a}) $其中$ l\ge2 $是正整数. 为了得到至少两个孤立点, 显然要删除$ K_{\lfloor\frac{al-1}{b}\rfloor} $ 中的所有顶点, 选择$ m $ (其中$ m\in[2, l] $ 是整数) 个$ K_{a} $并对每个$ K_{a} $删除其中的$ a-1 $个顶点. 从而有,
设$ al-1=bn+c $, 其中$ n\in\Bbb N\cup\{0\} $, $ c\in\{0, 1, \cdots, b-1\} $. 进而$ \frac{1}{b}\le\frac{c+1}{b}\le1 $,
可以看到为了让比值达到最小需要取$ m=l $, 同时$ I(G) $的值随着$ l $的增大而增大, 最后逼近于$ a-1+\frac{a}{b} $但无法到达$ a-1+\frac{a}{b} $ (因为图是有限的). 即$ \lim\limits_{l\to+\infty}I(G)=a-1+\frac{a}{b}. $ 设$ S=V(K_{\lfloor\frac{al-1}{b}\rfloor}) $及$ T=V(lK_{a}) $, 则有
若$ al-1 $是$ b $的整数倍, 则
若$ al-1 $不是$ b $的整数倍, 则
综上所述, $ b|S|-a|T|+\sum_{x\in T}d_{G-S}(x) < 0 $, 根据引理3.3, 可知$ G $没有分数$ [a, b] $-因子.
为了证明定理3.1, 我们需要用到几个引理. 以下结果刻画了分数$ [a, b] $-因子存在的充分必要条件.
引理3.2[6] 设$ G $是一个图, $ a, b $为正整数且满足$ a\le b $. 则$ G $存在分数$ [a, b] $-因子当且仅当对任意$ S\subseteq V(G) $, 有
成立, 其中$ T=\{x\in V(G)-S|d_{G-S}(x)\le a\} $.
可知引理3.2中的$ T $由顶点集$ S $决定, 且可以改写为$ T=\{x\in V(G)-S|d_{G-S}(x)\le a-1\} $. 值得注意的是, 引理3.2有如下等价形式.
引理3.3[6] 设$ G $是一个图, $ a, b $为正整数且满足$ a\le b $. 则$ G $存在分数$ [a, b] $-因子当且仅当
对任意不相交的顶点子集$ S, T\subseteq V(G) $都成立.
以下引理刻画了特定框架下的独立集和覆盖集.
引理3.4[7] 设$ G $是一个图, $ H=G[T] $满足对任意$ x\in V(H) $有$ d_{G}(x)= k-1 $且$ H $的任何一个连通分支都不与$ K_{k} $同构, 其中$ T\subseteq V(G) $且$ k\ge2 $为整数. 则存在$ H $的最大独立集$ I $和覆盖集$ C=V(H)-I $满足
其中$ I^{(i)}=\{x\in I, d_{H}(x)=k-i\} $ ($ 1\le i \le k $)且$ \sum\limits_{i=1}^{k}|I^{(i)}|=|I| $.
若$ G $是完全图, 则根据$ \delta(G)\ge a $可知结果成立. 下面讨论非完全图. 设$ G $满足定理3.1的所有条件, 但不存在分数$ [a, b] $-因子. 根据引理3.3, 存在$ V(G) $的不相交子集$ S $和$ T $满足
选取$ S $和$ T $使得$ |T| $达到最小. 从而可知$ T\ne\emptyset $, 且对任意$ x\in T $有$ d_{G-S}(x)\le a-1 $.
设$ l $是$ H'=G[T] $中与$ K_{a} $同构的连通分支数, $ T_{0}=\{x\in V(H')| d_{G-S}(x)=0\} $. 设子图$ H $是从$ H'-T_{0} $中删除$ l $个与$ K_{a} $同构的连通分支后得到的子图. 在$ H' $的每个$ K_{a} $连通分支中选取$ a-1 $个顶点构成的顶点子集记为$ S' $.
若$ |V(H)|=0 $, 则由(4.1)可知$ |S|\le \frac{a(|T_{0}|+l)-1}{b} $. 由$ |T|\ne0 $得到$ |T_{0}|+l\ge1 $. 若$ |T_{0}|+l=1 $, 则$ |S|\le \frac{a-1}{b} $进而有$ S=\emptyset $. 由$ d_{G-S}(x)+|S|\ge d_{G}(x)\ge\delta(G)\ge a $可得$ d_{G-S}(x)\ge a-|S|=a $, 这与任意$ x\in T $满足$ d_{G-S}(x)\le a-1 $矛盾. 进而$ i(G-S\cup S')=|T_{0}|+l\ge2 $且
设$ a(|T_{0}|+l)-1=mb+c $, 其中$ m\in\Bbb N\cup\{0\} $且$ c\in\{0, \cdots, b-1\} $. 则$ \frac{1}{b}\le\frac{c+1}{b}\le1, $
这说明$ a-1+\frac{\lfloor\frac{a(|T_{0}|+l)-1}{b}\rfloor}{|T_{0}|+l} $随着$ |T_{0}|+l $的增大而增大, 当$ |T_{0}|+l $逼近于无穷时达到最大, 进而有$ I(G) < a-1+\frac{a}{b} $, 矛盾.
由此有$ |V(H)| > 0 $. 设$ H=H_{1}\cup H_{2} $其中$ H_{1} $是$ H $中的连通分支的并集, 其中对任意$ v\in V(H_{1}) $满足$ d_{G-S}(v)=a-1 $. 且$ H_{2}=H-H_{1} $. 根据引理3.4, $ H_{1} $存在最大独立集$ I_{1} $和覆盖集$ C_{1}=V(H_{1})-I_{1} $满足
和
其中$ I^{(i)}=\{v\in I_{1}, d_{H_{1}}(v)=a-i\} $($ 1\le i \le a $)且$ \sum\limits_{i=1}^{a}|I^{(i)}|=|I_{1}| $. 根据$ H $和$ H_{2} $的定义, 可知$ H_{2} $的每个连通分支都至少存在一个$ G-S $中度至多为$ a-2 $的顶点. 显然, 若$ H_{2}\ne\emptyset $, 则$ a\ge3 $, 且$ I_{2} $可以通过下面的程序选出: 选择顶点$ v\in V(H_{2}) $使得它在$ G-S $中有最小的度(每次迭代按照原$ G-S $的度进行计算). 若当前所有顶点在原来$ G-S $中的度均为$ a-1 $, 则选择在当前子图中度最小的. 更新$ V(H_{2})\gets V(H_{2})\setminus(\{v\}\cup N_{H_{2}}(v)) $并重复这一过程直到$ V(H_{2})=\emptyset $.
设$ W=V(G)-S-T $且$ U=S\cup S'\cup C_{1}\cup(N_{G}(I_{1})\cap W))\cup N_{G-S}(I_{2})=S\cup S'\cup N_{G-S}(I_{1})\cup N_{G-S}(I_{2}) $. 下面分两种情况讨论.
情况1. $ |T_{0}|+l\ge1 $.
下面两个断言说明$ H_{1} $或$ H_{2} $都不能单独存在.
断言4.1 若$ |T_{0}|+l\ge1 $, 则$ |I_{2}|\ne0 $.
证 假设$ |I_{2}|=0 $. 由$ |V(H)| > 0 $可知$ |I_{1}|\ne 0 $.
将$ I_{1} $划分为如下两个子集.
$ I_{11} $: $ v\in I_{11} $若存在$ v'\in I_{1}\setminus\{v\} $使得$ N_{G-S}(v)\cap N_{G-S}(v')\ne\emptyset $;
$ I_{12} $: $ v\in I_{12} $若$ N_{G-S}(v) $和$ N_{G-S}(I_{1}\setminus\{v\}) $之间不存在交集.
可得
且
这与$ I(G)\ge a-1+\frac{a}{b} $矛盾.
断言4.2 若$ |T_{0}|+l\ge1 $, 则$ |I_{1}|\ne0 $.
证 假设$ |I_{1}|=0 $. 根据$ |V(H)| > 0 $有$ |I_{2}|\ne0 $, 进而$ a\ge3 $.
设$ I_{2}=\{v_{1}, v_{2}, \cdots, v_{|I_{2}|}\} $满足$ d_{G-S}(v_{1})\le a-2 $和$ d_{G-S}(v_{1})\le d_{G-S}(v_{2})\le\cdots\le d_{G-S}(v_{|I_{2}|}) $. 则$ |T|=|V(H_{2})|+|T_{0}|+al $,
可得$ i(G-U)\ge2 $其中$ U=S\cup S'\cup N_{G-S}(I_{2}) $,
因此,
矛盾.
根据断言4.1和断言4.2, 得$ |I_{1}| > 0 $, $ |I_{2}| > 0 $且$ a\ge3 $.
记$ v_{1}, v_{2}, \cdots, v_{|I_{2}|} $是按照断言4.2定义的$ I_{2} $的顶点序列. 则$ |T|=|V(H_{1})|+|V(H_{2})|+|T_{0}|+al $,
可得$ i(G-U)\ge3 $其中$ U=S\cup S'\cup C_{1}\cup(N_{G}(I_{1})\cap W)\cup N_{G-S}(I_{2}) $且
因此有
与$ I(G) $的假设矛盾.
情况2. $ |T_{0}|+l=0 $.
与情况1类似, 下面两个断言是确认$ H_{1} $或$ H_{2} $不能独立存在.
断言4.3 若$ |T_{0}|+l=0 $, 则$ |I_{2}|\ne0 $.
证 若$ |I_{2}|=0 $. 则可得$ |I_{1}|\ne 0 $, $ |T|=|V(H_{1})| $和$ b|S|\le a|T|-d_{G-S}(T)-1=|T|-1 $.
若$ |I_{1}|=1 $, 则$ |T|\le a-1 $且$ |S|\le\frac{|T|-1}{b}\le \frac{a-2}{b} $. 因此$ |S|=0 $且$ a\le\delta(G)\le |S|+(a-1)=a-1 $, 矛盾. 从而有$ |I_{1}|\ge2 $.
进而$ i(G-U)\ge|I_{1}|\ge2 $其中$ U=S\cup C_{1}\cup(N_{G}(I_{1})\cap W) $. 类似断言4.1的推导, 我们有
从而
断言4.4 若$ |T_{0}|+l=0 $, 则$ |I_{1}|\ne0 $.
证 假设$ |I_{1}|=0 $. 则根据$ |V(H)| > 0 $有$ |I_{2}|\ne 0 $, 进而$ a\ge3 $.
若$ |I_{2}|=1 $, 则设$ d_{min}=\min\{d_{G-S}(v)|v\in H_{2}\} $, $ z\in V(H_{2}) $满足$ d_{G-S}(z)=d_{min} $, 进而有$ d_{min}\in\{1, \cdots, a-2\} $. 可得
从而可得$ |I_{2}|\ge2 $. 设$ v_{1}, v_{2}, \cdots, v_{|I_{2}|} $是断言4.2中定义的$ I_{2} $顶点序列, 从而$ d_{G-S}(v_{1})\le a-2 $且$ d_{G-S}(v_{1})\le d_{G-S}(v_{2})\le\cdots\le d_{G-S}(v_{|I_{2}|}) $. 从而有$ |T|=|V(H_{2})| $,
根据$ i(G-U)\ge|I_{2}|\ge2 $其中$ U=S\cup N_{G-S}(I_{2}) $, 以及断言4.2中的讨论, 得到
从而有
从断言4.3和断言4.4, 可知$ |I_{1}|\ge1 $, $ |I_{2}|\ge1 $且$ a\ge3 $. 可得$ i(G-U)\ge2 $其中$ U=S\cup C_{1}\cup(N_{G}(I_{1})\cap W)\cup N_{G-S}(I_{2}) $且
综上所述, 结论成立.