关于树图中全控制数与全外部连通控制数比值的研究∗

庄蔚

(厦门理工学院应用数学学院，福建厦门361024)

0 引言

令G= (V,E)是一个没有孤立点的简单图,v是G中的一个点．v的开邻域N(v) = {u∈V|uv∈E}，闭邻域N[v]=N(v)∪{v}．点v的度数d(v)=|N(v)|．对于连通图G中的两个点u和v, 它们之间的距离d(u,v)是G中最短(u,v)-路的长度．G的直径diam(G)=max{d(u,v)|u,v∈V(G)}．我们将G中度为1的点称为叶子，与叶子相邻的点称为G的支撑点．连到至少两个叶子的支撑点称为强支撑点．将一个非平凡星（点数至少为2）的每条边都剖分一次，称这个图为分割星．

全控制是最重要的控制参数之一．在一个不含孤立点的图G中，若存在一个点集S，使得N(S)=V(G)，则称S是G中的一个全控制集．G的全控制数γt(G)=min{|S|:S是G中的全控制集}．一个基数为γt(G)的全控制集称为γt(G)-集．与全控制相关的结果可参见文献[1]. 近些年，人们提出了许多新的控制参数，其中一些参数与全控制数密切相关．在本文中，我们主要研究其中的一种控制参数，全外部连通控制数，这种参数可以看做是全控制数的一种变形．

Cyman在2010年首先提出全外部连通控制数的概念[2]，并做了相关的研究．令D是图G的一个全控制集，若点集V(G)D的导出子图是连通的，则称D是G的一个全外部连通控制集．G的全外部连通控制数γtc(G)=min{|D|:D是G中的全外部连通控制集}．一个基数为γtc(G)的全外部连通控制集称为γtc(G)-集．显然的，γt(G)≤γtc(G)．

在本文中，我们证明了对于没有强支撑点的树T，总是有．另外，我们也刻画了能够使上式等号成立的图类．

1 树图中全控制数与全外部连通控制数的比值问题

在本节中，我们的目标是研究树图中全控制数与全外部连通控制数的比值问题．根据全控制数与全外部连通控制数的概念，我们有下面的结论．

观察1[3]令G是一个连通图，且不是一个星图，那么在G中必然存在一个不含叶子的γt-集．

命题1[4]令D是一个连通图G的γtc-集，|G|≥3，最小度δ(G)=1．那么D包含了G的所有支撑点．进一步的，如果γtc(G)≤n−2，那么D也包含G中的所有叶子．

定理1令T是一个非平凡树，则

另一方面，给定任意的树T, 然后构造一系列的树图T0(=T),T1,T2,···，其中Ti+1是在Ti的基础上，通过增加一个点，并把这个点连到Ti的一个支撑点上得到的，i=0,1,2,···．通过观察1，在构造这些树图的过程中，每个Ti的全控制数都保持不变，但通过性质1和全外部连通控制数的定义，随着下标i的增大，每个Ti的全外部连通控制数一直都在增加．这意味着当n足够大时，会不断趋近于无穷大．所以在下文中，我们主要讨论不含强支撑点的树图．

下面，我们定义树T的点标记这个概念(这种点标记的方式在[6]中被首次提出)．首先对V(T)划分成三个点集S=(SA,SB,SC)，若一个点v∈Sx(x∈{A,B,C})，则说明v被字母x所标记．我们也可以说v的状态是x，或记为sta(v)=x．我们把(T,S)称为T的标记树．

令U 是这样一族标记树:

(i) 包含(P4,S0)，其中S0是在P4的基础上，给P4的两个叶子分配状态C，两个支撑点分配状态A;

(ii) 对于操作P1是封闭的（操作P1的说明如下）．

操作P1: 取某个(T′,S′)∈U，令v是(T′,S′)中一个状态为A的点．另取一条4-路v1v2v3v4和一个点u，分别连接u,v2两点和u,v两点．令sta(v1)=sta(v4)=C, sta(v2)=sta(v3)=A，sta(u)=B．（如图1所示）

图1 操作P1

令(T,S) ∈U 是一个标记树．那么必然存在一系列的标记树(P4,S0), (T1,S1),···,(Tk−1,Sk−1), (Tk,Sk)使得(Tk,Sk)=(T,S)，其中每个(Ti,Si)都是在(Ti−1,Si−1)的基础上通过操作P1获得．

接下来，我们先给出一些显然的结论．

观察2令T是一个点数不少于4的树，S是T的某种标记方式使得(T,S)∈U ．则T有下列性质:

(a) 一个点的状态是A当且仅当它是支撑点；

(b) 一个点的状态是C当且仅当它是叶子；

(c)SB∪SC是T的一个独立集, 且

(d)SA是T中唯一的γt-集；

(e) 取任意x∈SB∪SC，则V(T){x}是T的一个γtc-集．

根据观察2 (c)，2 (d) 和2 (e)，可以直接导出下面的引理．

推论1令T是一个非平凡树，S是T的某一种标记使得(T,S)∈U ．则

定理2令T是一个不包含强支撑点的非平凡树，则有，上式等号成立当且仅当存在某种标记S，使得(T,S)∈U ．

证明我们对树T的点数n来做归纳法(如前所述，我们只需要考虑没有强支撑点的树)．当n≤4时，结论显然成立．令n≥5，假设对于任意点数小于|T|的树T′，都有，该式等号成立当且仅当存在某种标记S′使得(T′,S′)∈U.

当diam(T)≤3，结论显然成立．进一步的，如果，则(T,S)=(P4,S0)∈U ．因此我们假设diam(T)≥4，令P=v1v2···vt是T的所有最长路中d(v3)最大的那条最长路．我们知道d(v2)=2．令D是T中一个不含叶子的γt-集，则v2,v3∈D．若(N(v3){v2})∩D/=∅，则令T′=T−{v1,v2}，令R是T′的一个γtc-集，我们有γtc(T′)+2 ≥γtc(T)，γt(T)−1 ≥γt(T′)．这意味着因此我们考虑(N(v3){v2})∩D=∅的情况．

声明1d(v3)=2.

如果d(v3)>2，那么d(v3) = 3，且v3是T的一个支撑点．假设d(v4)>2,u1是v4在P外的一个邻点．那么在T−u1v4中，包含u1的那个分支T1，要么是一个3-路u1u2u3，要么是一个4-路uu1u2u3(其余的每一种情况，要么类似于我们上面已经讨论的情况，要么与条件(N(v3){v2})∩D=∅相矛盾)．在任一种情况中，令T′是T−v4u1里包含v4的那个分支．则有γtc(T′)+4 ≥γtc(T)，γt(T)−2 ≥γt(T′)．这意味着

因此，d(v4)=2．于是令T′和T′′分别是T−v4v5中包含v5和v4的分支，我们有γtc(T′)+5 ≥γtc(T)，γt(T)−2 ≥γt(T′)．这意味着．如果γtc(T) =．上面的不等式等号都成立．特别的，有根

据归纳，存在某个标记S′，使(T′,S′)∈U ．若v5在S′中有状态B或C，那么根据观察2(e)，R′=V(T′){v5}是T′的一个γtc-集，于是R′∪(V(T′′){v4})是T的一个全外部连通控制集．即γtc(T′)+4 ≥γtc(T)，矛盾．因此v5在S′中有状态A．令S是在S′的基础上通过将v1和v3的叶邻点(leaf-neighbor)标记为C，v2和v3标记为A，v4标记为B而获得的．那么(T,S)可以在(T′,S′)的基础上通过操作P1而被获得．因此(T,S)∈U ．

通过声明1，我们有d(v3)=2．若d(v4)≥3，令u是v4在P外的一个邻点，由于(N(v3){v2})∩D=∅和P的选择方式，T−uv4中那个包含u的分支是一个P3，其中u是这个P3的一个叶子．当d(v4)≥3，令T′=T−{v1,v2,v3}；当d(v4)=2，令T′=T−{v1,v2,v3,v4}．类似于上面的讨论，我们总是有