全局意大利控制数较大的图的刻画

Characterization of Graphs with Large Global Italian Domination Numbers

摘要

研究了图的全局意大利控制问题。通过对图的结构分析，利用分类讨论法刻画了全局意大利控制数等于顶点数的所有连通图。在此基础上，进一步刻画了全局意大利控制数等于顶点数减一且直径不小于3的所有连通图。

Abstract

This paper studies the problems of global Italian domination in graphs. By analyzing the structure of graphs and using the method of categorical discussion, all connected graphs with global Italian domination number equal to the number of vertices are characterized. On this basis, all connected graphs of diameter no less than 3 with global Italian domination number equal to the number of vertices minus one are further characterized.

Graphical abstract

关键词

意大利控制 / 全局意大利控制 / 连通图

Key words

Italian domination / global Italian domination / connected graph

0 引言

近几十年来，以图的控制参数为研究对象的控制理论逐渐成为图论中一个非常活跃的研究分支。各种控制参数的研究不仅丰富和发展了图的理论，而且也在组合优化、计算机科学、计算科学及网络工程等应用领域得到了很好的发展。关于图的控制问题的研究始于20世纪60年代^［1］。控制集问题一经提出，便引起了学术界的广泛关注^［2-9］。2004年，Cockayne等^［10］受“Defend the Roman Empire” ^［11］中防御策略的启发，引入了图的罗马控制的概念。2016年，Chellali等^［12］弱化了“Defend the Roman Empire”中的防御策略，提出了图的罗马\{\mathrm{2}\}-控制的概念，并证明了确定二部图的罗马\{\mathrm{2}\}-控制数问题是NP-完全的。2017年，Henning和Klostermeyer^［13］将罗马\{\mathrm{2}\}-控制重新命名为意大利控制。Varghese和Lakshmanan^［14］得到了Mycielskian图和Sierpinski图的意大利控制数的上下界。Bommel^［15］计算了有向圈的笛卡尔乘积图的意大利控制数。Gao等^［16］确定了广义彼得森图的意大利控制数的精确值。Haynes等^［17］给出了最小度至少为2的任意图的意大利控制数的上界并且刻画了等号成立的极图。2019年，Hao等^［18］引入了图的意大利控制数的一个衍生变量，即全局意大利控制数，并且分别刻画了全局意大利控制数与意大利控制数的差为1和2的所有树。

1 预备知识

本文用G=(V(G),E(G))表示一个无向简单连通图，其中V(G)和E(G)分别表示图G的顶点集和边集。用N(v)=N_G(v)=\{u\in V(G)\left|uv\in E(G)\}\right.与N[v]=N_G[v]=N_G(v)\bigcup \{v\}分别表示图G中顶点v的开邻域与闭邻域。图G中顶点v的度d(v)=d_G(v)=\left|N_G(v)\right|\mathrm{。}阶为n的路记为P_n\mathrm{。}

图中顶点u与v的距离d(u,v)是指连接这两个顶点的最短路的长度。图G的直径\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)是指图G中任意两个顶点的最大距离。图中长度等于直径的最短路称为直径路。图G的补图\overline{G}是指满足V(\overline{G})=V(G)且uv\in E(\overline{G})当且仅当uv\notin E(G)的图。顶点数为n+\mathrm{1}的完全二部图K_{\mathrm{1},n}称为星图，其中度为n的顶点称为星图的中心。双星图S_{r,s}是指由含有r+\mathrm{1}个顶点的星图K_{\mathrm{1},r}和含有s+\mathrm{1}个顶点的星图K_{\mathrm{1},s}组成的图，且使得星图K_{\mathrm{1},r}的中心与星图K_{\mathrm{1},s}的中心相邻。

若函数f:V(G)\to \{\mathrm{0,1},\mathrm{2}\}使得对图G中所有满足f(v)=\mathrm{0}的顶点v,都有{\sum }_{u\in N(v)}f(u)\ge \mathrm{2}成立，则称f为G的意大利控制函数。称\omega (f)={\sum }_{x\in V(G)}f(x)为f的权。G的意大利控制数{\gamma }_I(G)是指G的意大利控制函数的最小权。若f不仅是图G的意大利控制函数，而且还是图\overline{G}的意大利控制函数，则称f为G的全局意大利控制函数。G的全局意大利控制数{\gamma }_{gI}(G)是指G的全局意大利控制函数的最小权。称权为{\gamma }_{gI}(G)的全局意大利控制函数为{\gamma }_{gI}(G)-函数。本文继续研究图的全局意大利控制问题，得到了如下结果：

定理1 对于任意n阶连通图G,{\gamma }_{gI}(G)=n当且仅当图G满足下列条件之一：

（1）n\le \mathrm{4}; （2）n\ge \mathrm{5}且\overline{G}的每个连通分支都是路P_{\mathrm{1}}或路P_{\mathrm{2}}\mathrm{。}

定理2 对于直径不小于3的任意n阶连通图G,{\gamma }_{gI}(G)=n-\mathrm{1}当且仅当图G满足下列条件之一： （1）G\in \{P_{\mathrm{5}},S_{\mathrm{1,2}}\}; （2）G\in \{G_{\mathrm{1}},G_{\mathrm{2}},\cdots ,G_{\mathrm{6}}\},其中图G_i(\mathrm{1}\le i\le \mathrm{6})如图1所示。

2 定理1的证明

首先假设n\le \mathrm{4}\mathrm{。}令f是一个{\gamma }_{gI}(G)-函数。如果G中每个顶点v都满足f(v)\ne \mathrm{0},则{\gamma }_{gI}(G)=\omega (f)=\sum _{v\in V(G)}f(v)\ge n;如果存在某个顶点v\in V(G)使得f(v)=\mathrm{0},则由{\gamma }_{gI}(G)-函数的定义知，\sum _{x\in N_G\left(v\right)}f(x)\ge \mathrm{2}且\sum _{x\in N_{\overline{G}}(v)}f(x)\ge \mathrm{2},于是{\gamma }_{gI}(G)=\omega (f)=f(v)+\sum _{x\in N_G(v)}f(x)+\sum _{x\in N_{\overline{G}}(v)}f(x)\ge \mathrm{4}\ge n\mathrm{。}另一方面，显然有{\gamma }_{gI}(G)\le n\mathrm{。}故{\gamma }_{gI}(G)=n\mathrm{。}

下设n\ge \mathrm{5}\mathrm{。}如果\overline{G}的每个连通分支都是路P_{\mathrm{1}}或路P_{\mathrm{2}},则不难验证函数f使得对任意顶点x\in V(G),都有f(x)=\mathrm{1}是一个{\gamma }_{gI}(G)-函数，于是{\gamma }_{gI}(G)=n\mathrm{。}因此充分性成立。为证明必要性，假设{\gamma }_{gI}(G)=n\mathrm{。}我们给出以下断言。

断言1 对于任意顶点v\in V(G),d(v)\in \{\mathrm{1},n-\mathrm{2},n-\mathrm{1}\}\mathrm{。}

断言1的证明 假设存在顶点v\in V(G)使得\mathrm{2}\le d(v)\le n-\mathrm{3}\mathrm{。}则不难验证函数f使得f(v)=\mathrm{0}且当x\in V(G)-\{v\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{1},与{\gamma }_{gI}(G)=n矛盾。断言1得证。

断言2 \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)=\mathrm{2}\mathrm{。}

断言2的证明 假设\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)\ge \mathrm{3}\mathrm{。}不失一般性，令P=v_{\mathrm{1}}{v}_{\mathrm{2}}\cdots v_{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)+\mathrm{1}}是图G的一条直径路。因为v_{\mathrm{3}},v_{\mathrm{4}}\notin N(v_{\mathrm{1}}),所以d(v_{\mathrm{1}})\le n-\mathrm{3}\mathrm{。}故由断言1知，d(v_{\mathrm{1}})=\mathrm{1}\mathrm{。}同理可得d(v_{\mathrm{4}})=\mathrm{1}\mathrm{。}因此\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)=\mathrm{3}\mathrm{。}又因为v_{\mathrm{1}},v_{\mathrm{3}}\in N(v_{\mathrm{2}})且v_{\mathrm{4}}\notin N(v_{\mathrm{2}}),所以\mathrm{2}\le d(v_{\mathrm{2}})\le n-\mathrm{2}\mathrm{。}于是由断言1知，d(v_{\mathrm{2}})=n-\mathrm{2}\mathrm{。}同理可得d(v_{\mathrm{3}})=n-\mathrm{2}\mathrm{。}又因为n\ge \mathrm{5}且d(v_{\mathrm{1}})=d(v_{\mathrm{4}})=\mathrm{1},所以对于任意顶点x\in V(G)-\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}}\},都有v_{\mathrm{2}},v_{\mathrm{3}}\in N(x)且v_{\mathrm{1}},v_{\mathrm{4}}\notin N(x),故\mathrm{2}\le d(x)\le n-\mathrm{3},与断言1矛盾。因此\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)\le \mathrm{2}\mathrm{。}又因为n\ge \mathrm{5},所以\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)=\mathrm{2}\mathrm{。}断言2得证。

断言3 \overline{G}的每个连通分支都是路P_{\mathrm{1}}或路P_{\mathrm{2}}\mathrm{。}

断言3的证明 首先假设图G中存在1度顶点v\mathrm{。}令N(v)=\{u\}\mathrm{。}则由断言2知，\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)=\mathrm{2}\mathrm{。}因此对于任意顶点x\in V(G)-\{u,v\},都有x\in N(u)-N(v)成立。于是不难看出函数f使得f(u)=f(v)=\mathrm{2}且当x\in V(G)-\{u,v\}时，f(x)=\mathrm{0}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=\mathrm{4}\le n-\mathrm{1},矛盾。因此G中不存在1度顶点。故由断言1可得，对于任意顶点x\in V(G),都有d_G(x)\in \{n-\mathrm{2},n-\mathrm{1}\},即在\overline{G}中，任意顶点的度都为0或1。因此\overline{G}的每个连通分支都是路P_{\mathrm{1}}或路P_{\mathrm{2}}\mathrm{。}断言3得证。

由断言3知，当{\gamma }_{gI}(G)=n时，如果n\ge \mathrm{5},则图\overline{G}的每个连通分支都是路P_{\mathrm{1}}或路P_{\mathrm{2}}\mathrm{。}因此必要性成立。

3 定理2的证明

为证明定理2，我们首先给出以下两个引理。

引理1 对于直径不小于4的任意n阶连通图G,{\gamma }_{gI}(G)=n-\mathrm{1}当且仅当G=P_{\mathrm{5}}\mathrm{。}

证明 因为\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)\ge \mathrm{4},所以n\ge \mathrm{5}\mathrm{。}若n=\mathrm{5},则易见G=P_{\mathrm{5}}且{\gamma }_{gI}(G)=n-\mathrm{1}\mathrm{。}下设n\ge \mathrm{6}\mathrm{。}在这种情况下，为证明结论成立，只需要证明{\gamma }_{gI}(G)\ne n-\mathrm{1}即可。设P=v_{\mathrm{1}}{v}_{\mathrm{2}}\cdots v_{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)+\mathrm{1}}是图G的一条直径路。如果\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)\ge \mathrm{5},则函数f使得f(v_{\mathrm{2}})=f(v_{\mathrm{4}})=\mathrm{0}且当x\notin \{v_{\mathrm{2}},v_{\mathrm{4}}\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2}\mathrm{。}因此不妨假设\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)=\mathrm{4}\mathrm{。}

若d(v_{\mathrm{1}})\ge \mathrm{2},则不妨设u\in N(v_{\mathrm{1}})-\{v_{\mathrm{2}}\}\mathrm{。}因为P是图G的直径路，所以u\notin N(v_{\mathrm{4}})\mathrm{。}于是函数f使得f(v_{\mathrm{1}})=f(v_{\mathrm{4}})=\mathrm{2}，f(v_{\mathrm{2}})=f(v_{\mathrm{3}})=f(v_{\mathrm{5}})=f(u)=\mathrm{0}且当x\notin \{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{5}},u\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2}\mathrm{。}同理，若d(v_{\mathrm{5}})\ge \mathrm{2},则{\gamma }_{gI}(G)\le n-\mathrm{2}\mathrm{。}因此可以假设d(v_{\mathrm{1}})=d(v_{\mathrm{5}})=\mathrm{1}\mathrm{。}

如果d(v_{\mathrm{2}})\ge \mathrm{3},则不妨假设u\in N(v_{\mathrm{2}})-\{v_{\mathrm{1}},v_{\mathrm{3}}\}\mathrm{。}易见函数f使得f(v_{\mathrm{2}})=f(v_{\mathrm{5}})=\mathrm{2}，f(v_{\mathrm{1}})=f(v_{\mathrm{3}})=f(v_{\mathrm{4}})=f(u)=\mathrm{0}且当x\notin \{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{5}},u\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2}\mathrm{。}同理，如果d(v_{\mathrm{4}})\ge \mathrm{3},则{\gamma }_{gI}(G)\le n-\mathrm{2}\mathrm{。}因此可以假设d(v_{\mathrm{2}})=d(v_{\mathrm{4}})=\mathrm{2}\mathrm{。}注意到d(v_{\mathrm{1}})=d(v_{\mathrm{5}})=\mathrm{1}\mathrm{。}又因为n\ge \mathrm{6},所以d(v_{\mathrm{3}})\ge \mathrm{3}\mathrm{。}于是函数f使得f(v_{\mathrm{2}})=f(v_{\mathrm{4}})=\mathrm{0}且当x\notin \{v_{\mathrm{2}},v_{\mathrm{4}}\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2}\mathrm{。}

引理2 对于直径为3的任意n阶连通图G,{\gamma }_{gI}(G)=n-\mathrm{1}当且仅当图G满足下列条件之一：

（1）G=S_{\mathrm{1,2}}; （2）G\in \{G_{\mathrm{1}},G_{\mathrm{2}},\cdots ,G_{\mathrm{6}}\},其中图G_i(\mathrm{1}\le i\le \mathrm{6})如图1所示。

证明 如果G=S_{\mathrm{1,2}}或G\in \{G_{\mathrm{1}},G_{\mathrm{2}},\cdots ,G_{\mathrm{6}}\},则由图1知，{\gamma }_{gI}(G)=n-\mathrm{1},因此充分性成立。下面证明必要性也成立。设{\gamma }_{gI}(G)=n-\mathrm{1}\mathrm{。}令P=v_{\mathrm{1}}{v}_{\mathrm{2}}{v}_{\mathrm{3}}{v}_{\mathrm{4}}是图G的一条直径路。

首先证明d(v_{\mathrm{1}})+d(v_{\mathrm{4}})\le \mathrm{3}\mathrm{。}（反证法）假设d(v_{\mathrm{1}})+d(v_{\mathrm{4}})\ge \mathrm{4}\mathrm{。}因为P是图G的直径路，所以N(v_{\mathrm{1}})\bigcap N(v_{\mathrm{4}})=\mathrm{\varnothing }\mathrm{。}于是函数f使得f(v_{\mathrm{1}})=f(v_{\mathrm{4}})=\mathrm{2};当x\in N(v_{\mathrm{1}})\bigcup N(v_{\mathrm{4}})时，f(x)=\mathrm{0}且当x\notin N[v_{\mathrm{1}}]\bigcup N[v_{\mathrm{4}}]时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故

{\gamma }_{gI}(G)\le \omega (f)=\left(n-\left|N[v_{\mathrm{1}}]\bigcup N[v_{\mathrm{4}}]\right|\right)+\mathrm{4}=(n-d(v_{\mathrm{1}})-d(v_{\mathrm{4}})-\mathrm{2})+\mathrm{4}\le n-\mathrm{2},

与{\gamma }_{gI}(G)=n-\mathrm{1}矛盾。因此d(v_{\mathrm{1}})+d(v_{\mathrm{4}})\le \mathrm{3}\mathrm{。}不失一般性，假设d(v_{\mathrm{1}})=d(v_{\mathrm{4}})=\mathrm{1}或d(v_{\mathrm{1}})=\mathrm{2}且d(v_{\mathrm{4}})=\mathrm{1}\mathrm{。}下面分两种情形考虑。

情形1d(v_{\mathrm{1}})=d(v_{\mathrm{4}})=\mathrm{1}\mathrm{。}

在这种情形下，我们给出以下两个断言。

断言1 \left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|\in \{\mathrm{0,1}\}且\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|\in \{\mathrm{2,3}\}\mathrm{。}

断言1的证明 首先证明\left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|\in \{\mathrm{0,1}\}\mathrm{。}（反证法）假设\left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|\ge \mathrm{2}\mathrm{。}则函数f使得当x\in N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})时，f(x)=\mathrm{0}且当x\notin N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})时，f(x)=\mathrm{1}是G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|\le n-\mathrm{2},与{\gamma }_{gI}(G)=n-\mathrm{1}矛盾。因此\left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|\in \{\mathrm{0,1}\}\mathrm{。}

其次证明\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|\in \{\mathrm{2,3}\}\mathrm{。}因为

v_{\mathrm{1}},v_{\mathrm{4}}\in (N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}]),

所以

\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|\ge \mathrm{2}\mathrm{。}

下证\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|\le \mathrm{3}\mathrm{。}（反证法）假设

\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|\ge \mathrm{4}\mathrm{。}

易见函数f使得f(v_{\mathrm{2}})=f(v_{\mathrm{3}})=\mathrm{2};当x\in (N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])时，f(x)=\mathrm{0}，且当x\notin (N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}}))时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故

{\gamma }_{gI}(G)\le \omega (f)=\left(n-\mathrm{2}-\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|\right)+\mathrm{4}\le (n-\mathrm{2}-\mathrm{4})+\mathrm{4}=n-\mathrm{2},

与{\gamma }_{gI}(G)=n-\mathrm{1}矛盾。因此\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|\le \mathrm{3}\mathrm{。} 断言1得证。

断言2 G\in \{S_{\mathrm{1,2}},G_{\mathrm{1}},G_{\mathrm{2}}\}\mathrm{。}

断言2的证明 由断言1知，\left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|\in \{\mathrm{0,1}\}且\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|\in \{\mathrm{2,3}\}\mathrm{。}注意到\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)=\mathrm{3}且d(v_{\mathrm{1}})=d(v_{\mathrm{4}})=\mathrm{1}\mathrm{。}因此，如果\left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|=\mathrm{0}且\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|=\mathrm{2},则显然G=P_{\mathrm{4}}并且由定理1知，{\gamma }_{gI}(P_{\mathrm{4}})=n,矛盾；如果\left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|=\mathrm{0}且\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|=\mathrm{3},则易见G=S_{\mathrm{1,2}}\mathrm{。}

下面假设\left|N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})\right|=\mathrm{1}\mathrm{。}令N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})=\{w\}\mathrm{。}首先设

\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|=\mathrm{2},

即(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])=\{v_{\mathrm{1}},v_{\mathrm{4}}\}\mathrm{。}则N(v_{\mathrm{2}})=\{v_{\mathrm{1}},v_{\mathrm{3}},w\}且N(v_{\mathrm{3}})=\{v_{\mathrm{2}},v_{\mathrm{4}},w\}\mathrm{。} 注意到d(v_{\mathrm{1}})=d(v_{\mathrm{4}})=\mathrm{1}\mathrm{。}因此如果n\ge \mathrm{6},则V(G)-\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},w\}中一定存在某个顶点，不妨设为w\mathrm{\text{'}},使得w\mathrm{\text{'}}\in N(w)且w\mathrm{\text{'}}\notin N(v_{\mathrm{1}})\bigcup N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}})\bigcup N(v_{\mathrm{4}})\mathrm{。}于是不难验证函数g使得g(v_{\mathrm{2}})=g(v_{\mathrm{3}})=\mathrm{0}且当x\notin \{v_{\mathrm{2}},v_{\mathrm{3}}\}时，g(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (g)=n-\mathrm{2},矛盾。因此n=\mathrm{5},即G=G_{\mathrm{1}}\mathrm{。}

其次设\left|(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])\right|=\mathrm{3}\mathrm{。}不失一般性，假设

(N(v_{\mathrm{2}})\bigcup N(v_{\mathrm{3}}))-(N[v_{\mathrm{2}}]\bigcap N[v_{\mathrm{3}}])=\{v_{\mathrm{1}},v_{\mathrm{4}},u\},

其中N(v_{\mathrm{2}})-\{v_{\mathrm{1}},v_{\mathrm{3}},w\}=\{u\}\mathrm{。}因为N(v_{\mathrm{2}})\bigcap N(v_{\mathrm{3}})=\{w\},所以u\notin N(v_{\mathrm{3}})\mathrm{。}如果n\ge \mathrm{7},则前面定义的函数g是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (g)=n-\mathrm{2},矛盾。因此n=\mathrm{6}\mathrm{。}如果uw\in E(G),则函数f使得f(v_{\mathrm{3}})=f(w)=\mathrm{0}且当x\notin \{v_{\mathrm{3}},w\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。因此uw\notin E(G),即G=G_{\mathrm{2}}\mathrm{。}断言2得证。

情形2d(v_{\mathrm{1}})=\mathrm{2}且d(v_{\mathrm{4}})=\mathrm{1}\mathrm{。}

在这种情形下，设N(v_{\mathrm{1}})-\{v_{\mathrm{2}}\}=\{u\}\mathrm{。}我们给出以下四个断言。

断言3 \left|N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|\in \{\mathrm{1,2}\}\mathrm{。}

断言3的证明 假设\left|N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{0}\mathrm{。}因为P=v_{\mathrm{1}}{v}_{\mathrm{2}}{v}_{\mathrm{3}}{v}_{\mathrm{4}}是图G的一条直径路且d(v_{\mathrm{4}})=\mathrm{1},所以一定存在某个顶点w\in N(v_{\mathrm{3}})\bigcap N(u)（否则，d(u,v_{\mathrm{4}})\ge \mathrm{4}>\mathrm{3}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G),矛盾）。又因为N(v_{\mathrm{1}})=\{u,v_{\mathrm{2}}\}且N(v_{\mathrm{4}})=\{v_{\mathrm{3}}\},所以函数f使得f(v_{\mathrm{2}})=f(w)=\mathrm{0}，且当x\notin \{v_{\mathrm{2}},w\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。因此断言3得证。

断言4 如果\left|N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{1},则G\in \{G_{\mathrm{3}},G_{\mathrm{4}}\}\mathrm{。}

断言4的证明 假设G\notin \{G_{\mathrm{3}},G_{\mathrm{4}}\}\mathrm{。}则\left|V(G)-\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},u\}\right|\ge \mathrm{1}\mathrm{。}不失一般性，假设w\in V(G)-\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},u\}\mathrm{。}注意到N(v_{\mathrm{1}})=\{u,v_{\mathrm{2}}\}且N(v_{\mathrm{4}})=\{v_{\mathrm{3}}\}\mathrm{。}因此如果\left|N(w)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{2},则函数f使得f(u)=f(w)=\mathrm{0}，且当x\notin \{u,w\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。如果\left|N(w)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{1},则因为\left|N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{1},所以函数f使得f(v_{\mathrm{2}})=f(v_{\mathrm{3}})=\mathrm{2},f(v_{\mathrm{1}})=f(v_{\mathrm{4}})=f(u)=f(w)=\mathrm{0}，且当x\notin \{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},u,w\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。因此N(w)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}=\mathrm{\varnothing }\mathrm{。}

注意到\left|N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{1}\mathrm{。}若N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}=\{v_{\mathrm{2}}\},则函数f使得f(v_{\mathrm{1}})=f(v_{\mathrm{3}})=\mathrm{0}，且当x\notin \{v_{\mathrm{1}},v_{\mathrm{3}}\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。因此N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}=\{v_{\mathrm{3}}\}\mathrm{。}

如果uw\in E(G),则函数f使得f(u)=f(v_{\mathrm{3}})=\mathrm{0}，且当x\notin \{u,v_{\mathrm{3}}\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。如果uw\notin E(G),则函数f使得f(u)=f(v_{\mathrm{2}})=\mathrm{0}，且当x\notin \{u,v_{\mathrm{2}}\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。因此G\in \{G_{\mathrm{3}},G_{\mathrm{4}}\}\mathrm{。}断言4得证。

断言5 如果\left|N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{2},则对任意x\notin \{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},u\},\left|N(x)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{2}\mathrm{。}

断言5的证明 假设存在顶点w\notin \{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},u\}使得\left|N(w)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|\le \mathrm{1}\mathrm{。}如果\left|N(w)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{0},则函数f使得f(v_{\mathrm{2}})=f(v_{\mathrm{3}})=\mathrm{0}，且当x\notin \{v_{\mathrm{2}},v_{\mathrm{3}}\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。下设\left|N(w)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{1}\mathrm{。}

如果w\in (N(v_i)-N(v_{\mathrm{5}-i}))\bigcap N(u),其中i\in \{\mathrm{2,3}\},则函数f使得f(v_{\mathrm{1}})=f(w)=\mathrm{0}，且当x\notin \{v_{\mathrm{1}},w\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。如果w\in N(v_i)-(N(v_{\mathrm{5}-i})\bigcup N(u)),其中i\in \{\mathrm{2,3}\},则函数f使得f(u)=f(v_{\mathrm{5}-i})=\mathrm{0}，且当x\notin \{u,v_{\mathrm{5}-i}\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。断言5得证。

断言6 如果\left|N(u)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{2},则G\in \{G_{\mathrm{5}},G_{\mathrm{6}}\}\mathrm{。}

断言6的证明 如果n\ge \mathrm{7},则不妨设w,w\mathrm{\text{'}}\in V(G)-\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},u\}\mathrm{。}于是由断言5知，\left|N(w)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\left|N(w\mathrm{\text{'}})\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{2}\mathrm{。}注意到N(v_{\mathrm{1}})=\{u,v_{\mathrm{2}}\}且N(v_{\mathrm{4}})=\{v_{\mathrm{3}}\}\mathrm{。}因此函数f使得f(w)=f(w\mathrm{\text{'}})=\mathrm{0}，且当x\notin \{w,w\mathrm{\text{'}}\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，于是{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。故n\in \{\mathrm{5,6}\}\mathrm{。}

如果n=\mathrm{5},则显然G=G_{\mathrm{5}}\mathrm{。}下设n=\mathrm{6}且V(G)-\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},u\}=\{w\}\mathrm{。}于是由断言5知，\left|N(w)\bigcap \{v_{\mathrm{2}},v_{\mathrm{3}}\}\right|=\mathrm{2}\mathrm{。}如果uw\notin E(G),则函数f使得f(v_{\mathrm{1}})=f(w)=\mathrm{0}，且当x\notin \{v_{\mathrm{1}},w\}时，f(x)=\mathrm{1}是图G的全局意大利控制函数，故{\gamma }_{gI}(G)\le \omega (f)=n-\mathrm{2},矛盾。因此uw\in E(G),即G=G_{\mathrm{6}}\mathrm{。}断言6得证。

因此如果{\gamma }_{gI}(G)=n-\mathrm{1},则由断言2、4和6知，G=S_{\mathrm{1,2}}或G\in \{G_{\mathrm{1}},G_{\mathrm{2}},\cdots ,G_{\mathrm{6}}\},即必要性成立。

定理2的证明 由引理1和引理2知，定理2显然成立。

4 结论

本文主要研究了图的控制理论中的全局意大利控制问题。通过对图的结构分析，利用分类讨论法刻画了{\gamma }_{gI}(G)=n成立的所有n阶连通图。此外，还刻画了{\gamma }_{gI}(G)=n-\mathrm{1}成立的所有直径不小于3的n阶连通图。在未来的研究中，可以考虑刻画{\gamma }_{gI}(G)=n-\mathrm{1}成立的直径为2的n阶连通图。

参考文献

[1] ORE O. Theory of Graphs[M]. Providence, Rhode Island: American Mathematical Society, 1962. DOI: 10.1090/coll/038 .

[2] BABIKIR A, HENNING M A. Domination Versus Total Domination in Claw-free Cubic Graphs[J]. Discrete Math, 2022, 345(4): 112784. DOI: 10.1016/j.disc.2021.112784 .

[3] BLIDIA M, BOUCHOU A, CHELLALI M. Extremal Graphs for a Bound on the Roman Domination Number[J]. Discuss Math Graph Theory, 2020, 40(3): 771. DOI: 10.7151/dmgt.2142 .

[4] MEIYANATHAN M, ANITHA K. Domination, Edge Domination and Roman Domination in Human Chain Graph[J]. J Phys: Conf Ser, 2021, 1724(1): 012023. DOI: 10.1088/1742-6596/1724/1/012023 .

[5] SUN X L, DU J W. On Sombor Index of Trees with Fixed Domination Number[J]. Appl Math Comput, 2022, 421: 126946. DOI: 10.1016/j.amc.2022.126946 .

[6] 张新鸿, 郭亚丽. 有向de Bruijn图与广义有向de Bruijn图的罗马控制数[J]. 山西大学学报(自然科学版), 2023, 46(5): 1042-1049. DOI: 10.13451/j.sxu.ns.2023007 .

[7] ZHANG X H, GUO Y L. The Roman Domination Numbers of the Directed de Bruijn and Generalized Directed de Bruijn Graphs[J]. J Shanxi Univ Nat Sci Ed, 2023, 46(5): 1042-1049. DOI: 10.13451/j.sxu.ns.2023007 .

[8] JOSEPH J, JOSEPH M. Roman Domination in Signed Graphs[J]. Commun Comb Optim, 2023, 8(2): 349-358. DOI:10.22049/cco.2022.27438.1264 .

[9] 郝国亮, 曾淑婷, 庄蔚, 等. 全局3-彩虹控制数与3-彩虹控制数之差为2和3的树的刻画[J]. 大连理工大学学报, 2023, 63(5): 544-550. DOI: 10.7511/dllgxb202305014 .

[10] HAO G L, ZENG S T, ZHUANG W, et al. Characterization of Trees with Difference of Their Global 3-rainbow Domination Number and 3-rainbow Domination Number being 2 and 3[J]. J Dalian Univ Technol, 2023, 63(5): 544-550. DOI: 10.7511/dllgxb202305014 .

[11] HAO G L, XIE Z H, SHEIKHOLESLAMI S M, et al. Bounds on the Total Double Roman Domination Number of Graphs[J]. Discuss Math Graph Theory, 2023, 43(4): 1033. DOI: 10.7151/dmgt.2417 .

[12] COCKAYNE E J, DREYER P A, HEDETNIEMI S M, et al. Roman Domination in Graphs[J]. Discrete Math, 2004, 278(1/2/3): 11-22. DOI: 10.1016/j.disc.2003.06.004 .

[13] STEWART I. Defend the Roman Empire![J]. Sci Am, 1999, 281(6): 136-138. DOI: 10.1038/scientificamerican1299-136 .

[14] CHELLALI M, HAYNES T W, HEDETNIEMI S T, et al. Roman{2}-domination[J]. Discrete Appl Math, 2016, 204(C): 22-28. DOI: 10.1016/j.dam.2015.11.013 .

[15] HENNING M A, KLOSTERMEYER W F. Italian Domination in Trees[J]. Discrete Appl Math, 2017, 217(P3): 557-564. DOI: 10.1016/j.dam.2016.09.035 .

[16] VARGHESE J, APARNA LAKSHMANAN S. Italian Domination on Mycielskian and Sierpinski Graphs[J]. Discrete Math Algorithm Appl, 2021, 13(4): 2150037. DOI: 10.1142/s1793830921500373 .

[17] VAN BOMMEL C M. Italian Domination of Cartesian Products of Directed Cycles[J]. Discrete Appl Math, 2021, 299: 82-86. DOI: 10.1016/j.dam.2021.04.023 .

[18] GAO H, XI C Q, LI K, et al. The Italian Domination Numbers of Generalized Petersen Graphs P(N, 3)[J]. Mathematics, 2019, 7(8): 714. DOI: 10.3390/math7080714 .

[19] HAYNES T W, HENNING M A, VOLKMANN L. Graphs with Large Italian Domination Number[J]. Bull Malays Math Sci Soc, 2020, 43(6): 4273-4287. DOI: 10.1007/s40840-020-00921-y .

[20] HAO G L, HU K X, WEI S L, et al. Global Italian Domination in Graphs[J]. Quaest Math, 2019, 42(8): 1101-1115. DOI: 10.2989/16073606.2018.1506831 .

基金资助

国家自然科学基金(12061007)

菏泽学院博士基金(XY23BS12)

菏泽学院博士基金(XY23BS48)