特定双罗马控制数的刻画

张 宁，叶淼林，张子杰

（安庆师范大学 数理学院,安徽安庆 246133）

控制数和控制集的概念最早是由Ore[1]提出的，根据罗马帝国的统治历史，Stewart[2]于1999年首次提出了罗马控制的概念，经过多年的讨论和发展，Beeler[3]等人于2016年在此基础上改进了罗马防御战路，推广到了双罗马控制函数，研究给出了连通图的双罗马控制数的一个上界，引起了广泛的关注。2017年，Ahangar[4]等人给出了路径Pn，圈Cn的双罗马控制数的准确值，证明了二部图和弦图的双罗马控制问题是NP完备的。2018年，陈优[5]刻画了几类特殊图的双罗马控制数，Yue[6]研究给定最小度的图和直径为2的图，并用线性时间算法描述了协图的双罗马控制数。2021年，杜良丽[6]讨论得出了笛卡尔积运算下，格子图P2□Pm的双罗马控制数。2022年谢智红[7]等人借用围长、周长等图论工具，给出含圈图的双罗马控制数的若干界限。2023年Erovnik[8]总结了历年来双罗马控制已有的结论，并给出一些公开的问题和猜想。

在此基础上，本文继续对图的双罗马进行讨论。首先从双罗马控制数和最大度之间的关系出发，给出图G是连通的一个必要条件，其次结合树和块图所具有的特殊结构性质，刻画得出特定双罗马控制数的相关结论。

1 预备知识

设G=(V(G),E(G))是一个图，V(G)是图G的顶点集，E(G)是图G的边集，阶数n(G)=|V(G)|，边数m(G)=|E(G)|。对于任意的v∈V(G)，v的开邻域指v的所有邻点构成的集合，即N(v)={u|uv∈E(G)}，闭邻域N[v]=N(v)⋃{v}，记ˉ[v]=V(G)-N[v]。顶点v的度指与v相邻的点的个数，即deg(v)=|N(v)|，记作d G(v)，Δ(G)表示图G的最大度，δ(G)表示图G的最小度。对于集合S⊆V(G),定义集合的开邻域为集合的闭邻域为N[S]=N(S)⋃S，G[S]表示由顶点集S导出的子图，即删去V(G)-S的所有点及与之关联的所有边。如果图G的分支ω(G)=1，则称G是连通图，否则称G是不连通的。如果G只有一个顶点，则称G是平凡图，否则称G是非平凡图。Kn表示n阶完全图，Pn表示阶数为n的路，Cn表示阶数为n的圈，无圈的连通图称为树。如果B⊆G，B没有割点且真包含B的子图至少有一个割点，则称连通子图B是块，如果G的每个块都是完全图，则称G是块图。设V(G)={u1,u2,…,up}，V(H)={v1,v2,…,vq}，定义两个简单图G和H的笛卡尔积运算：顶点集为V(G)×V(H)，边集为所有形如(u1,v1)(u2,v2)的集合，满足：v1=v2，u1u2∈E(G)或者u1=u2，v1v2∈E(H)，记作G□H。

接下来，定义本文涉及到的两类控制以及各自对应的控制数，并给出证明中所用到的引理。

定义1[3]对于S⊆V(G)，如果N[S]=V(G)，则称顶点集S是图G的一个控制集，控制集的最小基数称为控制数，记作γ(G)，即γ(G)=min{|S||S是G的控制集}，图G中，基数为γ(G)的控制集称为G的γ(G)-集。

定义2[3]设函数f:V(G)→{0,1,2,3}，令={v∈V(G)|f(v)=i,i=0,1,2,3}，若f满足条件：

（1）如果f(v)=0，则v至少有两个邻点在中或者v有一个邻点在中；

（2）如果f(v)=1，则v至少有一个邻点在中。

则称f是图G的双罗马控制函数，简记为DRDF f。函数f:V(G)→{0,1,2,3}与顶点划分=间存在一个一一对应，可记作双罗马控制函数的权定义为所有顶点的赋值之和，即最小权称为图G的双罗马控制数，记作γdR(G)，即γd R(G)=min{ω(f)|f是G的双罗马控制函数}。图G中，权为γdR(G)的双罗马控制函数称为G的γdR(G)-函数。

引理1[3]在图G的权为γdR(G)的双罗马控制函数中，一定存在γdR(G)-函数，没有顶点赋值为1。

引理2[3]对任意的图G，2γ(G)≤γdR(G)≤3γ(G)。

引理3[3]对任意的树T，2γ(T)+1≤γdR(T)≤3γ(T)。

引理4[4]如果G是一个非平凡的块图，则γdR(G)≥2γ(G)+1。

引理5[5]设G是一个连通图，是G的一个γdR(G)-函数，是G的γ(G)-集，则有下列性质：

（a）是独立集，与之间没有边；

（b）中任一点都与中的某点相邻；

（c）若G是一个树或块图，则中任意两点都没有公共邻点，且中的任一点都和中的某点相邻。

引理6[6]设G是n阶图，最大度为Δ(G)，则γdR(G)≤2n(G)-2Δ(G)+1。

2 主要结果

定理1设G是n阶简单图，最小度δ(G)≥2，如果γdR(G)+2Δ(G)=2n(G)+1，则G是连通图。

证明假设G不是连通图，设G1,G2,…,Gk是G的k个分支，其顶点集分别为n(G1),n(G2),…,n(Gk)，不失一般性，令Δ(G)=Δ(Gk)，根据条件，有

由引理6知对于每个Gi，满足γdR(Gi)≤2n(Gi)-2Δ(Gi)+1，又因为对任意的i有Δ(Gi)≥δ(Gi)≥2，从而

因此只能k=1，故G是连通图。

下面给出满足γdR(G)+2Δ(G)=2n(G)+1的n阶连通图G的一个性质。

定理2设G是n阶简单图，最大度为Δ(G)，如果γdR(G)+2Δ(G)=2n(G)+1，则对于每个最大度顶点v，有：

（1）N(v)的每个顶点至多和Nˉ[v]中的一个顶点相邻；

（2）G[[v]]是无边图。

证明令v是V(G)中一个度最大的顶点，即Δ(G)=deg(v)。考虑图G的双罗马控制函数f，使得

计算上述定义的DRDF,f的权，即

此时，γdR(G)=ω(f)，因此我们构造的f是图G的γdR(G)-函数。

（1）记w是v的一个邻点，利用反证法，假设w至少与[v]中的两个顶点相邻，即N(w)⋂[v]≥2，重新定义一个函数g，使得：

根据双罗马控制函数的定义，上述定义的函数g是一个DRDF，g的权

这样，找到了一个权比f小的DRDF,g与f是图G的γdR(G)-函数矛盾，因此，N(v)的每个顶点至多和ˉ[v]中的一个顶点相邻。

（2）如果u∈ˉ[v]有一个邻点在[v]中，记作w。定义函数h，使得：

按上述构造的函数h满足DRDF的定义，且h的权

通过计算，说明h的权比f的权小，与f的权是最小的矛盾，故ˉ[v]中任意两点都不相邻，即G[[v]]是无边图。

定理3如果G是n阶树或非平凡的块图，是图G的γdR(G)-函数，是G的γ(G)-集，则γdR(G)=2γ(G)+1当且仅当存在一个度为n(G)-γ(G)的顶点。

证明充分性

假设G有一个顶点v，deg(v)=n(G)-γ(G)，若是G的一个DRDF函数，令

计算得出g的权

由引理3和引理4知，对于树或者非平凡的块图G，有2γ(G)+1≤γdR(G)=ω(f)≤ω(g)=2γ(G)+1，从而γdR(G)=2γ(G)+1。

必要性

此时定义的函数g符合双罗马控制函数的定义，则g的权

得到一个权比f小的双罗马控制函数g，与f是γdR(G)-函数矛盾，所以中任意两点都不相邻。又因为G中没有连接{v}与的边，由引理5（c）知因此deg(v)==n(G)-γ(G)。

定理4如果G是n阶树或非平凡的块图，是G的一个γdR(G)-函数，是G的γ(G)-集，则γdR(G)=2γ(G)+2当且仅当

（1）G中没有度为n(G)-γ(G)的顶点；

（2）G有两个顶点v和w，使得|N[v]⋃N[w]|=n(G)-γ(G)+2。

证明充分性

因为G没有度为n(G)-γ(G)的顶点，所以由引理3，引理4，定理3知γdR(G)>2γ(G)+1，如果G有两个顶点v和w，使得|N[v]⋃N[w]|=n(G)-γ(G)+2，重新构造DRDF g=，使得：

则双罗马控制函数g的权

所以2γ(G)+1<γdR(G)=ω(f)≤ω(g)=2γ(G)+2，故γdR(G)=2γ(G)+2。

必要性

对于一个γdR(G)-函数f=且γdR(G)=2γ(G)+2，是G的γ(G)-集，满足等式组：

（2）G中存在一个k个顶点的集合Wk使得=n(G)-γ(G)+k。

证明必要性

设f=是G的γdR(G)-函数，权为2γ(G)+k，即=2γ(G)+k。

首先证明（1）。

假设结论不成立，即存在整数t0，有1≤t0≤k-1，且G存在一个t0个顶点的集合使得=n(G)-γ(G)+t0，由定理3知t0≥2（否则，若t0=1，则γdR(G)=2γ(G)+1，与条件γdR(G)=2γ(G)+k矛盾，这里k≥2）。设DRDFf′=其中

根据双罗马控制函数的定义和定理条件，有

另一方面，假设γdR(G)=2γ(G)+m，其中m≥k+1，即2≤k≤m-1，由必要性（1）知G中不存在t（1≤t≤m-1）个顶点的集合Ut使得=n(G)-γ(G)+t，这与条件（2）G中存在k（2≤k≤m-1）个顶点的集合Wk使得=n(G)-γ(G)+k矛盾。因此γdR(G)=2γ(G)+k。

3 结 论

控制数一直是图论的经典问题，其形式多种多样。本文从连通图的双罗马控制数出发，描述了最大度条件下给定双罗马控制数的图所具有的性质，给出判断连通图的必要条件。根据树和块图的相关结论，研究得出γdR(G)=2γ(G)+k(1≤k≤γ(G))的充要条件，建立起双罗马控制数与控制数之间的关系，描绘出在此特定双罗马控制数下图所具有的特点，拓展了n阶树或非平凡的块图的结构，丰富了对双罗马控制数的研究。