在1-连通和2-连通的二部图中保持连通度的一些树的研究∗

罗莲，田应智

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

0 引言

本文只考虑无自环和无平行边的有限无向图.V(G),E(G) 和δ(G) 分别表示的是图G 的点集,边集和最小度.图G 的阶|G|表示的是它的点集的基数.对于任意的点v ∈V(G),N(v)=NG(v)表示与点v 相邻的所有的顶点的集合,并且dG(v)=|NG(v)| 称为图G 中点v 的度数.一个树T 中度为1 的点称之为树T 的叶子,Leaf(T)表示的是树T 的叶子点的集合.一个树T 中度数至少为2 的点称之为树T 的内点,VI(T)表示的是树T 的内点的集合.对于任意的一个非空子集S ⊆V(G),G[S] 表示的是由S 导出G 的子图.图G 的连通度记作κ(G),是满足G-S 是不连通的或是平凡图K1的最小点集S 的基数.如果κ(G)≥k,则称G 是k-连通的.若B 是G 的一个极大的没有割点的连通子图,则称B 是G 的块.本文中未定义的术语和符号可参阅文献[1].

Chartrand 等人给出如下著名定理.

定理1[2]任意连通图G 中存在点x,使得G-x 仍然是k-连通的.Fujita 和Kawarabayashi 在[3] 中验证了的k-连通的图G 中存在相邻的两点u,v 使得G-{u,v} 仍然是k-连通的.他们也提出如下猜想.

猜想1[3]对任意的正整数k,m,存在一个非负整数fk(m) 使得的k-连通图G 中存在一个阶为m 的连通子图W,使得G-W 仍然是k-连通的.

他们还在[3] 中验证了对任意的正整数k,m,都有fk(m) ≥m.Mader 在[4] 中验证了猜想1 中的参数fk(m)=m,并且可取连通子图W 为一条路P.

定理2[4]对任意的正整数k,m,每一个的k-连通图G 中存在一个阶为m 的路P,使得G-V(P) 仍然是k-连通的.

基于定理2,Mader 提出如下猜想.

猜想2[4]对任意的阶为m 的树T,每一个的k-连通图G 中存在一个子树T′～=T,使得G-V(T′) 仍然是k-连通的.

在[5] 中,Mader 证明了δ(G)≥2(k-1+m)2+m-1 时,猜想2 是成立的.

定理3[5]对任意的阶为m 的树T,每一个δ(G)≥2(k-1+m)2+m-1 的k-连通图G 中存在一个子树T′～=T,使得G-V(T′) 仍然是k-连通的.

Diwan 和Tholiya 在[6] 中验证了猜想2 在k=1 时的情形.

定理4[6]对任意的阶为m 的树T,每一个δ(G)≥m 的连通图G 中存在一个子树T′～=T,使得G-V(T′)仍然是连通的.

对于猜想2,当k=2 时,Tian 等学者在[7-8]中验证了T 是星图,双星图,或路双星图时的情形;Hasunuma和Ono 在[9] 中验证了当T 有至多5 个内点,或者T 是一个拟单调的毛毛虫图或是一个具有6 个内点的毛毛虫图的情形;在[10] 中Lu 等学者验证了当T 的直径至多是4 的情形;在[11] 中Hong 等学者验证了当T 是任意的毛毛虫图和蜘蛛图时的情形.关于二部图的点连通度的其他研究可参阅文献[12-13].

受到以上结论的启发,我们也对二部图提出了类似的猜想.

猜想3对任意的具有二部划分X 和Y 的树T,每一个δ(G)≥k+t (t=max{|X|,|Y|})的k-连通的二部图G 中存在一个子树T′～=T,使得G-V(T′) 仍然是k-连通的.

把T 中最多有一个点的度大于1 的树称为星图.把T 中只有两个相邻点的度大于或等于2 的树称为双星图.对于树T,若VI(T)/=∅且T[VI(T)] 是一条路P,则T 是一个毛毛虫图.可以看出星图和双星图都是特殊的毛毛虫图.

在本文中,我们验证了猜想3 在k=1 和k=2 时,T 是一个内点的个数至多为3 的毛毛虫图的情形是对的.

1 主要结果

在这一节中,我们首先给出一些在二部图中子树存在的度条件的结论.

由引理1,我们可以得到下面的推论.

推论1设T 是一个具有二部划分X 和Y 的树,记t=max{|X|,|Y|},每一个δ(G)≥t 的二部图G 中存在一个子树T′～=T.

下面我们将要证明主要结论.

定理5 设T 是一个具有二部划分X 和Y 的树,记t=max{|X|,|Y|}.如果T 的内点的个数不大于3,则每一个δ(G)≥t+1 的连通的二部图G 中存在一个子树T′～=T 使得G-V(T′) 仍然是连通的.

证明假设此定理是不成立的.由推论2 知G 中存在与T 同构的子树T′.在所有同构于T 的子树中,选择一个子树T′使得G-V(T′)包含的连通子图的阶数最大.设H0是G-V(T′)的最大连通分支,H1=G-V(T′∪H0),由假设知V(H1)/=∅.

因为G 是连通的,所以存在v ∈V(T′) 使得N(v)∩V(H0)/=∅.又因为δ(G)≥t+1,所以对任意的h ∈H1都有即δ(G[V(H1)])≥1.

当毛毛虫图T 的内点的个数为1 时,T 同构于星图.对任意的h ∈H1,|N(h)∩V(G-(V(H0)∪{v}))|≥t+1-1=t.由推论1 知,我们可以在G-(V(H0)∪{v}) 中找到一个以点h 为中心点的星图T′′～=T.但是V(H0)∪{v} 包含在G-V(T′′) 的一个连通分支中,这与T′的选择矛盾.

当毛毛虫图T 的内点的个数为2 时,T 同构于双星图.由于δ(G[V(H1)]) ≥1,则H1中至少存在一边e=h1h2.因为|N(h1)∩V(G-(V(H0)∪{v}))|≥t 和|N(h2)∩V(G-(V(H0)∪{v}))|≥t,那么由引理1 知,在G-(V(H0)∪{v}) 中存在一个以边e=h1h2的点为中心点的双星图T′′～=T.但是V(H0)∪{v} 包含在G-V(T′′)的一个连通分支中,这与T′的选择矛盾.

现在来看当毛毛虫图T 的内点的个数为3 时的情形.若H1中存在一条长为2 的路P=h1h2h3,因为|N(h1)∩V(G-(V(H0)∪{v}))|≥t,|N(h2)∩V(G-(V(H0)∪{v}))|≥t 和|N(h3)∩V(G-(V(H0)∪{v}))|≥t,所以由引理1 知,在G-(V(H0)∪{v})中存在一个以路P=h1h2h3的点为中心点的毛毛虫图T′′～=T.但是V(H0)∪{v}包含在G-V(T′′) 的一个连通分支中,这与T′的选择矛盾.因此H1中的连通分支都同构于K2.对任意的边h1h2∈H1,因为δ(G)≥t+1,所以|N(h1)∩V(T′)|=t,|N(h2)∩V(T′)|=t.设T′的二部划分为X′和Y′.不妨假设h1和Y′中的点都相连,h2和X′中的点都相连.如果v ∈X′,那么我们用h1代替v 可以找到一个毛毛虫图T′′～=T.但这时V(H0)∪{v} 包含在G-V(T′′) 的一个连通分支中,这与T′的选择矛盾.如果v ∈Y′,那么我们用h2代替v 可以找到一个毛毛虫图T′′～=T.但这时V(H0)∪{v} 包含在G-V(T′′) 的一个连通分支中,这也与T′的选择矛盾.

综上可知,假设不成立,则定理5 的结论是正确的.

定理6设T 是一个具有二部划分X 和Y 的毛毛虫图,记t=max{|X|,|Y|}.如果T 的内点的个数不大于3,则每一个δ(G)≥t+2 的2-连通的二部图G 中存在一个子树T′～=T 使得G-V(T′) 仍然是连通的.

证明假设此定理是不成立的.由二部图中子树存在的度条件知,G 中存在与T 同构的子树T′.在所有同构于T 的子树中,选择一个子树T′使得G-V(T′) 中包含的块的阶数最大,记G-V(T′) 中阶数最大的块为B.因为δ(G-V(T′))≥2,所以|B|≥3 且B 是2-连通的.除此之外,因为G-V(T′) 不是2-连通的,所以G-V(T′∪B)/=∅.令H=G-V(T′∪B).通过对B 的假设知,对任意的h ∈H,都有|N(h)∩V(B)| ≤1 和|N(h)∩V(H)|≥t+2-|N(h)∩V(B)|-|N(h)∩V(T′)|≥t+2-1-t=1,即δ(G[V(H)])≥1.

论断1对任意的v ∈T′,|N(v)∩V(B)|≤1.

假设论断1 不成立,那么存在v ∈T′,使得|N(v)∩V(B)|≥2.

当毛毛虫图T 的内点的个数为1 时,T 同构于星图.因为对于任意的h ∈H,|N(h)(V(B)∪{v})|≥t+2-1-1=t,所以我们可以很容易地在G-(V(B)∪{v}) 中找到一个以h 为中心点的同构于T 的星图T′′.但是V(B)∪{v}包含在G-V(T′′) 的一个块中,这与假设矛盾.

当毛毛虫图T 的内点的个数为2 时,T 同构于双星图.由于δ(G[V(H)])≥1,则H 中至少存在一边e=h1h2.因为|N(h1)∩V(G-(V(B)∪{v}))|≥t 和|N(h2)∩V(G-(V(B)∪{v}))|≥t,那么由引理1 知,在G-(V(B)∪{v})中存在一个以边e=h1h2的点为中心点的双星图T′′～=T.但是V(B)∪{v} 包含在G-V(T′′) 的一个块中,这与假设矛盾.

现在来看当毛毛虫图T 的内点的个数为3 时的情形.若H1中存在一条长为2 的路P=h1h2h3,因为|N(h1)∩V(G-(V(B)∪{v}))|≥t,|N(h2)∩V(G-(V(B)∪{v}))|≥t 和|N(h3)∩V(G-(V(B)∪{v}))|≥t,所以由引理1 知,在G-(V(B)∪{v}) 中存在一个以路P=h1h2h3的点为中心点的毛毛虫图T′′～=T.但是V(B)∪{v}包含在G-V(T′′) 的一个块中,这与假设矛盾.因此H 中的连通分支都同构于K2.对任意的边h1h2∈H,因为δ(G)≥t+2,所以|N(h1)∩V(T′)|≥t,|N(h2)∩V(T′)|≥t.设T′的二部划分为X′和Y′.不妨假设h1和Y′中的点都相连,h2和X′中的点都相连.如果v ∈X′,那么我们用h1代替v 可以找到一个毛毛虫图T′′～=T.但这时V(B)∪{v} 包含在G-V(T′′) 的一个块中,这与T′的选择矛盾.如果v ∈Y′,那么我们用h2代替v 可以找到一个毛毛虫图T′′～=T.但这时V(B)∪{v} 包含在G-V(T′′) 的一个块中,这又与T′的选择矛盾.

综上所述,论断1 是正确的.

因为G 是2-连通的,所以在G 中存在一个最短的路P=p1,p2,···,pr−1,pr,其中p1,pr∈V(B)且pi∈V(T′∪H)(2 ≤i ≤r-1).因为对于任意的点v ∈V(T′∪H) 都有|NG(v)∩V(B)|≤1,那么|P|≥4.又因为P 是最短路,所以NG(p2)∩V(B ∪P)={p1,p3},那么|NG(p2)∩V(H ∪T′)|=dG(p2)-|NG(p2)∩V(B ∪P)|≥t+2-2=t,这意味着V(G)V(B ∪P)/=∅.而对于任意的s ∈V(G)V(B ∪P),一定有|NG(s)V(B ∪P)|=dG(s)-|NG(s)∩V(B ∪P)|≥t+2-2=t (二部图中同一条边上的点的邻点集合不会相交).因此由推论2 可知,G-V(B∪P) 中存在一个子树T′′～=T,然而V(B)∪V(P) 包含在G-V(T′′) 的一个块中,这与T′的选择矛盾.

综上可知,假设不成立,则定理6 的结论是正确的.