¹新疆师范大学，数学科学学院，新疆 乌鲁木齐

²新疆大学，数学与系统科学学院，新疆 乌鲁木齐

收稿日期：2021年12月4日；录用日期：2022年1月11日；发布日期：2022年1月18日

摘要

令图 $G=\left(V,E\right)$ 是简单连通图，V和E分别为图G的顶点集和边集。若函数 $f:V\to \left\{0,1,2,3\right\}$ 满足条件：i) 对任意一点 $v\in V$，若 $f\left(v\right)=0$，存在 $v_1,v_2\in N\left(v\right)$，使得 $f\left(v_1\right)=f\left(v_2\right)=2$，或存在 $\omega \in N\left(v\right)$，使得 $f\left(\omega \right)=3$ ；ii) 对任意一点 $v\in V$，若 $f\left(v\right)=1$，存在 $\omega \in N\left(v\right)$，使得 $f\left(\omega \right)\ge 2$，则称函数f为图G的双罗马控制函数。图G的双罗马控制函数的权值 $f\left(V\right)$ 是图G中各点权值之和，图G的双罗马控制数是图G双罗马控制函数的最小权值，用 ${\gamma }_{dR}\left(G\right)$ 表示。本文主要通过构造的方法证明了，对于任意的正整数a和b，都存在一类图G及其导出子图H，使得 ${\gamma }_{dR}\left(G\right)=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。这个结果表明了一个图的双罗马控制数与其导出子图的双罗马控制数之间没有关系。

关键词

双罗马控制，双罗马控制数，双罗马控制数函数

Research on the Double Roman Domination Numbers of Graph and Its Induced Subgraphs

Huiling Liu^1*, Hong Bian^1#, Haizheng Yu², Lina Wei¹

¹School of Mathematical Sciences, Xinjiang Normal University, Urumqi Xinjiang

²College of Mathematics and System Sciences, Xinjiang University, Urumqi Xinjiang

Received: Dec. 4^th, 2021; accepted: Jan. 11^th, 2022; published: Jan. 18^th, 2022

ABSTRACT

Let $G=\left(V,E\right)$ be a connected simple graph with vertex set V and edge set E. If a function $f:V\to \left\{0,1,2,3\right\}$ satisfies with the following conditions: i) for $\forall v\in V$, if $f\left(v\right)=0$, then there exist $v_1,v_2\in N\left(v\right)$ such that $f\left(v_1\right)=f\left(v_2\right)=2$ or there exist $\omega \in N\left(v\right)$ such that $f\left(\omega \right)=3$ ; ii) for $\forall v\in V$, if $f\left(v\right)=1$, then there exist $\omega \in N\left(v\right)$ such that $f\left(\omega \right)\ge 2$, the function f is called a double Roman dominating function. The weight $f\left(V\right)$ of a double Roman dominating function on G is the sum of the weights of all vertices in G, and the minimum weight of a double Roman dominating function on G is the double Roman domination number, denoted by ${\gamma }_{dR}\left(G\right)$. In this paper, for any two positive integers a and b, by using the method of constructing, we show that there exist a class of graph G and its induced subgraph H such that ${\gamma }_{dR}\left(G\right)=a$ and ${\gamma }_{dR}\left(H\right)=b$. This result shows that there is no relation between the double Roman domination numbers of a graph and its induced subgraphs.

Keywords:Double Roman Domination, Double Roman Domination Number, Double Roman Dominating Function

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

设图 $G=\left(V,E\right)$ 是一个简单无向图，V和E分别为图G的顶点集和边集。若图G满足以下情形，则称函数 $f:V\to \left\{0,1,2,3\right\}$ 为图G的双罗马控制函数，简写为DRDF。在函数f下，赋值为i的点的集合用 $V_i,i=0,1,2,3$ 表示，且满足如下两个条件：

i) 若 $v\in V_0$，则点v至少有两个邻点在 $V_2$ 中或至少有一个邻点在 $V_3$ 中；

ii) 若 $v\in V_1$，则点v至少有一个邻点在 $V_2\cup V_3$ 中。

双罗马控制函数的权 $f\left(V\right)$ 是图G中各点权值之和，即 $f\left(V\right)={\displaystyle {\sum }_{v\in V}}f\left(v\right)$，图G的双罗马控制数是图G双罗马控制函数的最小权值，用 ${\gamma }_{dR}\left(G\right)$ 表示。

罗马控制函数的研究起源于I. Stewart [1] 在1999年发表的一篇文章，这一研究是将公元四世纪的古罗马帝国所采取的安全防御措施转化成了一个数学问题，即罗马控制问题：把罗马帝国的一个地区看作我们所研究的图中的一个顶点，把连接各地区的路线看作图中对应顶点间关联的边。若一个地区有军团驻扎则该地区就是安全的，否则就是不安全的，安全地区的军团可被派遣至相邻的不安全地区，但只有一个军团的地区不能将其向外派遣，因为调出军团后，原地区将不被保护。最高统治者想用尽可能少的军团达到理想的安全防御状态。M. A. Henning [2] 等在2003年提出了一个能达到给养军团费用最节约，且仍能够防御罗马帝国的新策略，将罗马控制问题转化成数学问题，从而引入了弱罗马控制的概念，并研究了其相应的性质。在2004年，E. J. Cockayne [3] 等提出了罗马控制函数的定义，一个权值为 ${\gamma }_R\left(G\right)$ 的罗马控制函数对应着一个最优的军团驻扎方案。为了找到更安全的防御措施，王彤歌 [4] 等人在2007年把图G的罗马控制推广为图G的k-罗马控制问题，并得到了一些3-罗马控制函数的性质。2016年M. Chellali [5] 等人首次提出了罗马{2}-控制函数的概念，若图G的一个罗马{2}-控制函数f满足 $V_1\cup V_2$ 是一个独立集，则称f为图G的一个独立罗马{2}-控制函数。同一年Beeler [6] 等人提出了双罗马控制的概念，这一防御策略使罗马帝国某一地区遭受袭击时，能够得到至少两个军团的支援，起到了双倍保护的作用。2018年，V. Anu和S. A. Lakshmanan [7] 用双罗马控制数给出了双罗马控制数在Mycielskian图上的一个界，并且分析了增加一条边之后对图的双罗马控制数所产生的影响。

2. 基本概念

对于图上G的一点v，若v与图G中其余所有点相邻，则v点叫做图G的universal点，若v仅与图G中其余任意一点相邻，则v点叫做图G的悬挂点。一条有n个点的路记为 $P_n$，其顶点集为 $\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$，其中 $v_i$ 与 $v_{i+1}$ 相邻( $i=1,2,\cdots ,n-1$ )。若在上述情形下满足 $v_n$ 与 $v_1$ 相邻( $n\ge 3$ )，则称其为n长圈，用 $C_n$ 表示。若一个图的顶点集可分为两个互不相交的非空子集X和Y，使得每条边都有一个端点在X中，另一个端点在Y中，满足这种分类条件的图称为二部图；若在一个二部图中X中的每个顶点都与Y中的每个顶点相邻，这样的图称为完全二部图；若 $\left|X\right|=p$ 而 $\left|Y\right|=q$，则这样的完全二部图记为 $K_{p\mathrm{,}q}$。一个没有边的图被称为完全不连通图。仅通过删除图G上的一些顶点得到的子图H称为图G的导出子图，图G称为其导出子图H的母图。

引理1 [8] 对于 $n\ge 1$，

${\gamma }_{dR}\left(P_n\right)=(\begin{array}{l}n,若n\equiv 0\left(\mathrm{mod}3\right),\\ n+1,若n\equiv 1,2\left(\mathrm{mod}3\right).\end{array}$

引理2 [8] 对于 $n\ge 3$，

${\gamma }_{dR}\left(C_n\right)=(\begin{array}{l}n,若n\equiv 0,2,3,4\left(\mathrm{mod}6\right),\\ n+1,若n\equiv 1,5\left(\mathrm{mod}6\right).\end{array}$

引理3 [9] 在权值为 ${\gamma }_{dR}\left(G\right)$ 的双罗马控制函数中，没有点赋值为1。

在不失一般性的情况下，当确定 ${\gamma }_{dR}\left(G\right)$ 的值时，对于所考虑的双罗马控制函数可假设 $V_1=\text{Ø}$。以下是已经得出的一些结论：

1) 对于一个至少有两个点的图G，若 ${\gamma }_{dR}\left(G\right)=3$，当且仅当图G有一个universal点；

2) 若图G是一个阶为n的完全不连通图，则 ${\gamma }_{dR}\left(G\right)=2n$ ；

3) 对于完全二部图 $K_{p\mathrm{,}q}$，若 $p\mathrm{,}q\ge 3$，则 ${\gamma }_{dR}\left(G\right)=6$，对于两种特殊情况的图， ${\gamma }_{dR}\left(K_{1,q}\right)=3$ ； ${\gamma }_{dR}\left(K_{2,q}\right)=4$。

3. 主要结果

由于不存在双罗马控制数等于1的图，并且对于任意一个图G，若 ${\gamma }_{dR}\left(G\right)=2$，当且仅当G是 $K_1$。因此在下面的定理中，只考虑 ${\gamma }_{dR}\left(G\right)\ge 3$ 的情况。

定理1 对于任意两个正整数 $a\ge \mathrm{3,}b\ge 3$，存在一个图G及其导出子图H，使得 ${\gamma }_{dR}\left(G\right)=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

证明 通过构造的方法证明。根据a和b的大小关系分以下两种情形：

情形1 $b\le a$。

子情形1 $a=6k$，$b=3l$。按以下方法构造图G：令 $C_{a-3}:v_1{v}_2\cdots v_{a-3}$，令 $X=\left\{u_1,u_2\right\}$ 和 $Y=\left\{{\omega }_1,{\omega }_2\right\}$ 为完全二部图 $K_{\mathrm{2,2}}$ 的两个顶点集，在 $v_{a-3}\in C_{a-3}$ 与 $u_1\in K_{\mathrm{2,2}}$ 之间加一条边，另外再添加一个顶点x，并使其与 $K_{\mathrm{2,2}}$ 的四个顶点相邻。为了找到图G的双罗马控制函数的最小权值，可根据定理1.2为 $C_{a-3}$ 上的各点赋值，对点 $u_1\mathrm{,}{u}_2\mathrm{,}{\omega }_1\mathrm{,}{\omega }_2$ 均赋值为0，对点x赋值为3，这样即可得出 ${\gamma }_{dR}\left(G\right)=a-3+3=a$。令导出子图H为 $G-\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-b}\right\}$，则图H是由 $P_{b-3}$ 及其悬挂点 $v_{b-3}$ 与 $K_{\mathrm{2,2}}$ 中的 $u_1$ 相邻，和一点x与 $K_{\mathrm{2,2}}$ 的四个顶点相邻这几部分构成的(如图1所示)。因为 $b-3\equiv 0\left(\mathrm{mod}3\right)$，所以 ${\gamma }_{dR}\left(H\right)=b-3+3=b$。

图1. 情形1的子情形1中构造的图G与其导出子图H

子情形2 $a=6k$，$b=3l+1$。图G的构造方法与情形1中的子情形1相同。令导出子图H为 $G-\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-b+1}\mathrm{,}x\right\}$。则H是由 $P_{b-4}$ 及其悬挂点 $v_{b-4}$ 与 $K_{\mathrm{2,2}}$ 中的 $u_1$ 相邻构成的(如图2所示)。因为 $b-4\equiv 0\left(\mathrm{mod}3\right)$ 且 ${\gamma }_{dR}\left(K_{2,2}\right)=4$，所以 ${\gamma }_{dR}\left(H\right)=b-4+4=b$。

图2. 情形1的子情形2中构造的图G与其导出子图H

子情形3 $a=6k$，$b=3l+2$。令 $G=C_a$，则 ${\gamma }_{dR}\left(G\right)=a$，令 $H=P_{b-1}$，则 ${\gamma }_{dR}\left(H\right)=b-1+1=b$。

子情形4 $a=6k+1$，$b=3l$。按以下方法构造图G，令 $C_{a-4}:v_1{v}_2\cdots v_{a-4}$，令 $X=\left\{u_1,u_2\right\}$ 和 $Y=\left\{{\omega }_1,{\omega }_2\right\}$ 为完全二部图 $K_{\mathrm{2,2}}$ 的两个顶点集。在 $v_{a-4}\in C_{a-4}$ 与 $u_1\in K_{\mathrm{2,2}}$ 之间加一条边(如图3所示)。由于 $a-4\equiv 3\left(\mathrm{mod}6\right)$ 且 ${\gamma }_{dR}\left(K_{2,2}\right)=4$，可以得出 ${\gamma }_{dR}\left(G\right)=a-4+4=a$。若 $l<k$，则取路 $P_b:v_1{v}_2\cdots v_b$ 作为导出子图H，那么 ${\gamma }_{dR}\left(H\right)=b$.若 $l=2k$，那么 $b=a-1$。令路 $P_{a-2}:v_2{v}_3\cdots v_{a-4}{u}_1{\omega }_1{u}_2$ 作为导出子图H，因为 $a-2=b-1$ 且 $b-1\equiv 2\left(\mathrm{mod}3\right)$，那么 ${\gamma }_{dR}\left(H\right)=b-1+1=b$。

图3. 情形1的子情形4中构造的图G与其导出子图H

子情形5 $a=6k+1$，$b=3l+1$。图G的构造方法与情形1中的子情形4相同。令导出子图H为 $G-\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-b}\right\}$，则H是由 $P_{b-4}$ 及其悬挂点 $v_{a-4}$ 与 $K_{\mathrm{2,2}}$ 中的 $u_1$ 相邻构成的。因此 ${\gamma }_{dR}\left(H\right)=b-4+4=b$。(注意，如果 $l=2k$，那么H就是G本身。)

子情形6 $a=6k+1$，$b=3l+2$。图G的构造方法与情形1中的子情形4相同。取路 $P_{b-1}:v_1{v}_2\cdots v_{b-1}$ 作为导出子图H，则 ${\gamma }_{dR}\left(H\right)=b-1+1=b$。

子情形7 $a=6k+2$，$b=3l$。令 $G=C_a$，则 ${\gamma }_{dR}\left(G\right)=a$，令导出子图 $H=P_b$，则 ${\gamma }_{dR}\left(H\right)=b$。

子情形8 $a=6k+2$，$b=3l+1$。图G的构造方法与情形1中的子情形4相同。导出子图H的构造方法与情形1中的子情形5相同。那么 ${\gamma }_{dR}\left(G\right)=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形9 $a=6k+2$，$b=3l+2$。令 $G=C_a$，则 ${\gamma }_{dR}\left(G\right)=a$，令导出子图 $H=P_{b-1}$，则 ${\gamma }_{dR}\left(H\right)=b-1+1=b$。

子情形10 $a=6k+3$，$b=3l$。令 $G=C_a$，则 ${\gamma }_{dR}\left(G\right)=a$，令导出子图 $H=P_b$，则 ${\gamma }_{dR}\left(H\right)=b$。

子情形11 $a=6k+3$，$b=3l+1$。图G的构造方法与情形1中的子情形1相同。导出子图H的构造方法与情形1中的子情形2相同。因为 $a-3\equiv 0\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形12 $a=6k+3$，$b=3l+2$。令 $G=C_a$，则 ${\gamma }_{dR}\left(G\right)=a$，令导出子图 $H=P_{b-1}$，则 ${\gamma }_{dR}\left(H\right)=b-1+1=b$。

子情形13 $a=6k+4$，$b=3l$。令 $G=C_a$，则 ${\gamma }_{dR}\left(G\right)=a$，令导出子图 $H=P_b$，则 ${\gamma }_{dR}\left(H\right)=b$。

子情形14 $a=6k+4$，$b=3l+1$。图G的构造方法与情形1中的子情形4相同。导出子图H的构造方法与情形1中的子情形5相同。因为 $a-4\equiv 0\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-4+4=a$，${\gamma }_{dR}\left(H\right)=b$。

子情形15 $a=6k+4$，$b=3l+2$。令 $G=C_a$，则 ${\gamma }_{dR}\left(G\right)=a$，令导出子图 $H=P_{b-1}$，则 ${\gamma }_{dR}\left(H\right)=b-1+1=b$。

子情形16 $a=6k+5$，$b=3l$。按以下方法构造图G，令 $C_{a-3}:v_1{v}_2\cdots v_{a-3}$，令 $X=\left\{u\right\}$ 和 $Y=\left\{{\omega }_1,{\omega }_2,{\omega }_3\right\}$ 为完全二部图 $K_{\mathrm{1,3}}$ 的两个顶点集，在 $v_{a-3}\in C_{a-3}$ 与 $u\in K_{\mathrm{1,3}}$ 之间加一条边(如图4所示)。因为 $a-3\equiv 2\left(\mathrm{mod}6\right)$ 且 ${\gamma }_{dR}\left(K_{1,3}\right)=3$，可以得出 ${\gamma }_{dR}\left(G\right)=a-3+3=a$。取H为 $G-\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-b}\right\}$，则导出子图H是由 $P_{b-3}$ 与 $K_{\mathrm{1,3}}$ 及点 $v_{b-3}$ 与u之间连一条边这几部分构成的。因为 $b-3\equiv 0\left(\mathrm{mod}3\right)$，所以 ${\gamma }_{dR}\left(H\right)=b-3+3=b$。

子情形17 $a=6k+5$，$b=3l+1$。图G的构造方法与情形1中的子情形1相同。导出子图H的构造方法与情形1中的子情形2相同。因为 $a-3\equiv 2\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$，${\gamma }_{dR}\left(H\right)=b$。

子情形18 $a=6k+5$，$b=3l+2$。图G的构造方法与情形1中的子情形16相同。取H为 $G-\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-b+1}\right\}$，则导出子图H是由 $P_{b-4}$ 与 $K_{\mathrm{1,3}}$ 及点 $v_{b-4}$ 与u之间连一条边这几部分构成的。因为 $b-4\equiv 2\left(\mathrm{mod}3\right)$ 且 ${\gamma }_{dR}\left(K_{\mathrm{1,3}}\right)=3$，所以 ${\gamma }_{dR}\left(H\right)=b-4+1+3=b$。

图4. 情形1的子情形16中构造的图G与其导出子图H

情形2 $b>a$。

子情形1 $a=6k$，$b=3l$。取 $H=P_b:v_1{v}_2\cdots v_{a-4}{v}_{a-3}{v}_{a-2}{v}_{a-1}{v}_a{v}_{a+1}\cdots v_b$，则 ${\gamma }_{dR}\left(H\right)=b$。按以下方法构造H的母图G：加一个孤立点u，使其与点 $v_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}\cdots \mathrm{,}{v}_b$ 相邻，再加一点 $v_0$，使其与点 $v_1$ 和点 $v_{a-4}$ 相邻(如图5所示)。在图G中，对点 $v_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}\cdots \mathrm{,}{v}_b$ 赋值为0，对u赋值为3。对点 $v_0\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-3}\mathrm{,}{v}_{a-4}$ 可根据定理1.2为 $C_{a-3}$ 上的各点赋值，因此可得 ${\gamma }_{dR}\left(G\right)=a-3+3=a$。

图5. 情形2的子情形1中构造的母图G

子情形2 $a=6k+1$，$b=3l$。取 $H=P_b:v_1{v}_2\cdots v_{a-5}{v}_{a-4}{v}_{a-3}{v}_{a-2}{v}_{a-1}{v}_a\cdots v_b$，则 ${\gamma }_{dR}\left(H\right)=b$。按以下方法构造图H的母图G：加两个孤立点u和w，使这两点均与点 $v_{a-4}\mathrm{,}{v}_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}\cdots \mathrm{,}{v}_b$ 相邻，再加一点 $v_0$，使其与点 $v_1$ 和点 $v_{a-5}$ 相邻(如图6所示)。在图G中，对点 $v_{a-4}\mathrm{,}{v}_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}\cdots \mathrm{,}{v}_b$ 赋值为0，对u和w均赋值为2。对点 $v_0\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-4}\mathrm{,}{v}_{a-5}$ 可根据定理1.2为 $C_{a-4}$ 上的各点赋值，因此可得 ${\gamma }_{dR}\left(G\right)=a-4+4=a$。

图6. 情形2的子情形2中构造的图G

子情形3 $a=6k+2$，$b=3l$。对于图G和图H的构造方法分别与情形2中的子情形2相同。因为 $a-4\equiv 4\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-4+4=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形4 $a=6k+3$，$b=3l$。对于图G和图H的构造方法分别与情形2中的子情形1相同。因为 $a-3\equiv 0\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形5 $a=6k+4$，$b=3l$。对于图G和图H的构造方法分别与情形2中的子情形2相同。因为 $a-4\equiv 0\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-4+4=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形6 $a=6k+5$，$b=3l$。对于图G和图H的构造方法分别与情形2中的子情形1相同。因为 $a-3\equiv 2\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形7 $a=6k$，$b=3l+1$。按以下方法构造图H：取 $P_{b-4}:v_1{v}_2\cdots v_{b-4}$，令 $X=\left\{u_1,u_2\right\}$ 和 $Y=\left\{{\omega }_1,{\omega }_2\right\}$ 为完全二部图 $K_{\mathrm{2,2}}$ 的两个顶点集。在 $v_{b-4}\in P_{b-4}$ 与 $u_1\in K_{\mathrm{2,2}}$ 之间加一条边。由此可得 ${\gamma }_{dR}\left(H\right)=b-4+4=b$。按以下方法构造图H的母图G：加一个孤立点u，使其与点 $v_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}{v}_{a+1}\mathrm{,}\cdots \mathrm{,}{v}_{b-4}\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}{\omega }_1\mathrm{,}{\omega }_2$ 相邻，再加一点 $v_0$，使其与 $v_1$ 和点 $v_{a-4}$ 相邻(如图7所示)。在图G中，对点 $v_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}{v}_{a+1}\mathrm{,}\cdots \mathrm{,}{v}_{b-4}\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}{\omega }_1\mathrm{,}{\omega }_2$ 赋值为0，对点u赋值为3。对点 $v_0\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-3}\mathrm{,}{v}_{a-4}$ 可根据定理1.2为 $C_{a-3}$ 上的各点赋值，因为 $a-3\equiv 3\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$。

图7. 情形2的子情形7中构造的导出子图H与其母图G

子情形8 $a=6k+1$，$b=3l+1$。对于图G和图H的构造方法分别与情形2中的子情形7相同。因为 $a-3\equiv 4\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形9 $a=6k+2$，$b=3l+1$。对于图H的构造方法与情形2中的子情形7相同，则 ${\gamma }_{dR}\left(H\right)=b-4+\mathrm{4\; <mo>\; =\; </mo>}b$。按以下方法构造H的母图G：加两个孤立点u和w，并使这两点均与点 $v_{a-4}\mathrm{,}{v}_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}\cdots ,v_{b-4}\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}{\omega }_1\mathrm{,}{\omega }_2$ 相邻，再加一点 $v_0$，使其与点 $v_1$ 和点 $v_{a-5}$ 相邻(如图8所示)。在图G中，对点 $v_{a-4}\mathrm{,}{v}_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}\cdots \mathrm{,}{v}_{b-4}\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}{\omega }_1\mathrm{,}{\omega }_2$ 赋值为0，对点u和点w均赋值为2。对点 $v_0\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{a-4}\mathrm{,}{v}_{a-5}$ 可根据定理1.2为 $C_{a-4}$ 上的各点赋值，因为 $a-4\equiv 4\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-4+4=a$。

图8. 情形2的子情9中构造的图G

子情形10 $a=6k+3$，$b=3l+1$。对于图G和图H的构造方法分别与情形2中的子情形7相同。因为 $a-3\equiv 0\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形11 $a=6k+4$，$b=3l+1$。对于图G和图H的构造方法分别与情形2中的子情形9相同。因为 $a-4\equiv 0\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-4+4=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形12 $a=6k+5$，$b=3l+1$。对于图G和图H的构造方法分别与情形2中的子情形7相同。因为 $a-3\equiv 2\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形13 $a=6k$，$b=3l+2$。取 $H=P_{b-1}$，则 ${\gamma }_{dR}\left(H\right)=b-1+1=b$。对于图G的构造，除了点u与点 $v_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}{v}_{a+1}\mathrm{,}\cdots \mathrm{,}{v}_{b-1}$ 相邻外，其余方法均与情形2中的子情形1相同(如图9所示)。因此 ${\gamma }_{dR}\left(G\right)=a-3+3=a$。

图9. 情形2的子情形13中构造的图G

子情形14 $a=6k+1$，$b=3l+2$。对于图G和图H的构造方法均与情形2中的子情形13相同。因为 $a-3\equiv 2\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a-3+3=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形15 $a=6k+2$，$b=3l+2$。取 $H=P_{b-1}$，则 ${\gamma }_{dR}\left(H\right)=b-1+1=b$。对于图G的构造，除了两孤立点u和 $\omega$ 均与点 $v_{a-4}\mathrm{,}{v}_{a-3}\mathrm{,}{v}_{a-2}\mathrm{,}{v}_{a-1}\mathrm{,}{v}_a\mathrm{,}{v}_{a+1}\mathrm{,}\cdots \mathrm{,}{v}_{b-1}$ 相邻外，其余方法均与情形2中的子情形2相同(如图10所示)。因此 ${\gamma }_{dR}\left(G\right)=a-4+4=a$。

图10. 情形2的子情形15中构造的图G

子情形16 $a=6k+3$，$b=3l+2$。对于图G和图H的构造方法均与情形2中的子情形13相同。因为 $a-3\equiv 3\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形17 $a=6k+4$，$b=3l+2$。对于图G和图H的构造方法分均情形2中的子情形15相同。因为 $a-4\equiv 0\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

子情形18 $a=6k+5$，$b=3l+2$。对于图G和图H的构造方法分均情形2中的子情形13相同。因为 $a-3\equiv 2\left(\mathrm{mod}6\right)$，所以 ${\gamma }_{dR}\left(G\right)=a$ 且 ${\gamma }_{dR}\left(H\right)=b$。

4. 结论

从上述定理证明可以得出，一个图的双罗马控制数与其导出子图的双罗马控制数之间没有关系。

基金项目

国家自然科学基金项目(11761070, 61662079)；2021年新疆维吾尔自治区自然基金联合项目(2021D01C078)；2020年新疆师范大学一流专业、一流课程项目资助。

文章引用

刘慧灵,边 红,于海征,魏丽娜. 图与其导出子图的双罗马控制数的研究
Research on the Double Roman Domination Numbers of Graph and Its Induced Subgraphs[J]. 理论数学, 2022, 12(01): 71-79. https://doi.org/10.12677/PM.2022.121010

参考文献