特殊图类的符号罗马控制数

The Signed Roman Domination Number of a Special Graph

摘要: 设图G=(V,E)为一个简单无向图，若S⊆V，则记f(S)=∑_v∈sf(v)。若实值函数满足以下两个条件：(i) 对于任意的顶点v∈V，均有f[v]≥1成立；(ii) 如果对任意的顶点v∈V，若f(v)=−1，则存在一个与v相邻的顶点u∈V满足f(u)=2，则称该函数为图G的符号罗马控制函数。图G的符号罗马控制数定义为γ_sR(G)=min{f(V)|f为图G的一个符号罗马控制函数}。本文利用构造法及穷标法主要得到了特殊图类2⋅C_n的符号罗马控制数的精确值。

Abstract: Let G=(V,E) be a simple undirected graph and denotes f(S)=∑_v∈sf(v) for S⊆V. A signed Roman domination function  satisfying the conditions that (i) f[v]≥1 for any v∈V, and (ii) every vertex v for which f(v)=−1 is adjacent to a vertex u for which is f(u)=2. The signed Roman domination number of G is γ_sR(G)=min{f(V)|f is a signed Roman function domination f of G}. In this paper, we determine exact values of the signed Roman domination number of a special graph 2⋅C_n by constructive method and exhaustive method.

1. 引言

本文所涉及到的图均为无向简单图，且文中没有说明的术语和符号见 [1]。

设 $G=\left(V,E\right)$ 是一个简单图，用 $V=V\left(G\right)$ 和 $E=E\left(G\right)$ 表示顶点集和边集。对 $u\in V\left(G\right)$，记 $N_G\left(u\right)$ 和 $N_G\left[u\right]=N_G\left(u\right)\cup \left\{u\right\}$ 为u点在G中的邻域和闭邻域，用 $d_G\left(u\right)=\left|N_G\left(u\right)\right|$ 表示u点在G中的度，而用 $\delta =\delta \left(G\right)$ 和 $\Delta =\Delta \left(G\right)$ 分别表示图G的最小度和最大度。把 $N_G\left[u\right]=N_G\left(u\right)\cup \left\{u\right\}$， $N_G\left[u\right]$， $\Delta \left(G\right)$， $\delta \left(G\right)$ 分别简单记为 $N\left(u\right)$， $N\left[u\right]$， $\Delta$， $\delta$。用 $C_n$ 表示n阶圈图。

近几十年来，国内外很多学者越来越投入研究图的控制理论中的问题，如今其研究内容越来越丰富。第一次提出的符号控制数概念是在1995年 [2]，通过几十年的发展，到目前为止已经繁衍出了各种形式的符号控制 [3] - [8]。符号罗马控制数的研究主要集中在研究其上下界 [9] 以及对特殊图的研究。Zhao [10] 等人得到了特殊图完全二部图、轮图的符号(全)罗马控制数。尹凯 [11] 等人把完全二部图的符号罗马控制数的结果推广到了完全多部图上。本文中主要计算出了图 $\text{2}\cdot C_n$ 的符号罗马控制数的精确值。

对于图 $G=\left(V,E\right)$，定义一个函数 $f:V\mapsto R$ 和G的一个子集 $S\subseteq V$，记 $f\left(S\right)={\displaystyle {\sum }_{v\in \in S}f\left(v\right)}$。下文中，为简单起见，记 $V_i$ 表示所有标号为i的顶点集合，其中 $i=-1,+1,+2$。对于 $x\in V$，把 $f\left(N\left[x\right]\right)$ 简单记为 $f\left[x\right]$。

2. 基本概念

定义1 [9] 设图 $G=\left(V,E\right)$ 为一个图，若 $S\subseteq V$，则记 $f\left(S\right)={\displaystyle {\sum }_{v\in \in S}f\left(v\right)}$。若 $f:V\mapsto \left\{-1,1,2\right\}$ 满足：(i) 对于任意的顶点 $v\in V$，均有 $f\left[v\right]\ge 1$ 成立；(ii) 如果对任意的顶点 $v\in V$，若 $f\left(v\right)=-1$，则存在一个与v相邻的顶点 $u\in V$ 满足 $f\left(u\right)=2$，则称该函数为图G的符号罗马控制函数。图G的符号罗马控制数定义为 ${\gamma }_{sR}\left(G\right)=\min \left\{f\left(V\right)|f为图G的一个符号罗马控制函数\right\}$。若符号罗马控制函数f满足 ${\gamma }_{sR}\left(G\right)={\displaystyle {\sum }_{v\in V}f\left(v\right)}$，则称函数f为图G的 ${\gamma }_{sR}\left(G\right)$ -函数。

定义2 图 $G=2\cdot C_n\left(n\ge 3\right)$ 表示恰有一个公共点的两个圈的拷贝。

引理1 [9] 对 $n\ge 3$ 时，有 ${\gamma }_{sR}\left(C_n\right)=\lceil \frac{2n}{3}\rceil$。

从引理1容易看出下面的注释。

注释：对于圈 $C_n\left(n=3k+i,i=0,1,2,k\ge 1\right)$， ${\gamma }_{sR}\left(C_n\right)$ 达到最小仅当 $C_n$ 上某连续3k个顶点中每3个点标号之和至少为2 (事实上，恰好为2)且剩下点标号至少为1 (如果有的话)。

3. 主要结果

定理 设 $G=2\cdot C_n\left(n\ge 3\right)$，则

${\gamma }_{sR}\left(G\right)=\{\begin{array}{l}2\lceil \frac{2n}{3}\rceil -3,当n\equiv 0,1\left(mod3\right)且n\ne 3,4时\hfill \\ 2\lceil \frac{2n}{3}\rceil -4,当n\equiv \text{2}\left(mod3\right)且n\ne \text{5}时\hfill \\ \text{2,}当n=3时\hfill \\ n,当n=4,5时\hfill \end{array}$

证明：设 $G=\left(V,E\right)$， $G=C_n^{\left(1\right)}\cup C_n^{\left(2\right)}$，其中

$C_n^{\left(j\right)}=v_0{v}_1^{\left(j\right)}{v}_2^{\left(j\right)}\cdots v_{n-1}^{\left(j\right)},j=1,2$。

$V\left(G\right)=\left\{v_0,v_i^{\left(j\right)}|i=1,2,\cdots ,n-1,j=1,2\right\}$。

$E\left(G\right)=\left\{v_0{v}_1^j,v_i^{\left(j\right)}{v}_{\left(i+1\right)\left(\mathrm{mod}n\right)}^{\left(j\right)}|i=1,\cdots ,n-1,j=1,2\right\}$。

设f是图G的一个最小符号罗马控制函数，则 ${\gamma }_{sR}\left(G\right)=f\left(V\right)$。不难看出，当 $n=3$ 时， ${\gamma }_{sR}\left(G\right)=2$ ；当 $n=4,5$ 时， ${\gamma }_{sR}\left(G\right)=n$。下面只考虑 $n\ge 6$ 时的情况。

情况1 当 $n=3k$ 且 $n\ne 3$ 时，由注释以及定义1，有

$\begin{array}{l}{\gamma }_{sR}\left(G\right)=f\left(V\right)={\displaystyle \underset{i=1}{\overset{k-1}{\sum }}f\left[v_{3i-1}^{\left(1\right)}\right]}+f\left(v_{3k-2}^{\left(1\right)}\right)+f\left(v_{3k-1}^{\left(1\right)}\right)+{\displaystyle \underset{i=0}{\overset{k-2}{\sum }}f\left[v_{3i+1}^{\left(2\right)}\right]}+f\left[v_{3k-2}^{\left(2\right)}\right]\\ \ge 2\left(k-1\right)+0+2\left(k-1\right)+1=2\lceil \frac{2n}{3}\rceil -3\end{array}$

另一方面，通过给出一个符号罗马控制函数 $g_1$ 来证明上界。令

$g_1\left(v_0\right)=+2$， $g_1\left(v_i^{\left(1\right)}\right)=\{\begin{array}{l}-1,当i\equiv 2\left(\mathrm{mod}3\right),1\le i\le n-1\\ +2,当i\equiv 0\left(\mathrm{mod}3\right),3<i\le n-1或i=1\\ +1,其他\end{array}$

$g_1\left(v_i^{\left(2\right)}\right)=\{\begin{array}{l}-1,当i\equiv \text{1}\left(\mathrm{mod}3\right),1\le i<n-2或i=n-1\\ +2,当i\equiv \text{2}\left(\mathrm{mod}3\right),3<i<n-1\\ +1,其他\end{array}$

容易验证，对于任意顶点 $v\in V$，有 $g_1\left[v\right]\ge 1$。从而图G中有

$\left|V_2\right|=2\lceil \frac{n}{3}\rceil -2$， $\left|V_1\right|=2\lceil \frac{2n}{3}\rceil -\left(2\lceil \frac{n}{3}\rceil -1\right)$， $\left|V_{-1}\right|=2\lceil \frac{n}{3}\rceil$，

故，有

${\gamma }_{sR}\left(G\right)\le g_1\left(V\right)=2\left|V_2\right|+\left|V_1\right|-\left|V_{-1}\right|=2\lceil \frac{2n}{3}\rceil -3$。

综上所述，有

${\gamma }_{sR}\left(G\right)=2\lceil \frac{2n}{3}\rceil -3$。

情况2 当 $n=3k+1$ 且 $n\ne 4$ 时

情况2.1 当 $f\left(v_0\right)=-1$ 时， $f\left(v_1^{\left(1\right)}\right),f\left(v_1^{\left(2\right)}\right),f\left(v_{n-1}^{\left(1\right)}\right),f\left(v_{n-1}^{\left(2\right)}\right)$ 中至少有一个标号为+2，剩余的只能标+1 (若有一个标−1，不妨设 $f\left(v_1^{\left(1\right)}\right)=-1$，则 $f\left[v_1^{\left(1\right)}\right]\le 0$，与定义1矛盾)，并且有 $f\left(v_2^{\left(2\right)}\right),f\left(v_{n-2}^{\left(1\right)}\right),f\left(v_{n-2}^{\left(2\right)}\right)\ne -1$。故，有 $f\left[v_0\right]\ge 4$。由注释以及定义1，有

$\begin{array}{l}{\gamma }_{sR}\left(G\right)=f\left(V\right)={\displaystyle \underset{i=1}{\overset{k-1}{\sum }}f\left[v_{3i}^{\left(1\right)}\right]}+f\left(v_{3k-1}^{\left(1\right)}\right)+f\left[v_0\right]+{\displaystyle \underset{i=1}{\overset{k-1}{\sum }}f\left[v_{3i+1}^{\left(2\right)}\right]}+f\left(v_2^{\left(2\right)}\right)\\ \ge 2\left(k-1\right)+1+4+2\left(k-1\right)+1=2\lceil \frac{2n}{3}\rceil \end{array}$

情况2.2当 $f\left(v_0\right)=+1$ 时，由注释以及定义1，有

$\begin{array}{l}{\gamma }_{sR}\left(G\right)=f\left(V\right)={\displaystyle \underset{i=1}{\overset{k}{\sum }}f\left[v_{3i-1}^{\left(1\right)}\right]}+f\left(v_0\right)+{\displaystyle \underset{i=1}{\overset{k}{\sum }}f\left[v_{3i-1}^{\left(2\right)}\right]}\\ \ge 2k+1+2k=2\lceil \frac{2n}{3}\rceil -1\end{array}$

情况2.3 当 $f\left(v_0\right)=+2$ 时，由注释以及定义1，有

$\begin{array}{l}{\gamma }_{sR}\left(G\right)=f\left(V\right)={\displaystyle \underset{i=1}{\overset{k-1}{\sum }}f\left[v_{3i-1}^{\left(1\right)}\right]}+f\left[v_{3k-1}^{\left(1\right)}\right]+f\left(v_0\right)+{\displaystyle \underset{i=2}{\overset{k-1}{\sum }}f\left[v_{3i-1}^{\left(2\right)}\right]}+f\left[v_2^{\left(2\right)}\right]+f\left[v_{3k-1}^{\left(2\right)}\right]\\ \ge 2\left(k-1\right)+1+2+2\left(k-2\right)+1+1=2\lceil \frac{2n}{3}\rceil -3\end{array}$

综上所述，有

${\gamma }_{SR}\left(G\right)\ge 2\lceil \frac{2n}{3}\rceil -3$。

另一方面，通过给出一个符号罗马控制函数 $g_2$ 来证明上界。令

$g_2\left(v_0\right)=+2$， $g_2\left(v_i^{\left(1\right)}\right)=\{\begin{array}{l}-1,当i\equiv 2\left(\mathrm{mod}3\right),1\le i<n-2或i=n-1\\ +2,当i\equiv 0\left(\mathrm{mod}3\right),3<i<n-1或i=1\\ +1,其他\end{array}$

$g_2\left(v_i^{\left(2\right)}\right)=\{\begin{array}{l}-1,当i\equiv \text{1}\left(\mathrm{mod}3\right),1\le i<n-3或i=n-1\\ +2,当i\equiv \text{2}\left(\mathrm{mod}3\right),3<i<n-3\\ +1,其他\end{array}$

容易验证，对于任意顶点 $v\in V$，有 $g_2\left[v\right]\ge 1$。从而图G中有

$\left|V_2\right|=2\lceil \frac{n}{3}\rceil -4$， $\left|V_1\right|=2\lceil \frac{2n}{3}\rceil -2\lceil \frac{n}{3}\rceil +3$， $\left|V_{-1}\right|=2\lceil \frac{n}{3}\rceil -2$，

故，有

${\gamma }_{sR}\left(G\right)\le g_2\left(V\right)=2\lceil \frac{2n}{3}\rceil -3$。

综上所述，有

${\gamma }_{sR}\left(G\right)=2\lceil \frac{2n}{3}\rceil -3$。

情况3 当 $n=3k+2$ 且 $n\ne 5$ 时，由注释，定义1以及引理1，有

$\begin{array}{l}{\gamma }_{sR}\left(G\right)=f\left(V\right)={\gamma }_{SR}\left(C_n^{\left(1\right)}\right)+{\displaystyle \underset{i=1}{\overset{k-1}{\sum }}f\left[v_{3i+2}^{\left(2\right)}\right]}+f\left[v_2^{\left(2\right)}\right]+f\left(v_{3k+1}^{\left(2\right)}\right)\\ \ge \lceil \frac{2n}{3}\rceil +2\left(k-1\right)+1-1=2\lceil \frac{2n}{3}\rceil -4\end{array}$

另一方面，通过给出一个符号罗马控制函数 $g_3$ 来证明上界。令

$g_3\left(v_0\right)=+2$， $g_3\left(v_i^{\left(1\right)}\right)=\{\begin{array}{l}-1,当i\equiv 2\left(\mathrm{mod}3\right),1\le i<n-3或i=n-1\\ +2,当i\equiv 0\left(\mathrm{mod}3\right),3<i<n-2或i=1\\ +1,其他\end{array}$

$g_3\left(v_i^{\left(2\right)}\right)=\{\begin{array}{l}-1,当i\equiv \text{1}\left(\mathrm{mod}3\right),1\le i<n\\ +2,当i\equiv \text{2}\left(\mathrm{mod}3\right),3<i<n-1\\ +1,其他\end{array}$

容易验证，对于任意顶点 $v\in V$，有 $g_3\left[v\right]\ge 1$。从而图G中有

$\left|V_2\right|=2\lceil \frac{n}{3}\rceil -3$， $\left|V_1\right|=2\lceil \frac{2n}{3}\rceil -2\lceil \frac{n}{3}\rceil +1$， $\left|V_{-1}\right|=2\lceil \frac{n}{3}\rceil -1$，

故，有

${\gamma }_{sR}\left(G\right)\le g_3\left(V\right)=2\lceil \frac{2n}{3}\rceil -4$。

综上所述，有

${\gamma }_{sR}\left(G\right)=2\lceil \frac{2n}{3}\rceil -4$。

定理证毕。

基金项目

国家自然科学基金(No. 11701257)；校级教改项目(No. 2020xjgj016，No. 2019xjjj002)；河南省高校青年骨干教师培训计划(No. 2020GGJS194，No. 2019GGJS202)；洛阳师范学院青年骨干教师培训计划(2019XJGGJS-10) (2020-JSJYYB-053)。

NOTES

^*第一作者。

^#通讯作者。