图的符号全控制数

Signed Total Domination Number of Graphs

摘要: 设图G=(V,E)为一个图，一个双值函数f:v→{-1,+1}，若S⊆V，则记f(S)=∑_V∈Sf(V)。如果对任意的顶点ν∈V，均有f(N(ν))≥1成立，则称f为图G的一个符号全控制函数。图G的符号全控制数定义为γ_st(G)=min{f(V)|f是图G的一个符号全控制函数}。本文首先给出一般图的符号全控制数的下界，然后用分类讨论和穷标法得到了两类图广义Petesen图P(n,k)和Double广义Petesen图DP(n,k)的符号全控制数的精确值，这里n≡0(mod3),k≠0(mod3)。

Abstract: Let G=(V,E) be a graph and denotes f(S)=∑_V∈Sf(V) for S⊆V. A function f:v→{-1,+1} is said to be a signed total domination function (STDF), if f(N(ν))≥1 for ν∈V. The signed total domination number is γ_st(G)=min{f(V)|f is an STDF of G}. In this paper, a lower bound of the signed total domination number are obtained and we determine a exact value of signed total domi-nation number of two classes graphs generalized Petesen graph P(n,k) and Double generalized Petesen graph DP(n,k) by exhaustived method and classified discussion, where n≡0(mod3),k≠0(mod3).

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)$ 表示为u点在G中的领域， $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],\delta \left(G\right),\Delta \left(G\right)$ 分别简单记为 $N\left(u\right),N\left[u\right],\delta ,\Delta$ 。图G中两个顶点u和v之间的距离指连接这两个点的最短路的长度，记为 $d\left(u,v\right)$ 。

近几十年来，图的控制理论的研究内容越来越丰富，各种类型的符号控制数以及其变化的形式依次被提出，如图的符号控制数 [2] [3] [4] 、图的边符号控制数 [5] 、图的边全符号控制数 [5] 、图的符号全控制数 [6] [7] 、图的星符号控制数 [5] 、图的团符号(边)控制数 [5] 、图的逆符号(边)控制数 [5] 、图的反符号(边)控制数 [5] 、图的圈符号(边)控制数 [8] 、罗曼符号(边)控制数 [9] [10] 等。其中首次被提出的是图的符号控制概念，由J E Dunbar等人在1995年提出。图的符号控制数的研究有着广泛的应用背景，如交通岗位、物资供应点的设置等，但是符号控制数的计算是NP完全问题。

目前很多相关学者研究了关于图的符号全控制数的上下界 [11] [12] 以及特殊图的符号全控制数的精确值 [13] 。本文中主要得到了符号全控制数的一个下界以及两类图广义Petesen图 $P\left(n,k\right)$ 和Double广义Petesen图 $DP\left(n,k\right)$ 的符号全控制数的精确值，这里 $n\equiv 0\left(\mathrm{mod}3\right),k\ne 0\left(\mathrm{mod}3\right)$ 。

对于图 $G=\left(V,E\right)$ ，定义一个函数 $f:V\to R$ 和G的一个子集 $S\subseteq V$ ，记 $f\left(S\right)={\displaystyle {\sum }_{v\in S}f\left(v\right)}$ 。为简单起见，下文中适合 $f\left(u\right)=+1$ 的顶点称为+1点，适合 $f\left(u\right)=-1$ 的顶点称为-1点，用 ${{\rm Z}}_n$ 表示模n的剩余类。

2. 基本概念

定义1 [6] ：设图 $G=\left(V,E\right)$ 为一个图，一个双值函数 $f:V\to \left\{-1,+1\right\}$ ，若 $S\subseteq V$ ，则记 $f\left(S\right)={\displaystyle {\sum }_{v\in S}f\left(v\right)}$ 。

如果对任意的顶点 $v\in V$ ，均有 $f\left(N\left(v\right)\right)\ge 1$ 成立，则称f为图G的一个符号全控制函数，图G的符号全控制数定义为 ${\gamma }_{st}\left(G\right)=\min \left\{f\left(V\right)|f是图G的一个符号全控制函数\right\}$ 并将使得 ${\gamma }_{st}\left(G\right)=f\left(V\right)$ 的符号全控制函数称f为图G的一个最小符号全控制函数。

从定义1可以看出以下性质。

性质：设G是 $n\left(n>1\right)$ 个顶点的简单图。若 $f=\left(V_{-1},V_{+1}\right)$ 是图G一个最小符号全控制函数，则有以下结论成立。

i) $\left|V_{-1}\right|+\left|V_{+1}\right|=n$

ii) ${\gamma }_{st}\left(G\right)=\left|V_{+1}\right|-\left|V_{-1}\right|$

定义2 [5] ：设 $n,k$ 都是正整数且 $n>2k$ 。广义Petersen图 $P\left(n,k\right)$ 是具有2n个顶点的图，它的顶点集 $V\left(P\left(n,k\right)\right)$ 和边集 $E\left(P\left(n,k\right)\right)$ 分别为：

$\begin{array}{l}V\left(P\left(n,k\right)\right)=\left\{u_1,u_2,\cdots ,u_n,v_1,v_2,\cdots ,v_n\right\}\\ E\left(P\left(n,k\right)\right)=\left\{u_i{u}_{i+1},u_i{v}_i,v_i{v}_{i+k}|i\in {{\rm Z}}_n\right\}\end{array}$

定义3 [14] ：设n和k是正整数且 $n\ge 3,2\le 2k<n$ 。Double广义Petesen图 $DP\left(n,k\right)$ 是4n个顶点的简单图，它的顶点集 $V\left(P\left(n,k\right)\right)$ 和边集 $E\left(P\left(n,k\right)\right)$ 分别为：

$\begin{array}{l}V\left(P\left(n,k\right)\right)=\left\{x_i,u_i,v_i,y_i|i\in {{\rm Z}}_n\right\}\\ E\left(P\left(n,k\right)\right)=\left\{x_i{x}_{i+1},y_i{y}_{i+1},x_i{u}_i,y_i{v}_i,u_i{v}_{i+k},v_i{u}_{i+k}|i\in {{\rm Z}}_n\right\}\end{array}$

显然，广义Petersen图 $P\left(n,k\right)$ 和Double广义Petesen图 $DP\left(n,k\right)$ 都是3-正则图。

引理 [6] ：设G是一个r-正则图。若r是奇数，则 ${\gamma }_{st}\left(G\right)\ge n/r$ ；若r是偶数，则 ${\gamma }_{st}\left(G\right)\ge 2n/r$ 。

3. 主要定理及其证明

定理1：设图G是 $n\left(n>1\right)$ 个顶点的简单图。若 $f=\left(V_{-1},V_{+1}\right)$ 是图G一个最小符号全控制函数，且 $\delta =\delta \left(G\right)\ge 1$ ， $\Delta =\Delta \left(G\right)$ ，则有以下结论成立。

i) $\left(\Delta -1\right)\left|V_{+1}\right|\ge \left(\delta +1\right)\left|V_{-1}\right|$ ；

ii) $\left|V_{+1}\right|\ge \frac{\delta +1}{\Delta +\delta }n$ ；

iii) ${\gamma }_{st}\left(G\right)\ge \frac{\delta +2-\Delta }{\Delta +\delta }n$ ；

证明：i) 假设 $f=\left(V_{-1},V_{+1}\right)$ 是图G一个最小符号全控制函数，由性质，有

$\begin{array}{c}\left|V_{-1}\right|+\left|V_{+1}\right|=n\le {\displaystyle {\sum }_{v\in V\left(G\right)}f\left(N\left(v\right)\right)={\displaystyle {\sum }_{v\in V\left(G\right)}d\left(v\right)f\left(v\right)}}\\ ={\displaystyle {\sum }_{v\in V_{+1}}d\left(v\right)}-{\displaystyle {\sum }_{v\in V_{-1}}d\left(v\right)}\le \Delta \left|V_{+1}\right|-\delta \left|V_{-1}\right|\end{array}$

从而有

$\left(\Delta -1\right)\left|V_{+1}\right|\ge \left(\delta +1\right)\left|V_{-1}\right|$

ii) 由性质和i)，推导出

$\left(\Delta -1\right)\left|V_{+1}\right|\ge \left(\delta +1\right)\left(n-\left|V_{+1}\right|\right)=\delta n+n-\delta \left|V_{+1}\right|-\left|V_{+1}\right|$

通过移项，得

$\left|V_{+1}\right|\ge \frac{\delta +1}{\Delta +\delta }n$

iii) 由性质和i)，有

$\left(\Delta +\delta \right){\gamma }_{st}\left(G\right)=\left(\Delta +\delta \right)\left(2\left|V_{+1}\right|-n\right)\ge 2\left(\delta +1\right)n-\left(\Delta +\delta \right)n=\left(\delta +2-\Delta \right)n$

故，有

${\gamma }_{st}\left(G\right)\ge \frac{\delta +2-\Delta }{\Delta +\delta }n$

推论：设G是一个r-正则图，那么有 ${\gamma }_{st}\left(G\right)\ge \frac{n}{r}$ 。

注：定理1的结果与引理的结论一致。

定理2：设图G是广义Petersen图 $P\left(n,k\right)$ 且 $n\equiv 0\left(\mathrm{mod}3\right),k\ne 0\left(\mathrm{mod}3\right)$ 。那么

${\gamma }_{st}\left(P\left(n,k\right)\right)=\frac{2n}{3}$

证明：令图G是广义Petersen图 $P\left(n,k\right)$ ，这里 $n\equiv 0\left(\mathrm{mod}3\right),k\ne 0\left(\mathrm{mod}3\right)$ 。记

$\begin{array}{l}V\left(P\left(n,k\right)\right)=\left\{u_1,u_2,\cdots ,u_n,v_1,v_2,\cdots ,v_n\right\}\\ E\left(P\left(n,k\right)\right)=\left\{u_i{u}_{i+1},u_i{v}_i,v_i{v}_{i+k}|i\in {{\rm Z}}_n\right\}\end{array}$

因此，有

$\left|V\left(P\left(n,k\right)\right)\right|=2n,\left|E\left(P\left(n,k\right)\right)\right|=3n$

由定理1，有

${\gamma }_{st}\left(P\left(n,k\right)\right)\ge \frac{2n}{3}$

下面我们定义图G的一个符号全控制数f：

$f\left(u_i\right)=\{\begin{array}{l}+1,当i\equiv 0,2\left(\mathrm{mod}3\right)\\ -1,当i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

$f\left(v_i\right)=\{\begin{array}{l}+1,当i\equiv 0,2\left(\mathrm{mod}3\right)\\ -1,当i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

这里 $i\in {{\rm Z}}_n$

容易验证，对于每个顶点 $x\in V\left(G\right)$ ，有 $f\left(N\left(x\right)\right)=1$ 。注意到此时图G中-1点个数t为 $\frac{2n}{3}$ ，+1点个数s为 $\frac{4n}{3}$ 。从而

$f\left(V\left(G\right)\right)=s-t=\frac{2n}{3}$

因此，有

${\gamma }_{st}\left(P\left(n,k\right)\right)\le \frac{2n}{3}$

定理2：证毕。

定理3：设图G是Double广义Petesen图 $DP\left(n,k\right)$ 且 $n\equiv 0\left(\mathrm{mod}3\right),k\ne 0\left(\mathrm{mod}3\right)$ 。那么

${\gamma }_{st}\left(DP\left(n,k\right)\right)=\frac{4n}{3}$

证明：令图G是Double广义Petesen图 $DP\left(n,k\right)$ ，这里 $n\equiv 0\left(\mathrm{mod}3\right),k\ne 0\left(\mathrm{mod}3\right)$ 。记

$\begin{array}{l}V\left(P\left(n,k\right)\right)=\left\{x_i,u_i,v_i,y_i|i\in {{\rm Z}}_n\right\}\\ E\left(P\left(n,k\right)\right)=\left\{x_i{x}_{i+1},y_i{y}_{i+1},x_i{u}_i,y_i{v}_i,u_i{v}_{i+k},v_i{u}_{i+k}|i\in {{\rm Z}}_n\right\}\end{array}$

因此，有

$\left|V\left(P\left(n,k\right)\right)\right|=4n,\left|E\left(P\left(n,k\right)\right)\right|=5n$

由定理1，有

${\gamma }_{st}\left(P\left(n,k\right)\right)\ge \frac{4n}{3}$

下面我们定义图G的一个符号全控制数f：

$f\left(x_i\right)=\{\begin{array}{l}+1,当i\equiv 0,2\left(\mathrm{mod}3\right)\\ -1,当i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

$f\left(u_i\right)=\{\begin{array}{l}+1,当i\equiv 0,2\left(\mathrm{mod}3\right)\\ -1,当i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

$f\left(v_i\right)=\{\begin{array}{l}+1,当i\equiv 0,2\left(\mathrm{mod}3\right)\\ -1,当i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

$f\left(y_i\right)=\{\begin{array}{l}+1,当i\equiv 0,2\left(\mathrm{mod}3\right)\\ -1,当i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

这里 $i\in {{\rm Z}}_n$

容易验证，对于每个顶点 $w\in V\left(G\right)$ ，有 $f\left(N\left(w\right)\right)=1$ 。注意到此时图G中-1点个数t为 $\frac{4n}{3}$ ，+1点个数s为 $\frac{8n}{3}$ 。从而

$f\left(V\left(G\right)\right)=s-t=\frac{4n}{3}$

因此，有

${\gamma }_{st}\left(P\left(n,k\right)\right)\le \frac{4n}{3}$

定理3证毕。

基金项目

国家自然科学基金(No. 11701257, No.11801253, No. 11571005)，河南省教育厅高校重点项目(No. 18A110025, No. 18A110026)、河南省科技计划项目(182102310930, 182102310955)、(2017-JSJYYB-074)。