区间图Total-罗马控制性质研究

Total-Roman Domination Property on Interval Graphs

摘要: Total-罗马控制函数是函数f:V(G)→{0,1,2}，满足条件：1) 对G中任意函数值f(u)=0的顶点u，至少存在一个邻居v使得函数值f(v)=2；2) 由控制集{k|f(k)≥1且k∈V(G)}诱导的子图没有孤立点存在。结合3阶及以上区间图，本文主要探索了基于total-罗马对的定理，研究了团和路径的不同结合图类中total-罗马控制数等内容，以示例辅助理解，证明了任意阶团的total-罗马控制数为3、相交团的并的total-罗马控制数不超过4等性质。

Abstract: Total-Roman Domination Function is the function f:V(G)→{0,1,2}, which satisfies the following two conditions: 1) for any vertex u with f(u)=0, there is at least one neighbor v with f(v)=2；2) No outliers exist for a subgraph induced by a control set {k|f(k)≥1 and k∈V(G)}. Combined with interval graphs of order 3 and above, this paper mainly explores the Total-Roman control number based on the theorem of Total-Roman pairs, studies the Total-Roman control number of different associative graph classes of groups and paths, and proves that the total-Roman control number of any order group is 3, and the Total-Roman control number of union of intersecting groups is not more than 4 and other properties.

1. 引言

区间图(Interval Graph)是对应到数轴上满足特定关系、以一组区间为表现形式的相交图，称数轴上的区间为区间表示。若各区间长度一致，则称该区间图为单位区间图 [1] 。区间图在电路设计、物流调度与网络管理问题等方面有重要运用，是图论研究中的热点图类之一 [2] 。

控制函数旨在搜索查找出一个顶点集S，使得图中该集合外的顶点至少与S中的一个顶点相邻。罗马控制函数(Roman Domination Function, RDF)将图的顶点集赋值为0、1、2，要求函数值为0的顶点至少要拥有一个函数值为2的邻居。在此基础上，total-罗马控制函数(Total Roman Domination Function, TRDF)增加了条件，即要求搜索查找出的顶点集S的诱导子图中没有孤立点存在 [3] 。

1999年，Stewart [4] 在《Scientific American》杂志上发表的《Defend the Roman Empire》一文中首次提出了包围罗马帝国的军队调控策略，通过调动各城市内驻扎的军队，保护罗马帝国免受外界多次攻击。自此，罗马控制问题引起广泛关注。2003年，Michael及其团队在《Discrete Mathematics》上接连发表了《Defending the Roman Empire from multiple attacks》《Defending the Roman Empire-A new strategy》等文章，研究保护罗马帝国的新型防守策略，推动罗马控制问题走向研究热潮 [5] [6] 。随时间发展，罗马控制问题得到变形，如双罗马控制、完全罗马控制和total罗马控制。total-罗马控制作为衍生问题之一，要求制定出特殊方案使得以下两个条件成立：① 在某座城市没有军队驻守的情况下，该城市的某一座邻居城市中一定驻守着两支军队，可使在危难来临前，邻居城市中的军队可分派一支前往保护该城市；② 拥有军队驻守的城市之间存在联系，即没有孤立的城市存在。2008年，Mathieu Liedloff等人研究了罗马控制在图类上的运用，表明区间图上的罗马控制数可用在线性时间内计算出来，证明存在多项式时间算法可用于计算无AT-图以及带有d-octopus的图的罗马支配数 [7] 。在2009年前，罗马控制函数及其变形如弱罗马控制函数等问题经常处于热点研究状态 [8] [9] [10] [11] 。2013年，Liu和Chang介绍了图中total-罗马控制函数的概念 [12] 。在 [13] [14] 中，作者对total-罗马控制函数继续进行研究，推动了total-罗马控制及罗马控制问题的发展。2018年，杨洪等人研究了区间图上的罗马控制，设计出求解罗马控制数的动态规划算法 [15] 。同年，Jafar Anjadi等人研究了total-罗马控制上的Nordhaus-Gaddum不等式，将total-罗马控制数与补图、图中所有顶点之间的最小度联系起来，得出系列不等式关系 [16] 。2020年，Jafar Amjadi继续给出total-罗马控制方面的钻研成果，开始了关于total-罗马控制在图中细分数的研究 [17] 。经常与其他控制相结合，total-罗马控制的研究前途广泛，未来还可应用于不同图类。

如下图1所示，本文主要从两个方面来刻画total-罗马控制函数。首先在文章第2节，介绍区间图、total-罗马控制函数等基础知识；在第3节介绍total-罗马对，以此为第一方面对total-罗马控制函数所具备的性质进行刻画，证明相关定理的正确性；在第4节介绍区间图中关于团、路径、团与团的并、团与路径的并等图的total-罗马控制数，是本文在第二方面的刻画；第5节，总结全文。

Figure 1. Frame of this paper

图1. 文章框架

2. 符号和预备知识

图(Graph)是由点、边以及各点之间存在的邻接关系所构成的三元组，用符号表示为 $G=\left(V\left(G\right),E\left(G\right)\right)$ ，其中 $V\left(G\right)$ 和 $E\left(G\right)$ 分别表示图G的顶点集和边集。若一个图拥有n个顶点，则称 $\left|V\left(G\right)\right|=n$ 为图的阶数，称该图为n-顶点图。区间图(Interval Graph)是对应到数轴上满足特定相交关系的图类，图中顶点与数轴上的区间一一对应。本文研究简单、无向且有限的区间图，即图中不含重边与圈、边上没有方向以及图的边集与顶点集中元素有限。

在图G中，对于顶点集中任意两个顶点u、v，若 $uv\in E\left(G\right)$ ，则称u、v互为邻居，也称此两点满足邻接关系。用 $N\left(u\right)=\left\{v|uv\in E\left(G\right)\right\}$ 表示任意顶点u的开邻域、 $N\left[u\right]=N\left(u\right)\cup \left\{u\right\}$ 表示其对应闭邻域。对于任意两个满足 $A\subseteq B$ 的顶点集A、B，用 $B-A$ 表示从集合B中删去A中所有元素，也写作 $B\backslash A$ 。若A是单元素集，不妨设 $A=\left\{u\right\}$ ，则 $B-A=B-\left\{u\right\}$ ，也即是 $B-u$ 。对于任意顶点集 $S\subseteq V\left(G\right)$ ，其诱导子图 $G\left[S\right]$ 保留了S中所有点及各点在图G中所对应的边，也是一个图。

团(Clique)是指任意两个顶点之间都存在邻接关系的图。路径(Path)具有顺序，设n阶路径 $P=\left(u_1,u_2,\cdots ,u_n\right)$ ，称第一个顶点 $u_1$ 、最后一个顶点 $u_n$ 分别为P的左、右端点，其中 $n\in N_{+}$ 。设存在任意正整数s、t使得 $P_1=\left(u_1,u_2,\cdots ,u_s\right)$ 与 $P_2=\left(v_1,v_2,\cdots ,v_t\right)$ 是两条顶点集互不相交的路径，这两条路径按照不同顺序首尾相连后，分别可以表示为两条新路径，即 $P^{\prime }=P_1+P_2=\left(u_1,u_2,\cdots ,u_s,v_1,v_2,\cdots ,v_t\right)$ 、 $P^{″}=P_2+P_1=\left(v_1,v_2,\cdots ,v_t,u_1,u_2,\cdots ,u_s\right)$ 。特别地，若路径是单元素路径，不妨设 $P_1=\left(u\right)$ ，则两条路径相加可表示为 $P^{\prime }=P_1+P_2=\left(u,v_1,v_2,\cdots ,v_t\right)$ 、 $P^{″}=P_2+P_1=\left(v_1,v_2,\cdots ,v_t,u\right)$ 。

定义1 区间图与区间表示一一对应，区间表示由区间构成。区间具有长度，分别记区间 $I\left(a\right)$ 的左、右端点值为 $l_{I\left(a\right)}$ 和 $r_{I\left(a\right)}$ 。给定一个图 $G=\left(V\left(G\right),E\left(G\right)\right)$ ，若存在一组区间 $I=\left\{I\left(x\right):x\in V\left(G\right)\right\}$ 满足关系：对任意顶点 $u,v\in V\left(G\right)$ ， $uv\in E\left(G\right)$ 当且仅当 $I\left(u\right)\cap I\left(v\right)\ne \varnothing$ ，则称该图G为区间图，称I为G的区间表示 [18] 。

在区间表示I上，对于任意区间 $I\left(a\right)$ 、 $I\left(b\right)$ 满足 $I\left(a\right)\cap I\left(b\right)=\varnothing$ ，记 $I\left(a\right)<I\left(b\right)$ 表示区间 $I\left(a\right)$ 先于区间 $I\left(b\right)$ 出现且。对于区间 $I\left(a\right)$ 与顶点集S满足 $I\left(a\right)\cap I\left(S\right)=\varnothing$ ，记 $I\left(a\right)<I\left(S\right)$ 表示区间

$I\left(a\right)$ 先于集合S中任意区间出现，即 $r_{I\left(a\right)}<\min \left\{l_{I\left(c\right)}|c\in S\right\}$ 。

定义2 n-顶点区间图G的右端点序列 $\pi =\left(u_1,u_2,\cdots ,u_n\right)$ 是指各顶点在区间表示I中按右端点按序列重新排序的结果，满足：对任意顶点i、j， $r_{I\left(i\right)}<r_{I\left(j\right)}$ 当且仅当 $i<j$ 。注意，若无特别说明，本文中的区间排序统一为右端点排序。如下图2所示，左图为7-顶点区间图，右图为对顶点进行右端点排序后的结果，其中， $\pi =\left(v_6,v_3,v_4,v_5,v_2,v_1,v_7\right)$ 。

Figure 2. Example: an interval graph (left) and the graph sorted by right endpoint sequence (right)

图2. 示例：区间图(左)和该图按右端点序列排序后的图(右)

定义3 给定任意图G，如果集合 $S\subseteq V\left(G\right)$ 满足对任意顶点 $u\in V\left(G\right)\backslash S$ 都存在另一个顶点 $v\in S$ 使得 $uv\in E\left(G\right)$ ，那么称S是G的一个控制集。G的控制数用 $\gamma \left(G\right)=\left|S^{\prime }\right|$ 表示，其中 $S^{\prime }$ 是G所有控制集中阶数最小的集合。在控制集基础上，total-控制函数(Total Domination Function, TDF)要求由控制集诱导的图中无孤立点存在，其控制数用 ${\gamma }_t\left(G\right)$ 表示；罗马控制函数(Roman Domination Function, RDF)是函数 $f:V\left(G\right)\to \left\{0,1,2\right\}$ ，满足：对G中任意函数值 $f\left(u\right)=0$ 的顶点u，至少存在一个邻居v使得函数值 $f\left(v\right)=2$ 。罗马控制函数也可表示为 $f=f\left(V_0,V_1,V_2\right)$ ，其中 $V_i=\left\{a|f\left(a\right)=i且a\in V\left(G\right)\right\}$ 。该图G中的罗马控制数表示为罗马控制函数的权值最小值，符号记作 ${\gamma }_R\left(G\right)$ 。

定义4 给定图G，total-罗马控制函数(Total Roman Domination Function, TRDF)是函数 $f:V\left(G\right)\to \left\{0,1,2\right\}$ ，满足条件：(1) 对G中任意函数值 $f\left(u\right)=0$ 的顶点u，至少存在一个邻居v使得函数值 $f\left(v\right)=2$ ；(2) 由控制集 $\{k|f\left(k\right)\ge 1$ 且 $k\in V\left(G\right)\}$ 诱导的子图没有孤立点存在。total-罗马控制数表示为 ${\gamma }_{tR}\left(G\right)$ ，称 $total-\left(V_1,V_2\right)$ 为图G的total-罗马对，简写为 $t-\left(V_1,V_2\right)$ 形式 [4] 。如下图3所示，在7阶区间图G中，存在total-罗马控制函数 $f:V(G)\to \{0,1,2\}$ ，此时控制数 ${\gamma }_{tR}(G)=5$ ，控制集 $\left\{u_3,u_4,u_6\right\}$ 中无孤立点存在，total-罗马对表现为 $t-\left(\left\{u_4\right\},\left\{u_3,u_6\right\}\right)$ 。

Figure 3. An interval graph G with a total-Roman Domination Function

图3. 区间图G及其total-罗马控制函数

3. 基于Total-罗马对的定理研究

定义5 已知 $I=\left\{I\left(x\right):x\in V\left(G\right)\right\}$ 是区间图的区间表示，对任意 $a,b\in V_2$ ，记 $l_{I\left(b\right)}<l_{I\left(a\right)}<r_{I\left(a\right)}<r_{I\left(b\right)}$ 表示区间 $I\left(a\right)$ 完全包含于 $I\left(b\right)$ ，写作 $I\left(a\right)\subseteq I\left(b\right)$ ，也称 $I\left(b\right)$ 完全包含 $I\left(a\right)$ [18] 。

定理1 若 $t-\left(V_1,V_2\right)$ 是区间图G的total-罗马对，那么 $I\left(V_2\right)$ 中的区间不能完全包含于 $I\left(V_2\right)$ 中的另一个区间，即由 $V_2$ 诱导的子图是严格区间图。

证明 反证法，设存在两个顶点 $a,b\in V_2$ 使得区间 $I\left(a\right)$ 完全包含于 $I\left(b\right)$ 。结合区间图按右端点序列进行排序可知 $a<b$ ，因此 $N\left[a\right]\subseteq N\left[b\right]$ 成立，故 $t-\left(V_1,V_2-a\right)$ 也是区间图G的一个total-罗马对，与 $t-\left(V_1,V_2\right)$ 是G的total-罗马对矛盾。因此， $I\left(V_2\right)$ 中的区间不能被完全包含于另外一个区间中。

定理2 若 $t-\left(V_1,V_2\right)$ 是n阶区间图G的total-罗马对，那么 $G[V_2]$ 中不会包含 $n^{\prime }\left(n^{\prime }\ge 3\right)$ 阶团。

证明 反证法。当 $n^{\prime }=3$ 时，设 $S=\left\{a,b,c\right\}$ 是一个3阶团。由定理1可知， $I\left(V_2\right)$ 中的区间不存在包含与被包含的关系，故设 $I\left(S\right)$ 中3个区间的端点值在数轴上满足 $l_{I\left(b\right)}<l_{I\left(a\right)}<l_{I\left(c\right)}<r_{I\left(c\right)}<r_{I\left(b\right)}<r_{I\left(a\right)}$ ，因此 $N\left[b\right]\subseteq (N\left[a\right]\cup N\left[c\right])$ ，这表明区间 $I\left(b\right)$ 能控制的区间(包含 $I\left(b\right)$ 在内)都可被区间 $I\left(a\right)$ 与 $I\left(c\right)$ 控制，即 $t-\left(V_1,V_2-b\right)$ 也是该区间图G的一个total-罗马对，与已知条件矛盾，故 $G[V_2]$ 中不含3阶团。

同理，当 $n^{\prime }\ge 4$ 时，设 $S^{\prime }=\left\{u_1,u_2,\cdots ,u_{n^{\prime }}\right\}$ 是 $n^{\prime }$ 阶团。由定理1可设个顶点对应的区间端点值满足关系 $l_{I\left(u_1\right)}<l_{I\left(u_2\right)}<\cdots <l_{I\left(u_{n^{\prime }}\right)}<r_{I\left(u_{n^{\prime }}\right)}<\cdots <r_{I\left(u_2\right)}<r_{I\left(u_1\right)}$ 。使用数学归纳法进行演算，可得到关系 $\left(N\left[u_2\right]\cup N\left[u_3\right]\cup \cdots \cup N\left[u_{n^{\prime }-1}\right]\right)\subseteq \left(N\left[u_1\right]\cup N\left[u_{n^{\prime }}\right]\right)$ ，这表明区间 $I\left(u_1\right)$ 与 $I\left(u_{n^{\prime }}\right)$ 能控制 $S^{\prime }$ 中其余区间控制的所有区间(包含这些区间在内)，即 $t-\left(V_1,V_2-\left\{u_2,u_3,\cdots ,u_{n^{\prime }-1}\right\}\right)$ 也是该区间图G的一个total-罗马对，与已知条件矛盾，故中不含阶团。

综上， $V_2$ 中不含 $n^{\prime }\left(n^{\prime }\ge 4\right)$ 阶团。

定理3 如果 $t-\left(V_1,V_2\right)$ 是n阶区间图G的total-罗马对，那么由 $V_2$ 诱导的各连通分量表现为路径，且每条路径阶数大于等于2。

证明 由于区间图G没有孤立点，。由定理1可知，由 $V_2$ 诱导的每个连通分量都是一个严格区间图，因此，这些严格区间图不含爪形图 $K_{1,3}$ 。结合定理4.2可知，由 $V_2$ 诱导的各连通分量表现为路径。若存在一条路径的阶数为1，那么这条路径只包含1个顶点，与total-罗马控制关于控制集的定义矛盾，故定理3成立。

另，若这些严格区间图是弦图(弦图中长度超过3的每个圈中都包含一条弦)，那么图中一定包含的最小圈为 $C_3$ ，因 $C_3$ 是3阶团，与定理2矛盾，故这些严格区间图不含弦图。

4. 区间图total-罗马控制数

4.1. 区间图中关于团的total-罗马控制数

定理4 任意n阶区间图G按右端点序列排序后满足以下：

若G为团且 $n\left(n\ge 3\right)$ ，那么 ${\gamma }_{tR}\left(G\right)=3$ 。

若 $G\backslash u_n$ 为团且 $n\left(n\ge 4\right)$ ，那么 ${\gamma }_{tR}\left(G\right)=3$ 。

若G为 $n\left(n\ge 3\right)$ 阶团，任意添加区间 $I\left(u_a\right)$ 后， ${\gamma }_{tR}\left(G\right)=3$ 。

证明 (1) 设区间右端点序列为 $\pi =\left(u_1,u_2,\cdots ,u_{n-1},u_n\right)$ 。若G为团，那么任意两个区间之间都存在相邻关系，即对任意区间 $I\left(u_k\right)$ 总存在另一个区间 $I\left(u_{k^{\prime }}\right)$ 使得 $I\left(u_k\right)\subseteq I\left(u_{k^{\prime }}\right)$ ，其中 $k\in \left[n-1\right]$ 。因此，上述所有区间均满足 $I\left(u_k\right)\subseteq I\left(u_n\right)$ 。同理可知，G的区间相互包含，不妨设存在 $t-\left(\left\{u_{n-1}\right\},\left\{u_n\right\}\right)$ 是图G的一个total-罗马对，因此 ${\gamma }_{tR}\left(G\right)=3$ 。

(2) 若 $G\backslash u_n$ 为团，结合(1)中可知在3阶团 $G\backslash u_n$ 中，对任意 $k^{″}\in \left[n-2\right]$ 知区间 $I\left(u_{k^{″}}\right)$ 都满足 $I\left(u_{k^{″}}\right)\subseteq I\left(u_{n-1}\right)$ ，设 $t-\left(\left\{u_{n-2}\right\},\left\{u_{n-1}\right\}\right)$ 是图 $G\backslash u_n$ 的一个total-罗马对。

图G无孤立点，故一定存在顶点 $u_t$ 使得 $u_t{u}_n\in E\left(G\right)$ ，要么 $u_t=u_{n-1}$ ，顶点 $u_n$ 可被顶点 $u_t$ 直接控制，要么 $u_t{u}_{n-1}\in E\left(G\right)$ ，故 $u_t{u}_{n-1}\in E\left(G\right)$ ，顶点 $u_n$ 也可被顶点 $u_t$ 控制。因此， $t-\left(\left\{u_{n-2}\right\},\left\{u_{n-1}\right\}\right)$ 不仅是图 $G\backslash u_n$ 的一个total-罗马对，同时也是图G的一个total-罗马对， ${\gamma }_{tR}\left(G\right)=3$ 。

(3) 已知G为 $n\left(n\ge 3\right)$ 阶团，若 $r_{I\left(n\right)}<r_{I\left(a\right)}$ ，添加的区间 $I\left(u_a\right)$ 右端点值最大，可能出现的情况共有n种，即 $u_k{u}_a\in E\left(G\right)$ ，其中 $k=1,2,\cdots ,n$ 。当 $k=1$ 时， $I\left(u_a\right)$ 与 $I\left(u_1\right)$ 相交，此时 $G\cup u_a$ 为 $n+1$ 阶团，由前述定理4中(2)可知， ${\gamma }_{tR}\left(G\right)=3$ ，此时的total-罗马对是 $t-\left(\left\{u_{n-1}\right\},\left\{u_n\right\}\right)$ 。为更好将新添加区间 $I\left(u_a\right)$ 纳入考虑，根据题意可知 $t-\left(\left\{u_a\right\},\left\{u_n\right\}\right)$ 也是满足情况的total-罗马对。当 $k\ge 2$ 时，考虑 $I\left(u_a\right)$ 与其他区间相交。因G为 $n\left(n\ge 3\right)$ 阶团，故将 $I\left(u_a\right)$ 赋值为2后，可控制G内其他所有区间，因此 $G\backslash u_n$ 中区间赋值为0，另将 $I\left(u_a\right)$ 赋值为1，故存在 $t-\left(\left\{u_a\right\},\left\{u_n\right\}\right)$ 是图 $G\cup u_a$ 的一个total-罗马对，此时， ${\gamma }_{tR}\left(G\right)=3$ 。综上，无论新添加区间 $I\left(u_a\right)$ 所处何种位置，都存在 $t-\left(\left\{u_a\right\},\left\{u_n\right\}\right)$ 是图 $G\cup u_a$ 的一个total-罗马对，因此total-罗马控制数 ${\gamma }_{tR}\left(G\right)=3$ 。

定理5 若区间图G中两个不相交的团G₁、G₂分别与G中区间 $I\left(u_a\right)$ 相交，那么 ${\gamma }_{tR}\left(G_1\cup u_a\cup G_2\right)\le 5$ 。

证明 设区间图G按右端点序列排序，s阶团G₁、t阶团G₂区间不相交，分别对应区间表示 $I_1$ 、 $I_2$ ，存在一个区间 $I\left(u_a\right)$ 分别与两个团相交，设 $u_{k^{\prime }}\in N\left(u_a\right)\cap V\left(G_1\right)$ 、 $u_{k^{″}}\in N\left(u_a\right)\cap V\left(G_2\right)$ 。添加新区间 $I\left(u_{a^{\prime }}\right)\subseteq I\left(u_a\right)$ 且与 $I\left(u_a\right)$ 具有相同相交关系。根据定理4，对于图 $G_1\cup u_a$ ，存在 $t-\left(\left\{u_a\right\},\left\{u_{k^{\prime }}\right\}\right)$ 是一个total-罗马对。同理，对于图 $u_a\cup G_2$ ，存在 $t-\left(\left\{u_{a^{\prime }}\right\},\left\{u_{k^{″}}\right\}\right)$ 是 $u_a\cup G_2$ 的一个total-罗马对，因此，total-罗马控制数满足关系 ${\gamma }_{tR}\left(G_1\cup u_a\cup u_{a^{\prime }}\cup G_2\right)\le 3+3=6$ 。由于 $I\left(u_{a^{\prime }}\right)$ 与 $I\left(u_a\right)$ 具有相同的控制性，因此删去 $I\left(u_{a^{\prime }}\right)$ 后， $I\left(u_a\right)$ 的存在仍能保持图中的控制性，故 ${\gamma }_{tR}\left(G_1\cup u_a\cup G_2\right)\le 5$ ，并且在 ${\gamma }_{tR}\left(G_1\cup u_a\cup G_2\right)=5$ 时，存在 $t-\left(\left\{u_a\right\},\left\{u_{k^{\prime }},u_{k^{″}}\right\}\right)$ 是图 $G_1\cup u_a\cup G_2$ 的一个total-罗马对。

如下图4所示，10阶区间图G按右端点序列排序，G₁、G₂分别是4阶、5阶团且区间不相交，其中 $V\left(G_1\right)=\left\{u_1,u_2,u_3,u_4\right\}$ 、 $V\left(G_2\right)=\left\{u_6,u_7,u_8,u_9,u_{10}\right\}$ 、 $u_a=u_5$ ，根据上述定理，取 $u_5$ 赋值为1，任取顶点 $u_{k^{\prime }}\in N\left(u_5\right)\cap V\left(G_1\right)=\left\{u_3,u_4\right\}$ 与顶点 $u_{k^{″}}\in N\left(u_5\right)\cap V\left(G_2\right)=\left\{u_6,u_7,u_8,u_9\right\}$ 赋值为2，此时，total-罗马控制数满足关系 ${\gamma }_{tR}\left(G_1\cup u_a\cup G_2\right)={\gamma }_{tR}\left(G\right)=5$ 。

Figure 4. Example: an interval graph with 10 intervals G

图4. 示例：10阶区间图G

4.2. 区间图中关于团和路径的Total-罗马控制数

引理1 n阶图G是圈或路径 $\iff$ $${\gamma }_{tR}\left(G\right)=n$$ [17] 。

设f为对应的total-罗马控制函数，顶点集 $V_i=\left\{u_x|f\left(x\right)=i\right\}$ ，通过引理1可以得到 $\left|V_0\right|=\left|V_2\right|$ 。在后文引用引理1时，不妨设 $\left|V_0\right|=\left|V_2\right|=0$ ，即图G中的顶点全部赋值为1。

定理6 若区间图G中s阶团H与G中t阶路径P的端点相交，那么 ${\gamma }_{tR}\left(H\cup P\right)\le 2+t$ ，其中正整数 $s\ge 3$ 、 $t\ge 1$ 。

证明由已知设区间图G的区间表示为I、顶点集 $V\left(H\right)=\left\{u_1,u_2,\cdots ,u_s\right\}$ 、 $V\left(P\right)=\left\{v_1,v_2,\cdots ,v_t\right\}$ 。若团H中的区间只与路径P的一个端点区间相交，那么易知这个端点为 $v_1$ 。添加新区间 $I\left({v^{\prime }}_1\right)\subseteq I\left(v_1\right)$ 且与 $I\left(v_1\right)$ 具有相同的相交关系。对于图 $H\cup {v^{\prime }}_1$ ，由定理4可知存在 $u_k\in N\left({v^{\prime }}_1\right)\cap V\left(H\right)$ 使得 $t-\left(\left\{{v^{\prime }}_1\right\},\left\{u_k\right\}\right)$ 是图 $H\cup {v^{\prime }}_1$ 的一个total-罗马对，此时 ${\gamma }_{tR}\left(H\cup {v^{\prime }}_1\right)=3$ 。对于路径P，由引理1可知 ${\gamma }_{tR}\left(P\right)=t$ 。结合定理5证明中的思想易知 ${\gamma }_{tR}\left(H\cup P\right)\le 3+t-1$ ，故 ${\gamma }_{tR}\left(H\cup P\right)\le 2+t$ ，并且在 ${\gamma }_{tR}\left(H\cup P\right)=2+t$ 时，存在 $t-\left(V\left(P\right),\left\{u_k\right\}\right)$ 是图 $H\cup P$ 的一个total-罗马对。

若H中的区间与P的包含端点区间 $I\left(v_1\right)$ 在内的多个区间相交，那么存在正整数 $k\left(2\le k\le t\right)$ 使得 $r_{I\left(u_s\right)}>l_{I\left(v_k\right)}$ ，即区间 $I\left(u_s\right)$ 的右端点值大于路径P中前k个区间的左端点值，因此将区间 $I\left(u_s\right)$ 赋值为2后，路径P中存在k个区间被 $I\left(u_s\right)$ 控制，为了保证图 $H\cup P$ 的total性质，只能将P中 $k-1$ 个区间赋值为0，故图 $H\cup P$ 的total-罗马控制数 ${\gamma }_{tR}\left(H\cup P\right)\le 2+t-\left(k-1\right)=t-k+3$ 。特别地，这种控制函数的寻找方法同样适用于团H中的区间只与路径P的一个端点区间相交的情况。

如下图5所示，区间图G阶数为8， $V\left(H\right)=\left\{u_1,u_2,u_3,u_4\right\}$ 、 $V\left(P\right)=\left\{u_5,u_6,u_7,u_8\right\}$ 、 $N\left(u_5\right)=\left\{u_2,u_3,u_4\right\}$ 、 $t=4$ 、 $k=2$ ， ${\gamma }_{tR}\left(H\cup P\right)\le 4-2+3=5$ ，取等时，将H中右端点值最大的区间赋值为2、将路径P中第k个及之后的区间赋值为1，所得控制集即为该图G的total-罗马控制集。

Figure 5. Example: an interval graph with 8 intervals

图5. 示例：8阶区间图G

定理7 区间图G中两个团G₁、G₂相交，团的并图满足 ${\gamma }_{tR}\left(G_1\cup G_2\right)\le 4$ 。

证明 设区间图G的区间表示为I。G有G₁、G₂两个满足区间相交关系的团，分别对应区间表示I₁、I₂，团内按右端点序列排序，故对任意正整数 $s,t\ge 3$ ，设 $V\left(G_1\right)=\left\{u_1,u_2,\cdots ,u_s\right\}$ 、 $V\left(G_2\right)=\left\{v_1,v_2,\cdots ,v_t\right\}$ 。易知 $I\left(u_s\right)$ 是I₁中右端点值最大的区间，且可控制I₁中其他所有区间。由于两个团中区间存在相交关系，不妨设 $I\left(u_s\right)\cap I\left(v\right)\ne \varnothing$ ，即 $u_{s}v\in E\left(G\right)$ ，其中 $v\in V\left(G_2\right)$ 。

若 $l_{I\left(v\right)}\le r_{I\left(u_1\right)}$ ，即 $I\left(u_1\right)\cap I\left(v\right)\ne \varnothing$ ，故区间 $I\left(v\right)$ 与I₁中的每个区间都相交， $I\left(v\right)$ 可控制I₁中所有区间。由定理4可知G₂中存在 $t-\left(V_1,V_2\right)$ 使得 ${\gamma }_{tR}\left(G_2\right)=3$ ，不妨设 $V_1=\left\{v^{\prime }\right\}$ ， $V_2=\left\{v\right\}$ ，其中 $v^{\prime }v\in E\left(G_2\right)$ 。那么 $t-\left(\left\{v^{\prime }\right\},\left\{v\right\}\right)$ 也即是图 $G_1\cup G_2$ 的total-罗马对，此时 ${\gamma }_{tR}\left(G_1\cup G_2\right)=3$ 。如下图6左所示，3-团与4-团对应的区间表示I₁、I₂已用不同颜色进行标注。同理，若 $r_{I\left(v_t\right)}\le r_{I\left(u_s\right)}$ ，即区间 $I\left(u_s\right)$ 与I₂中的每个区间都相交，那么存在 $t-\left(\left\{u_{s-1}\right\},\left\{u_s\right\}\right)$ 使得 ${\gamma }_{tR}\left(G_1\cup G_2\right)=3$ 。如下图6右所示，在保证区间相交关系不变的情况下，可适当伸缩区间长度。

在其他情况下，易知 $I\left(u_s\right)$ 、 $I\left(v\right)$ 分别可以控制I₁、I₂中其他所有区间，由于 $u_{s}v\in E\left(G\right)$ ，故存在 $t-\left(\varnothing ,\left\{u_s,v\right\}\right)$ 是图 $G_1\cup G_2$ 的一个total-罗马对，此时total-罗马控制数 ${\gamma }_{tR}\left(G_1\cup G_2\right)=4$ 。

特别地，若 $G_1\cup G_2$ 中任意两个区间都相交，那么 $G_1\cup G_2$ 是一个 $s+t$ 阶团，故 ${\gamma }_{tR}\left(G_1\cup G_2\right)=3$ 。

综上，定理得证。结合定理7与定理5还可推广到满足区间相交的k个团，即若区间图G的k个团依次满足区间相交，那么图G₁、G₂的并的total-罗马控制数 ${\gamma }_{tR}\left(G\right)\le 2k$ 。

5. 结论

基于区间图，本文首先介绍了total-罗马对，主要研究了团和路径中的total-罗马控制函数性质以及团与团的并、团与路径的并等结合问题中的total-罗马控制数，在证明过程中多用反证法和数学归纳法，以示例辅助理解，在3阶及以上区间图中证明了以下几个主要结论：

Figure 6. Example: two interval representations I₁、I₂ in interval graph G

图6. 示例：区间图G中两个区间表示I₁、I₂

1) 若 $t-\left(V_1,V_2\right)$ 是n阶区间图G的total-罗马对，那么 $V_2$ 中不会包含阶团；

2) 任意n阶团的total-罗马控制数为3；

3) 任意n阶团添加任意顶点后的total-罗马控制数为3；

4) 相交团的并的total-罗马控制数不超过4；

在后续研究中，还可探讨以团和路径为基础的区间图的total-罗马控制函数性质、多个团及多条路径的并的total-罗马控制数等问题。

基金项目

重庆市研究生科研创新项目(CYS23687：罗马控制及变形问题研究)。

参考文献