路和圈、圈和圈的Kronecker 积图的超点连通性∗

吴丽芸，田应智

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

0 引言

本文主要研究的是无自环和平行边的有限无向图.设G 是一个点集为V(G),边集为E(G)的图.对于V(G)中的每一个点v ∈V(G),N(v)=NG(v) 表示与点v 相邻的所有的点的集合,并且dG(v)=|NG(v)| 称为图G 中点v 的度数.δ(G) 表示图G 的最小度.若对V(G) 中任意一点v 都有dG(v)=k,那么图G 是k-正则的.此外,若V′⊆V(G),那么G[V′] 是G 的由V′导出的子图.未定义的术语和符号可参阅文献[1].

设S 是点集V(G)的一个子集,如果G-S 不连通,那么称S 是图G 的点割.图G 的连通度κ(G) 是最小非负整数k,使得有S ⊂V(G) 满足|S|=k 且G-S 不连通或G-S 是平凡图K1.众所知周,κ(G)≤δ(G).因此,当κ(G)=δ(G) 时,我们称G 是极大点连通的.若图G 的每一个最小点割都是某个点的邻点集,那么G 是超点连通的,或者简称为是super-κ 的.由定义可知,若图G 是超点连通的,则G 一定是极大点连通的;反过来不一定成立,比如对于整数k ≥3,C2k是极大点连通的但不是超点连通的.

图G1与G2的Kronecker 积图是一个点集为V(G1×G2)=V(G1)×V(G2),边集为E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)} 的图.文献[2] 研究了两个完全图的Kronecker 积图的点连通度.文献[3] 给出了二部图和完全图的Kronecker 积图的点连通度.文献[4] 和文献[5] 分别独立地证明了文献[3] 中所提出的关于非平凡图与一个完全图的Kronecker 积图的点连通度的猜想是成立的,即:κ(G×Kn)=min{nκ(G),(n-1)δ(G)},其中n ≥3.文献[6] 证明了若G 是一个极大连通二部图,那么G×Kn(n ≥3) 是超点连通的.文献[7] 证明了两个完全图,路和完全图,圈和完全图的Kronecker 积图是超点连通的.进一步,文献[8]证明了对任一极大连通图G,除了G×Kn～=Km,m×K3(m ≥1),G×Kn(n ≥3) 是超点连通的.之后,文献[9] 证明了G×Kn(n ≥3)不是超点连通的当且仅当κ(G×Kn)=nκ(G),其中n ≥3 或G×Kn～=Kl,l×K3(l>0).与Kronecker 积图相关的其他结论可以参阅文献[10-11].

除了Kronecker 积图,乘积图中受到关注最多的是笛卡尔积图.与笛卡尔积图相关的连通性的研究结果可以参阅文献[12-18].

现在,列出一些关于Kronecker 积图的性质及结论.

性质1[19]设G=G1×G2=(V(G),E(G)),那么

(1) |V(G)|=|V(G1)|·|V(G2)|,

(2) |E(G)|=2|E(G1)|·|E(G2)|,

(3) 对任一顶点(u,v)∈V(G),dG(u,v)=dG1(u)·dG2(v).

定理1[20]若G1与G2是连通图,那么G1×G2是连通的当且仅当G1与G2中至少有一个图包含奇圈.

1 主要结果

对于两个图G1和G2的Kronecker 积图,记V1=V(G1)={u1,u2,···,um},V2=V(G2)={v1,v2,···,vn}.记Si={ui}×V2,i=1,2,···,m.将点(ui,vj) 简记为ωij,i=1,2,···,m,j=1,2,···,n.那么Si={ωi1,ωi2,···,ωin},i=1,2,···,m.因此,很容易得到记Pm是有m 个点的路,Cn是有n 个点的圈.

引理1对于整数m ≥2 和奇数n ≥3,有κ(Pm×Cn)=2.

证明令G=Pm×Cn.当m=2 时,可验证G=P2×Cn～=C2n,所以κ(G)=κ(C2n)=2.

当m ≥3 时.显然,κ(G)≤δ(G)=δ(Pm)·δ(Cn)=2.

假设S 是G 的一个点割集且|S|<2,即|S|=1.不妨假设S={ωij}.

当i=1 (或i=m) 时.因为Pm[{u2,···,um}]×Cn是连通的(当i=m 时,Pm[{u1,···,um-1}]×Cn是连通的),并且S1-S 中的每一个点在S2中都存在邻点(当i=m 时,Sm-S 中的每一个点在Sm-1中都存在邻点),那么G-S 是连通的,与假设矛盾.

当i=2 (或i=m-1) 时.若m=3,由于P3[{u1,u2}]×Cn-S 与P3[{u2,u3}]×Cn-S 都是连通的,并且V(P3[{u1,u2}]×Cn-S)∩V(P3[{u2,u3}]×Cn-S)=S2-S,所以通过S2-S 可知P3×Cn-S 是连通的,与假设矛盾.若m ≥4,由于Pm[{u1,u2}]×Cn-S 与Pm[{u3,···,um}]×Cn都是连通的(当i=m-1,Pm[{um-1,um}]×Cn-S与Pm[{u1,···,um-2}]×Cn都是连通的),并且S2-S 中的点在S3中都存在邻点(当i=m-1 时,Sm-1-S 中的点在Sm-2中都存在邻点),那么G-S 是连通的,与假设矛盾.

当3 ≤i ≤m-2 时,则m ≥5.由于Pm[{u1,···,ui-1}]×Cn与Pm[{ui+1,···,um}] ×Cn都是连通的,并且Si-S 中的每一个点在Si-1与Si+1中都存在邻点,那么G-S 是连通的,与假设矛盾.

分析上述所有情况,得到的都是与假设矛盾的结论,所以G 中不存在点割集S 满足|S|<2.因此,κ(G)≥2.

又因为已经证明了κ(G)≤2,所以可得κ(G)=2.

接下来,要证明路和圈的Kronecker 积图的超点连通性.当m=2 时,P2×Cn同构于C2n不是超点连通的.当整数m ≥3,n=3 时,由文献[7]中定理2.4 知Pm×C3是超点连通的.当m=3,n 是大于等于5 的奇数时,取S={ω2j,ω2(j+1)} (当j=n 时,j+1=1),此时P3×Cn-S (n ≥5) 是不连通且不包含孤立点的.因此,P3×Cn(n ≥5) 不是超点连通的.所以,下面主要考虑整数m ≥4 且奇数n ≥3 时的情况.

定理2若整数m ≥4,奇数n ≥3,那么G=Pm×Cn是超点连通的.

证明若整数m ≥4,n=3,由文献[7] 中定理2.4 知Pm×C3是超点连通的.接下来,只需考虑整数m ≥4 且奇数n ≥5 时的情况.

假设G 不是超点连通的,则存在G 的一个点割集S 满足|S|=2,使得G-S 不连通且不包含孤立点.不妨假设S={ωij,ωkl},且i ≤k.

情形1i=k.

当i=1 (或i=m) 时.因为Pm[{u2,···,um}]×Cn是连通的(当i=m 时,Pm[{u1,···,um-1}]×Cn是连通的),并且S1-S 中的每一个点在S2中都存在邻点(当i=m 时,Sm-S 中的每一个点在Sm-1中都存在邻点),所以G-S 是连通的,与假设矛盾.

当i=2 (或i=m-1) 时.由于Pm[{u3,···,um}]×Cn是连通的(当i=m-1 时,Pm[{u1,···,um-2}]×Cn是连通的),并且S2-S 中的每一个点在S3中都存在邻点(当i=m-1 时,Sm-1-S 中的每一个点在Sm-2中都存在邻点),那么Pm[{u2,u3,···,um}]×Cn-S 是连通的(当i=m-1 时,Pm[{u1,···,um-2,um-1}]×Cn-S 是连通的).因为G-S 不包含孤立点,所以S1中的每一个点在S2-S 中都存在邻点(当i=m-1 时,Sm-S 中的每一个点在Sm-1中都存在邻点).因此,G-S 是连通的,与假设矛盾.

当3 ≤i ≤m-2 时,则m ≥5.由于Pm[{u1,···,ui-1}]×Cn与Pm[{ui+1,···,um}] ×Cn都是连通的,并且Si-S 中的每一个点在Si-1与Si+1中都存在邻点,那么G-S 是连通的,与假设矛盾.

情形2i

此时|Si∩S|=1,|Sk∩S|=1.

当i=1 时.由于κ(Pm×Cn)=2,且|Sk∩S|=1,那么Pm[{u2,···,um}]×Cn-ωkl是连通的.若k=2,因为S1-{ωij}中的每一个点在S2-{ωkl}中都存在邻点,所以G-S 是连通的,与假设矛盾.若k ≥3,由于S1-{ωij}中的每一个点在S2中都存在邻点,那么G-S 是连通的,与假设矛盾.

当2 ≤i ≤m-2 时.由于κ(Pm×Cn)=2,且|Si∩S|=1,|Sk∩S|=1,那么Pm[{u1,···,ui}]×Cn-ωij与Pm[{ui+1,···,uk,···,um}]×Cn-ωkl都是连通的.若k=i+1,因为Si-{ωij} 中的每一个点在Sk-{ωkl} 中都存在邻点,所以G-S 是连通的,与假设矛盾.若k ≥i+2,由于Si-{ωij} 中的每一个点在Si+1中都存在邻点,那么G-S 是连通的,与假设矛盾.

当i=m-1 时.因为i

引理2对于整数m ≥3 和奇数n ≥3,有κ(Cm×Cn)=4.

证明令G=Cm×Cn.当m=3 或n=3 时,由文献[7] 中引理2.5 知κ(Cm×Cn)=4.所以,接下来主要考虑大于等于4 的整数m 以及大于等于5 的奇数n 的情况.显然,κ(G)≤δ(G)=δ(Cm)·δ(Cn)=4.

假设S 是G 的一个点割集且|S|<4,即|S|≤3.

由于Pm×Cn是G 的生成子图,则κ(G)≥κ(Pm×Cn)≥2,从而|S|≥2.

当|S|=2 时,若G-S 不连通,则Pm×Cn-S 也不连通.由定理2 可知S 一定是Pm×Cn中某个最小度点的邻点集,那么G-S 是连通的,与G-S 不连通矛盾.因此,|S|>2,进而|S|=3.

情形1|Si∩S|=|S|=3.

记Cm-ui～=因为是连通的，并且Si-S 中的每一个点在Si-1与Si+1(当i=1 时,i-1=m;当i=m 时,i+1=1) 中都存在邻点,那么G-S 是连通的,与假设矛盾.

情形2|Si∩S|=1,|Sk∩S|=2.

不妨假设i

情形3|Si∩S|=1,|Sk∩S|=1,|Sp∩S|=1.

不妨假设i

由于m ≥4,那么uiuk,ukup,upui不可能都是Cm中的边,不妨假设upui/∈E(Cm),则Pm[{uk+1,···,up,···,um,u1,···,ui-1}]×Cn-ωpq是连通的.

子情形3.1k=i+1.

若vjvl∈E(Cn),那么Pm[{ui,uk}]×Cn-{ωij,ωkl} 是连通的.当p=k+1 时,因为Sp-{ωpq} 中的每一个点在Sk-{ωkl} 中都存在邻点,所以G-S 是连通的,与假设矛盾.当k+2 ≤p ≤i-2 时,由于Sk-{ωkl} 中的每一个点在Sk+1中都存在邻点,那么G-S 是连通的,与假设矛盾.

若vjvl/∈E(Cn),那么Pm[{ui,uk}]×Cn-{ωij,ωkl} 不连通且不包含孤立点.因为Pm[{ui-1,ui}]×Cn-ωij是连通的,且Sk-{ωkl} 中的每一个点在Si-{ωij} 中都存在邻点,所以Pm[{ui-1,ui,uk}]×Cn-{ωij,ωkl} 连通.由于Sk-S 中的每一个点在Sk+1-S (当k=m 时,k+1=1) 中都存在2 个邻点,而|Sk+1-S|=0 或1,那么G-S 是连通的,与假设矛盾.

子情形3.2k ≥i+2.

当k=i+2 时,此时i+1=k-1.因为κ(Pm×Cn)=2,且|Si∩S|=1,|Sk∩S|=1,所以Pm[{ui,ui+1}]×Cn-ωij和Pm[{ui+1,uk}]×Cn-ωkl都是连通的.由于V(Pm[{ui,ui+1}]×Cn-ωij)∩V(Pm[{ui+1,uk}]×Cn-ωkl)=Si+1,那么通过Si+1可知Pm[{ui,ui+1,uk}]×Cn-{ωij,ωkl}是连通的.当k ≥i+3 时,由定理2 可知Pm[{ui,···,uk}]×Cn是超点连通的,因为{ωij,ωkl}不是Pm[{ui,···,uk}]×Cn中某个最小度点的邻点集,所以Pm[{ui,···,uk}]×Cn-{ωij,ωkl}是连通的.因此,当|Pm[{ui,···,uk}]|≥3 时,Pm[{ui,···,uk}]×Cn-{ωij,ωkl} 是连通的.

若p=k+1.因为Sp-{ωpq} 中的每一个点在Sk-{ωkl} 中都存在邻点,所以G-S 是连通的,与假设矛盾.

若k+2 ≤p ≤i-2.由于Sk-{ωkl} 中的每一个点在Sk+1中都存在邻点,那么G-S 是连通的,与假设矛盾.

分析上述所有情况,得到的都是与假设矛盾的结论,所以G 中不存在点割集S 满足|S|<4.因此,κ(G)≥4.

又因为已经证明了κ(G)≤4,所以可得κ(G)=4.

接下来,刻画的是圈和圈的Kronecker 积图的超点连通性.当m=3,n=3 时,由文献[7] 中定理2.6 可知C3×C3是超点连通的.当m=4,n=3 时,由文献[9] 可知C4×C3～=K2,2×K3不是超点连通的.当m=4,奇数n ≥5 时,取S=V(C4)×{vj},那么C4×Cn-S (n ≥5) 不连通且不包含孤立点.因此,C4×Cn(n ≥5) 不是超点连通的.所以,下面主要考虑大于等于5 的整数m 以及大于等于3 的奇数n 的情况.

定理3若整数m ≥5,奇数n ≥3,那么G=Cm×Cn是超点连通的.

证明若整数m ≥5,n=3,由文献[7] 中定理2.6 知Cm×C3是超点连通的.接下来,只需讨论整数m ≥5 且奇数n ≥5 时的情况.

假设G 不是超点连通的,则存在G 的一个点割集S 满足|S|=4,使得G-S 不连通且不包含孤立点.

情形1 |Si∩S|=4.

记Cm-ui～=因为×Cn是连通的，并且Si-S 中的每一个点在Si-1与Si+1(当i=1 时,i-1=m;当i=m 时,i+1=1) 中都存在邻点,那么G-S 是连通的,与假设矛盾.

情形2 |Si∩S|=1,|Sk∩S|=3.

不妨假设i

情形3 |Si∩S|=2,|Sk∩S|=2.

不妨假设i

子情形3.1 uiuk∈E(Cm).

记Cm-ui-uk～=因为×Cn是连通的,Si-S 中的每一个点在Si-1(当i=1 时,i-1=m) 中都存在邻点,且Sk-S 中的每一个点在Sk+1(当k=m 时,k+1=1) 中都存在邻点,那么G-S 是连通的,与假设矛盾.

子情形3.2 uiur,uruk∈E(Cm).

若Sr中存在某个点ωrt,该点在Si与Sk中的邻点集恰巧分别是Si∩S 与Sk∩S,那么G-S 存在孤立点,与假设矛盾.因此,Sr中的每个点在Si∪Sk-S 中至少存在一个邻点.因为|Si∩S|=2,|Sk∩S|=2,所以Sr中至多存在一个点ωrt′,该点在Si-S 或Sk-S 中不存在邻点,不妨假设该点在Si-S 中不存在邻点,那么该点在Sk-S 中存在邻点.由于×Cn-(Si∩S)∪{ωrt′} 是连通的,Sk-S 中的每一个点在Sk+1(当k=m 时,k+1=1) 中都存在邻点,而且Sk-S 中存在ωrt′的邻点,那么G-S 是连通的,与假设矛盾.若Sr中的每一个点在Si-S 中都存在邻点,那么×Cn-(Si∩S) 是连通的.由于Sk-S 中的每一个点在Sk+1(当k=m 时,k+1=1) 中都存在邻点,那么G-S 是连通的,与假设矛盾.

子情形3.3 在Cm中,ui到uk的最短路长大于2.因为Pm[{ui+1,···,uk-1}]×Cn与Pm[{uk+1,···,um,u1,···,ui-1}]×Cn都是连通的,并且Si-S 中的每一个点在Si-1与Si+1(当i=1 时,i-1=m;当i=m 时,i+1=1)中都存在邻点,Sk-S 中的每一个点在Sk-1与Sk+1(当k=1 时,k-1=m;当k=m 时,k+1=1) 中都存在邻点,所以G-S 是连通的,与假设矛盾.

情形4 |Si∩S|=1,|Sk∩S|=1,|Sp∩S|=2

不妨假设i

情形5 |Si∩S|=1,|Sk∩S|=1,|Sp∩S|=1,|Sx∩S|=1.

不妨假设i

由于m ≥5,那么uiuk,ukup,upux,uxui不可能都是Cm中的边,不妨假设uxui/∈E(Cm),则Pm[{up+1,···,ux,···,um,u1,···,ui-1}]×Cn-ωxy是连通的.

子情形5.1 k=i+1,p=k+1.

若vjvl∈E(Cn) 或vlvq∈E(Cn),那么Pm[{ui,uk}]×Cn-{ωij,ωkl} 或Pm[{uk,up}]×Cn-{ωkl,ωpq} 是连通的.因为Sp-{ωpq} 中的每一个点在Sk-{ωkl} 中都存在邻点,且Si-{ωij} 中的每一个点在Sk-{ωkl} 中都存在邻点,所以Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 是连通的.

当x=p+1 (或i-1) 时,因为Sp+1-{ωxy} 中的每一个点在Sp-{ωpq} 中都存在邻点(当x=i-1 时,Si-1-{ωxy} 中的每一个点在Si-{ωij} 中都存在邻点),所以G-S 是连通的,与假设矛盾.

当p+2 ≤x ≤i-2时,因为Sp-{ωpq}中的每一个点在Sp+1中都存在邻点,所以G-S是连通的,与假设矛盾.

若vjvl/∈E(Cn),且vlvq/∈E(Cn),那么Pm[{ui,uk}]×Cn-{ωij,ωkl} 和Pm[{uk,up}]×Cn-{ωkl,ωpq} 均不连通且不包含孤立点.当j=q 时,Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 不连通且不包含孤立点.当j/=q 时,因为Sp-{ωpq} 中的每一个点在Sk-{ωkl} 中都存在邻点,并且Sp-{ωpq} 可将Pm[{ui,uk}]×Cn-{ωij,ωkl} 中的各连通分支连接起来,所以Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 是连通的.

由于已经讨论了Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 是连通时的情况,所以接下来我们分析j=q 时,Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 不连通且不包含孤立点的情况.

当x=p+1(或x=i-1)时,因为Pm[{ui-1,ui}]×Cn-ωij是连通的(当x=i-1 时,Pm[{up,up+1}]×Cn-ωpq是连通的),所以通过Si-1可将Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq}中的各连通分支连接起来(当x=i-1 时,通过Sp+1可将Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq}中的各连通分支连接起来),从而可以得到Pm[{ui-1,ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 是连通的(当x=i-1 时,可以得到Pm[{ui,uk,up,up+1}]×Cn-{ωij,ωkl,ωpq} 是连通的).由于Si-1将连通的Pm[{up+1,···,ux,···,um,u1,···,ui-1}]×Cn-ωxy与Pm[{ui-1,ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 连接起来(当x=i-1 时,Sp+1将连通的Pm[{up+1,···,ux,···,um,u1,···,ui-1}]×Cn-ωxy与Pm[{ui,uk,up,up+1}]×Cn-{ωij,ωkl,ωpq} 连接起来),那么G-S 是连通的,与假设矛盾.

当p+2 ≤x ≤i-2 时,因为Pm[{up,up+1}]×Cn-ωpq是连通的,所以通过Sp+1可将Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 中的各连通分支连接起来.因此,Pm[{ui,uk,up,up+1}]×Cn-{ωij,ωkl,ωpq} 是连通的.由于V(Pm[{ui,uk,up,up+1}]×Cn-{ωij,ωkl,ωpq})∩V(Pm[{up+1,···,ux,···,um,u1,···,ui-1}]×Cn-ωxy)=Sp+1,那么通过Sp+1可得G-S 是连通的,与假设矛盾.

子情形5.2 k=i+1,p ≥k+2.

此时|Pm[{uk,···,up}]|≥3,由引理2 的证明中的子情形3.2 可知,此时|Pm[{uk,···,up}]|≥3,由引理2 的证明中的子情形3.2 知Pm[{uk,···,up}] ×Cn-{ωkl,ωpq} 是连通的.由于Si-{ωij} 中的每一个点在Sk-{ωkl} 中都存在邻点,那么Pm[{ui,uk,···,up}]×Cn-{ωij,ωkl,ωpq} 是连通的.

若x=p+1 (或i-1),因为Sp+1-{ωxy} 中的每一个点在Sp-{ωpq} 中都存在邻点(当x=i-1 时,Si-1-{ωxy} 中的每一个点在Si-{ωij} 中都存在邻点),所以G-S 是连通的,与假设矛盾.

若p+2 ≤x ≤i-2,因为Sp-{ωpq} 中的每一个点在Sp+1中都存在邻点,所以G-S 是连通的,与假设矛盾.

子情形5.3 k ≥i+2,p=k+1.

由Cm的对称性,类似于子情形5.2,可得G-S 是连通的,与假设矛盾.

子情形5.4 k ≥i+2,p ≥k+2.

此时|Pm[{ui,···,uk}]|≥3,|Pm[{uk,···,up}]|≥3,那么Pm[{ui,···,uk}]×Cn-{ωij,ωkl}与Pm[{uk,···,up}]×Cn-{ωkl,ωpq} 都是连通的.因为V(Pm[{ui,···,uk}]×Cn-{ωij,ωkl})∩V(Pm[{uk,···,up}]×Cn-{ωkl,ωpq})=Sk-{ωkl},所以通过Sk-{ωkl} 可知Pm[{ui,···,uk,···,up}]×Cn-{ωij,ωkl,ωpq} 是连通的.

若x=p+1 (或i-1),因为Sp+1-{ωxy} 中的每一个点在Sp-{ωpq} 中都存在邻点(当x=i-1 时,Si-1-{ωxy} 中的每一个点在Si-{ωij} 中都存在邻点),所以G-S 是连通的,与假设矛盾.

若p+2 ≤x ≤i-2,因为Sp-{ωpq} 中的每一个点在Sp+1中都存在邻点,所以G-S 是连通的,与假设矛盾.

通过上述情形讨论可得到与假设矛盾的结论,所以假设不成立.因此,G 是超点连通的.