与边控制相关的两类图∗

庄 蔚, 郝国亮

(1. 厦门理工学院 应用数学学院, 福建 厦门361024; 2. 东华理工大学 理学院, 江西 南昌330013)

0 引言

本文中考虑的所有的图都是简单、有限、无向图.文中未说明的术语与标记可参考[1].首先，令G=(V,E)是一个图.在G中,点v的开邻域N(v)={u|uv∈E(G)},闭邻域N[v]=N(v)∪{v}.用E(v)表示与点v相关联的边的集合.点v的度数d(v)=|N(v)|.度数为1的点被称为叶子.分别用δ(G)和∆(G)来表示G的最大度和最小度.被一个点集S⊆V(G)导出的图记为G[S].分别用和diam(G)来表示G的补图与直径.对于点u,v∈V(G), 令d(u,v)是两个点u和v之间的距离.g(G)和c(G)分别是G的围长和分支数，我们把一个基数为t的边集称为一个t-边集.

边控制这个概念被Mitchell 等人引入[2],并受到了广泛的关注[3−5].一个图G的边控制集D是一个边集，满足G中的每一条边要么在D中，要么与D中的某一条边相关联.G的边控制数, 标记为γ′(G), 是G的基数最小的边控制集的边数.一个最小边控制集被称为γ′-集.在[6, 7]中笔者引入了与边控制相关的两类图.

如果对于任意e∈E(), 都有γ′(G+e)<γ′(G), 则称图G是边控制临界图.一个边控制数等于k的边控制临界图称为k−边控制临界图, 简称为k−EDC图. 我们将点数至少为2的完全图也看作是边控制临界图.如果对于任意e∈E(G), 都有γ′(G−e)<γ′(G), 则称图G是边控制极小图.一个边控制数等于k的边控制极小图称为k−边控制极小图, 简称为k−EDM图.

首先我们给出一些直观的，但有用的结论.

观察1[6]令G是一个k−EDC图,S是G+e的一个最小边控制集, 则

(1)e∈S；

(2) |S|=k−1；

(3)u,v两点在G中的关联边都不在S中；

(4)G中没有孤立点；

(5) 若G是连通的，并且k≥2，则δ(G)≥2.

观察2[7]令G是一个k−EDM图，则

(1) 如果uv∈E(G)，D是G−uv的一个γ′-集，那么E(u)∩D=E(v)∩D=∅；

(2) 对于任意的e∈E(G)，都有γ′(G−e)=k−1.

观察3图G是一个边控制极小图当且仅当G的每一个非孤立点的分支都是边控制极小图.

观察4一个圈C是k−EDM图当且仅当|V(C)|=3k−2，其中k≥2.

观察5一个完全图G是k−EDM图当且仅当G=K2k.

观察4和5暗示对于任意的正整数k，都存在一个k−EDM图.另一方面，我们可以再构造一个图族{Gk,k≥3}，其中

V(Gk)={x,u1,v1,u2,v2,···,uk,vk},

E(Gk)={xu1,xv1,xu2,xv2,···,xuk,xvk,u1v1,u2v2,···,ukvk}.

从图族{Gk,k≥3}∪{K3,C4}可看出对于任意的正整数k, 都存在k−EDC图.

显然，K2是唯一的不包含孤立点的1−EDM图，K2,K2和K3是仅有的两个1−EDC图.进一步的，我们通过下面两个定理刻画出2−EDC图和2−EDM图.

对于一个简单图G=(V,E), 如果一个点u∈V(G), 那么N(u)表示u的邻点集, 点u的度d(u)=|N(u)|.如果x,y是G中的两个点, 则xy-路是一条分别以x和y为起点和终点的路.x与y这两点间的距离, 我们记为d(x,y), 表示最短的xy-路的长度.图G的直径diam(G)=max{d(u,v)|u,v是G中的两个点}.令S⊂V(G),x∈S, 如果在S⊂V(G)中存在一个点, 在S中只有一个邻点x, 我们称x针对于点集S有一个私有邻点.假设X,Y⊆V(G), 我们称点集X控制点集Y, 如果Y中的每一个点都至少连到X中的一个点.我们称一个图G为外平面图, 如果存在G的一个平面嵌入, 使得G中的每一个点都在这个平面嵌入的外部面的边界上.根据外平面图的定义, 我们可以看出一个2连通的外平面图一定有一个哈密顿圈.

在本文中, 我们研究了外平面图的全控制数.当外平面图的直径大于3时, 我们通过例子说明外平面图的全控制数可以任意大, 而当直径为2和3时, 我们给出了全控制数具体的上确界和下确界.这也暗示了一个直径不超过3的外平面图的全控制数可以在多项式时间内被计算出来.

定理1令G是一个没有孤立点的图，则G是2−EDM图当且仅当G∈{2K2,C4,K4}.

证明充分性显然.下面我们证明必要性.如果G是不连通的，那么G的每一个分支都是1−EDM图，因此G是2K2. 如果G是连通的，显然|G|≥4.假设|G|≥5.对于任意的边uv∈E(G)，都存在一条边u′v′控制G−uv中所有的边,其中u′,v′∈V(G){u,v}.显然,在G−uv中,V(G){u′,v′}是一个独立集.由于G是连通的, 存在一点w∈V(G){u,v,u′,v′}使得u′w∈E(G)或v′w∈E(G).不妨假设u′w∈E(G).现在考虑G−u′v′,uv和u′w不能被同一条边控制,与2−EDM图的定义矛盾.因此|G|=4.经过简单的验证可得,G是C4或K4.

类似的，我们有

定理2一个图G是2−EDC图当且仅当G∈{K4,K5,C4,2K2}.

假设D,D′是G中的两个边集, 在下文中, 我们用D→D′表示边集D可以控制边集D′, 即D′中的任意一条边都与D中的某条边关联.否则, 我们用DD′表示边集D无法控制边集D′.

在本文中，我们继续研究上面提到的两种图类的性质.另外，我们将刻画2−EDC图和2−EDM图.

1 边控制极小图

注意到, 在一个没有孤立点的图G中,G是k−EDM图当且仅当G∪tK1(t∈N) 是k−EDM图.因此在本文中, 我们只考虑不含孤立点的图.在本节中，我们研究边控制极小图.

命题1如果G是连通的k−EDM图, |E(G)|≥2, 那么δ(G)≥2.

证明当k= 2时, 结论显然成立.当k≥3时, 假设u为G中的叶子和uv∈E(G).因为G是连通的,且|E(G)|≥2, 必然存在e∈E(G){uv}与点v关联.在G−e中, 令D是最小边控制集.由观察2(1)可知D不能控制uv, 因此G中没有叶子.

由命题1，我们可以得到下面的结论.

推论1除K2外的树都不是边控制极小图.

进一步的，我们有

命题2如果G是连通的k−EDM图, 则G是2-连通图.

证明当k=1,2时, 结论成立.当k≥3时, 假设v是G中的割点,G−v有t个分支由命题1可得V(G1)和V(G2)都不是独立集. 令D1,D2分别是G1,G2的最小边控制集且γ′(G1) =k1,γ′(G2) =k2.显然,D1∪D2∪{uv}是G的边控制集, 其中u∈V(G2)∩N(v).因此,k1+k2≥k−1.现在考虑G−uv, 令D为G−uv的最小边控制集.根据观察2(1),v的关联边都不在D中.因此D= (D∩E(G1))∪(D∩E(G2)).那么|D∩E(G1)| ≥k1, |D∩E(G2)| ≥k2. 我们有k−1 = |D| =|D∩E(G1)|+|D∩E(G2)|≥k1+k2≥k−1，这暗示k1+k2=k−1和|D∩E(G1)|=k1.进一步的，由上面的条件D=(D∩E(G1))∪(D∩E(G2))我们可得γ′(G[V(G1)∪{v}])≤k1.通过类似的推导，γ′(G[V(G2)∪{v}])≤k2.因此γ′(G)≤k1+k2=k−1，矛盾.

下面我们要证明在图中删掉一个点或增加条边，边控制数至多减少1.

命题3如果G是连通的k−EDM图,k≥2, 那么对于任意的e∈E(), 都有k−1 ≤γ′(G+e)≤k.

证明当k= 2时, 结论成立.当k≥3时, 任取令D为G−uv′的最小边控制集.则D∪{uv′}是G+uv的边控制集, 因此假设存在使得令D′是G+u1v1的最小边控制集, 显然u1v1∈D′. 构造边集D′′= (D′{u1v1})∪({u1v′,v1v′′}), 其中v′∈N(u1){v1},v′′∈N(v1){u1}.容易看出,D′′是G的边控制集, 但|D′′|≤k−1, 矛盾.

因此k−1 ≤γ′(G+uv)≤k, 结论成立.

命题4如果G是连通的k−EDM图, 那么对于任意的v∈V(G), 都有γ′(G−v)=k−1.

证明当k=1时, 结论成立.当k≥2时, 令D为G−v的最小边控制集,u∈N(v), 则D∪{uv}是G的边控制集,因此|D∪{uv}|≥k,即|D|≥k−1. 现在令D1是G−uv的最小边控制集.注意到v的关联边都不在D1中,因此D1也是G−v的边控制集.于是γ′(G−v)≤|S1|=k−1, 即γ′(G−v)=k−1.

我们在2015年研究了3−EDM图的性质，并得到了下面的结果.

定理3[7]令G是一个连通的3−EDM图, 则diam (G)≤3.

上述定理中给出的界是紧的，我们可以用7圈作为例子.在同一篇文章中，我们也给出了k−EDM图的直径的上界，其中k≥4.

定理4[7]令G是一个连通的k−EDM图,k≥4, 则diam(G)≤2(k−1).

下面我们将开始刻画所有的3−EDM图，首先我们先讨论G不连通的情况.

定理5令G是一个不连通的图，且不包含孤立点.那么G是3−EDM图当且仅当G∈{3K2,K2∪C4,K2∪K4}.

证明充分性显然, 下面我们讨论必要性. 因为G中不含孤立点,G的分支数c(G) = 2或3, 且每个分支中都至少有一条边.若c(G)=3, 则每个分支只能是K2. 若c(G)=2, 那么两个分支分别是1 −EDM图和2−EDM图.这意味着G是K2∪C4或K2∪K4.

在本节的最后，我们讨论G是连通的情况.其中H1,H2,H3如图1所示.

图1 H1, H2, H3Fig 1 The Graphs H1, H2 and H3

定理6G是连通的3−EDM图当且仅当G∈{H1,H2,H3,K3,3, K6,C7}.

证明充分性显然,下面我们讨论必要性.通过定理3，diam(G)≥3.当diam(G)≥1时，显然有.因此我们考虑2 ≤diam(G)≤3的情况.显然, |G|≥6，否则我们将总是可以在G中找到一个基数至多为2的边集来控制G中其他的边.当|G|=6时, 我们取G中长度最短的奇圈C，那么|C|=3.通过简单的验证, 可得GK6，与条件diam(G)≥2矛盾.因此G中没有奇圈, 即G是二部图.令G=(A,B).显然|A|=|B|=3.由于γ′(G)=3, 因此GK3,3. 下面我们要说明当|G|≥7时, ∆(G)≤4.

首先，容易看出G中所有点的度数都小于|V|−1.假设存在一点x使得d(x)≥5,令N(x)={x1,x2,x3,x4,x5,···}.由于d(x)|V|−1, 不失一般性, 必然存在y∈V(G)N[x]且yx1∈E(G).在G−xx1中, 令D为最小边控制集.于是D{xx2,xx3,xx4,xx5,yx1}, 矛盾.因此∆(G)≤4.

当∆(G) = 2时,GC7.当∆(G) = 4时, 取一个最大度点a,N(a)中的每一个点都连到V(G)N[a]中的至多一个点.令N(a) = {a1,a2,a3,a4},b1,b2∈V(G)N[a].可以注意到对于任意的v∈V(G)N[a], 都有|N(v)∩N(a)|1.否则，假设a1是唯一一个同时连到v和a的点, 那么在G−aa1中没有一个2-边集可以控制{a1v,aa2,aa3,aa4}.

断言1V(G)N[a]中的每个点都连到N(a)中的某个点.

用反证法,不妨假设存在一个点b2,在N(a)中没有邻点.因为G是连通的，不失一般性，令a1b1∈E(G).那么b1在N(a)中有一个除a1外的邻点，设为a2.从条件diam(G)≤3可知d(a,b2)=3.令P=aaicb2是a和b2间的最短路，其中ai∈N(a),c∈V(G)(N[a]∪{b2}).若c=b1, 则必然有一个点b3∈V(G)N[a]连到b2.在这种情况下没有一个2-边集可以控制G−aa1中的所有边.反证，若cb1, 我们也能获得一个类似的矛盾.因此断言1成立.

根据上面的分析, 我们有V(G)N[a]={b1,b2}, 且在同构意义下, 有a1b1,a2b1,a3b2,a4b2∈E(G).在G−a1a的所有2边集中,只有{a2b1,a3a4}有可能控制所有的边,即a3a4∈E(G).同理,有a1a2∈E(G).进一步的,a1a3,a1a4,a2a3,a2a4E(G).又因为G中不存在割点,b1b2∈E(G).综上所述,GH3.

下面我们研究∆(G)=3的情况.由于G是连通的3−EDM图, diam(G)≥2, |G|≥7, 通过简单的推导可知g(G)≤4.于是我们最后只需讨论g(G)=3和g(G)=4的情况.

当g(G)=3时,令C1=abc是G中的一个3圈.因为G是2-连通的,因此C中至少有两个三度点.不失一般性,假设d(a)=d(b)=3,d(c)=2.则在G−ab中,没有一个2边集能控制{ac,bc}.因此有d(a)=d(b)=d(c)=3.令aa1,bb1,cc1∈E(G), 其中, {a1,b1,c1}⊆V(G)V(C1).若a1=b1=c1, 则G=K4, 与γ′(G)=3矛盾. 下面分两种情况讨论：

情形1.1a1,b1,c1是三个不同的点.

容易看出{aa1,b1c1}是G−bc的最小边控制集,即b1c1∈E(G).同理,a1c1,a1b1∈E(G). 因此d(a)=d(b)=d(c)=d(a1)=d(b1)=d(c1)=3.由于G是连通图, ∆(G)=3,因此V(G){a,b,c,a1,b1,c1}=∅,与|G|≥7矛盾.

情形1.2不失一般性,a1=b1c1.

因为c不是割点,d(a1)=3.令a2∈N(a1){a,b}. 显然a2c1.那么d(a2,c1)=2.否则，总是存在一条边e和边集D,使得D不能被G−e中的2-边集控制.令x∈N(c1)∩N(a2).则当d(a2)=d(x)=d(c1)=2时，GH2.如果d(x)=3或d(a2)=3,γ′(G−xa2)≥3.如果d(c1)=3,γ′(G−c1x)≥3.都与3−EDM图的定义矛盾.

当g(G)=4时, 令C2=abcd是G中的一个4圈.因为G是2-连通的, 因此C中至少有两个三度点.下面我们分两种情况讨论：

情形2.1C2包含两个相邻的3度点，假设为c和d.

存在两点c1,d1V(C2)使得cc1,dd1∈E(G).显然,c1d1.考虑G−cd,令{e1,e2}是最小边控制集.不妨设ad被e1控制,由于cc1,dd1,bc不能有同一条边控制,因此e1必须控制cc1或bc.若e1控制cc1,e1=ac1.进一步的,e2=bd1.在G{a,b,c,d}中,令P=c1x1x2···xt−1d1是c1和d1间的最短路，则|P|≥2.但在G−x1x2中,不存在一个2边集能控制所有的边,矛盾.若e1控制bc,e1=ab.进一步的,e2=c1d1.令V1=V(G){a,b,c,d,c1,d1}.我们可以推导出V1是一个独立集.注意到d(x)≥2和xc1E(G), 我们有xd1∈E(G), 因此|V1|=1.那么,G∼=H1.

情形2.2不失一般性,d(a)=d(c)=3,d(b)=d(d)=2.

令aa1,cc1∈E(G)，其中a1,c1V(C2). 由于G中没有割点,a1c1.因此再没有一个2-边集可以控制G−aa1中的所有边.

2 边控制临界图

我们在[6]中研究了边控制临界图的性质.在同一篇文章中，我们获得了3−EDC图的直径的一个上确界和连通k−EDC图的直径的一个上界，其中k≥4.

定理7[6]如果G是连通的3−EDC图, 那么diam(G)≤2.

定理8[6]如果G是连通的k−EDC图,k≥4, 那么diam(G)≤3k−6.

下面我们将刻画3−EDC图.

定理9令G是一个不连通的图，那么G是3−EDC图当且仅当G∈{K2∪C4,K2∪K4,3K2}.

证明充分性是显然的, 下面我们讨论必要性.由于G中没有孤立点,G的分支数c(G)=2或3, 且每个分支中都至少有一条边.若c(G)=3,每个分支的边控制数都是1.这意味着每个分支都是K2或K3.通过简单的验证,G是3K2.若c(G)=2, 不妨令G=G1∪G2,γ′(G1)=1,γ′(G2)=2.那么G1是K2或K3.同时, 由于G2是2−EDC图,G2∈{K4,K5,C4}.通过简单的验证, 可以得到G是K2∪C4或K2∪K4.

图2 F1, F2, F3Fig 2 The Graphs F1, F2 and F3

最后我们考虑G是连通的情况.

定理10令G是一个连通图，那么G是3−EDC图当且仅当G∈{F1,F2,F3,K3,3,K6,K7}，其中F1,F2和F3如图2所示.

证明充分性是显然的, 下面我们讨论必要性.令G是一个连通3−EDC图, 由定理7可知,G的直径是1或2.当直径为1时, 只能是完全图K6和K7.如果直径为2, 由观察1(5)可知G包含圈.进一步的，3 ≤g(G)≤4(若g(G)=5, 容易推出矛盾).下面我们讨论g(G)=4的情况.假设G中存在奇圈, 取其中长度最短的奇圈C.|C| = 5.令C=abcde.因为G不是5圈，存在一个点f∈V(G)V(C), 它连到C中的某个点,不妨设为a.注意到{af,cd}E(G), 因此,V(G)(V(C)∪{f})∅.任取g∈V(G)(V(C)∪{f}), 容易看出fg,bg∈E(G).但是, 在G+ce中, 每个包含ce的2边集都无法控制{ab,bg,gf,af}.因此G中没有奇圈,即G是二部图.令G=(A,B).显然, |A|≥3, |B|≥3.不妨假设|A|≥4.任取a1,a2,a3,a4∈V(A).根据观察1(3), 在G+a1a2中, 不存在包含a1a2且控制所有与a3或a4相关联的边的2边集.因此, |A|=3.同理|B|=3.这就可以推出G=K3,3.否则,γ′(G)≤2.

最后, 讨论g(G)=3的情况.我们给出如下断言

断言2G中的每个3圈都有且仅有一个点的度为|V|−1.

首先我们证明G中的每一个3圈都至少有一个点的度数是|V|−1.使用反证法, 假设有一个3圈abc, 它的每个点的度数都小于|V|−1.下面我们分三种情形讨论：

情形3存在d∈V(G){a,b,c}, 使得ad,bd,cdE(G).

由于diam(G)=2且cdE(G), 必然存在d1∈V(G){a,b,c}, 使得dd1,cd1∈E(G).因为G中没有叶子，必存在d2∈V(G), 使得dd2∈E(G).令A=V(G){a,b,c,d,d1}.|A|≥2.同时,G[A]是一个团且|A|<3.因此|A|=2.令A{d2}={d3}.容易看到bd3,cd3∈E(G).进一步的, 有ad1∈E(G).但是在G+bd中, 不存在一个包含bd的2边集S使得S→{ac,cd1,ad1,d2d3}, 矛盾.

情形4存在d∈V(G){a,b,c}, 使得d恰好与a,b,c中的一个点相连.

不失一般性,令ad,bdE(G),cd∈E(G).因为d(c)<|V|−1,必然存在d1∈V(G),使得cd1E(G).d1连到a或b, 不妨设为a(若ad1,bd1E(G)，证明将类似于情形3.由于diam(G)=2, 因此有两种子情形：

子情形4.1dd1∈E(G).

令A=V(G){a,b,c,d,d1}.G[A]是一个团且b连到A中的每一个点.如果|A|≥2,a会连到A中的每一个点.但在G+cd1中, 每个包含cd1的2边集都无法控制E(G[{a,b}∪A]).另一方面，如果|A|=1, 令A={a1}.由于{cd,ab}E(G), 因此a1d1∈E(G).这就推出{a1d1,ac}→E(G), 矛盾.于是dd1E(G), 那么我们有下面的子情况.

子情形4.2存在d2∈V(G){a,b,c,d,d1}, 使得dd2,d1d2E(G).

由于{ac,d1d2}E(G),V(G){a,b,c,d,d1,d2}∅.令d3V(G){a,b,c,d,d1,d2},我们有bd3∈E(G).进一步的,有bd2∈E(G),dd3E(G).但在G+cd1中,不存在一个包含cd1的2边集S使得S→{ab,bd3,dd3,dd2,bd2},矛盾.

情形5V(G){a,b,c}中的每个点都与a,b,c中的至少两个点相连.

由于d(a)<|V|−1, 必然存在a1∈V(G){a,b,c}使得aa1E(G), 于是有a1b,a1c∈E(G).同理, 存在b1,c1∈V(G){a,b,c,a1}使得bb1,cc1E(G),ab1,cb1,bc1,ac1∈E(G).因为{a1c,ac1}E(G), 我们有V(G){a,b,c,a1,b1,c1}∅.令d∈V(G){a,b,c,a1,b1,c1}.我们有a1d,c1d∈E(G).但在G+bb1中, 每个包含bb1的2边集都无法控制{ac,ca1,a1d,dc1,ac1}, 矛盾.

因此G中的每个3圈都至少有一个点的度数是|V|−1, 现在我们证明G中的每个3圈都只有一个点的度为|V|−1.

使用反证法,假设G中有一个3圈a′b′c′,d(b′)=d(c′)=|V|−1.显然,|V(G){a′,b′,c′}|≥3.若|V(G){a′,b′,c′}|=3, 那么通过简单的验证有G[V(G){a′,b′,c′}]是一个团. 由于G不是完全图，我们总是可以获得一个可以控制E(G)的2-边集，这是不可能的.因此, |V(G){a′,b′,c′}|≥4.令a1,a2,a3,a4∈V(G){a′,b′,c′}.注意到V(G){a′,b′,c′}不是一个独立集，不妨设a1a2∈E(G), 那么a3a4∈E(G).进一步的,a′a1∈E(G).类似的,a′连到V(G){a′,b′,c′}中的每一个点.根据G不是一个完全图，我们可以得到G[V(G){a′,b′,c′}]不是一个团，不妨设a2a3E(G).那么在G+a2a3中, 每个包含a2a3的2边集都无法控制{b′c,b′a4,c′a4,a′a1}, 矛盾.

因此断言2成立.即G中的每个3圈都有且仅有一个点的度为|V|−1.

现在我们要说明G中有且仅有一个点的度为|V|−1.由断言2可知存在性成立,下面说明唯一性.假设存在x,y∈V(G)使得d(x)=d(y)=|V(G)|−1.取z∈V(G){x,y}.显然有xy,xz,yz∈E(G).即xyz是G中的3圈,这与断言2矛盾.因此G中有且仅有一个点x的度为|V|−1.又由于每个3圈上都有度为|V|−1的点,于是每一个3圈都包含x.这暗示|G|≥7.又显然|G|<8, 因此|G|=7.令xx1x2是G中的一个3圈，V(G){x,x1,x2}={a1,a2,a3,a4}.显然, {a1,a2,a3,a4}不是独立集.不妨令a1a2∈E(G), 那么a3a4∈E(G).这时GF1.否则,不失一般性, 有a2a3∈E(G).于是a1a4∈E(G).如果此时G中没有其它的边, 则GF2.若G{F1,F2}, 那么不失一般性，a1a3∈E(G)或ba1∈E(G).如果a1a3∈E(G)，我们有a2a4∈E(G),进一步的,有ba1∈E(G).注意到两个3圈aba1和a2a3a4没有公共点,矛盾.如果ba1∈E(G),则有ca4∈E(G).进一步的,有ca2∈E(G).同理, ba3∈E(G).这时图G中不会再有其它的边, 否则G中总会出现两个没有公共点的3圈.因此G≌F3.