AAM  >> Vol. 7 No. 12 (December 2018)

    图的符号全控制数
    Signed Total Domination Number of Graphs

  • 全文下载: PDF(541KB) HTML   XML   PP.1543-1548   DOI: 10.12677/AAM.2018.712180  
  • 下载量: 242  浏览量: 385   国家自然科学基金支持

作者:  

红 霞,高 峰,张彩环,魏春艳:洛阳师范学院数学科学学院,河南 洛阳

关键词:
符号全控制函数符号全控制数广义Petesen图P(nk)Double广义Petesen图DP(nk)Signed Total Domination Function Signed Total Domination Number Generalized Petesen Graph P(nk) Double Generalized Petesen Graph DP(nk)

摘要:

设图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)

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 = ( V , E ) 是一个图,其顶点集 V = V ( G ) 和边集 E = E ( G ) 。对任意 u V ( G ) ,则 N G ( u ) 表示为u点在G中的领域, N G [ u ] = N G ( u ) { u } 为u点在G中的闭领域, d G ( u ) = | N G ( u ) | 为u点在G中的度,而 δ = δ ( G ) Δ = Δ ( G ) 分别为图G的最小度和最大度。在不致混淆情况下,可将 N G ( u ) , N G [ u ] , δ ( G ) , Δ ( G ) 分别简单记为 N ( u ) , N [ u ] , δ , Δ 。图G中两个顶点u和v之间的距离指连接这两个点的最短路的长度,记为 d ( u , v )

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

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

对于图 G = ( V , E ) ,定义一个函数 f : V R 和G的一个子集 S V ,记 f ( S ) = v S f ( v ) 。为简单起见,下文中适合 f ( u ) = + 1 的顶点称为+1点,适合 f ( u ) = 1 的顶点称为-1点,用 Ζ n 表示模n的剩余类。

2. 基本概念

定义1 [6] :设图 G = ( V , E ) 为一个图,一个双值函数 f : V { 1 , + 1 } ,若 S V ,则记 f ( S ) = v S f ( v )

如果对任意的顶点 v V ,均有 f ( N ( v ) ) 1 成立,则称f为图G的一个符号全控制函数,图G的符号全控制数定义为 γ s t ( G ) = min { f ( V ) | f G } 并将使得 γ s t ( G ) = f ( V ) 的符号全控制函数称f为图G的一个最小符号全控制函数。

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

性质:设G是 n ( n > 1 ) 个顶点的简单图。若 f = ( V 1 , V + 1 ) 是图G一个最小符号全控制函数,则有以下结论成立。

i) | V 1 | + | V + 1 | = n

ii) γ s t ( G ) = | V + 1 | | V 1 |

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

V ( P ( n , k ) ) = { u 1 , u 2 , , u n , v 1 , v 2 , , v n } E ( P ( n , k ) ) = { u i u i + 1 , u i v i , v i v i + k | i Ζ n }

定义3 [14] :设n和k是正整数且 n 3 , 2 2 k < n 。Double广义Petesen图 D P ( n , k ) 是4n个顶点的简单图,它的顶点集 V ( P ( n , k ) ) 和边集 E ( P ( n , k ) ) 分别为:

V ( P ( n , k ) ) = { x i , u i , v i , y i | i Ζ n } E ( P ( n , k ) ) = { 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 Ζ n }

显然,广义Petersen图 P ( n , k ) 和Double广义Petesen图 D P ( n , k ) 都是3-正则图。

引理 [6] :设G是一个r-正则图。若r是奇数,则 γ s t ( G ) n / r ;若r是偶数,则 γ s t ( G ) 2 n / r

3. 主要定理及其证明

定理1:设图G是 n ( n > 1 ) 个顶点的简单图。若 f = ( V 1 , V + 1 ) 是图G一个最小符号全控制函数,且 δ = δ ( G ) 1 Δ = Δ ( G ) ,则有以下结论成立。

i) ( Δ 1 ) | V + 1 | ( δ + 1 ) | V 1 |

ii) | V + 1 | δ + 1 Δ + δ n

iii) γ s t ( G ) δ + 2 Δ Δ + δ n

证明:i) 假设 f = ( V 1 , V + 1 ) 是图G一个最小符号全控制函数,由性质,有

| V 1 | + | V + 1 | = n v V ( G ) f ( N ( v ) ) = v V ( G ) d ( v ) f ( v ) = v V + 1 d ( v ) v V 1 d ( v ) Δ | V + 1 | δ | V 1 |

从而有

( Δ 1 ) | V + 1 | ( δ + 1 ) | V 1 |

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

( Δ 1 ) | V + 1 | ( δ + 1 ) ( n | V + 1 | ) = δ n + n δ | V + 1 | | V + 1 |

通过移项,得

| V + 1 | δ + 1 Δ + δ n

iii) 由性质和i),有

( Δ + δ ) γ s t ( G ) = ( Δ + δ ) ( 2 | V + 1 | n ) 2 ( δ + 1 ) n ( Δ + δ ) n = ( δ + 2 Δ ) n

故,有

γ s t ( G ) δ + 2 Δ Δ + δ n

推论:设G是一个r-正则图,那么有 γ s t ( G ) n r

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

定理2:设图G是广义Petersen图 P ( n , k ) n 0 ( mod 3 ) , k 0 ( mod 3 ) 。那么

γ s t ( P ( n , k ) ) = 2 n 3

证明:令图G是广义Petersen图 P ( n , k ) ,这里 n 0 ( mod 3 ) , k 0 ( mod 3 ) 。记

V ( P ( n , k ) ) = { u 1 , u 2 , , u n , v 1 , v 2 , , v n } E ( P ( n , k ) ) = { u i u i + 1 , u i v i , v i v i + k | i Ζ n }

因此,有

| V ( P ( n , k ) ) | = 2 n , | E ( P ( n , k ) ) | = 3 n

由定理1,有

γ s t ( P ( n , k ) ) 2 n 3

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

f ( u i ) = { + 1 , i 0 , 2 ( mod 3 ) 1 , i 1 ( mod 3 )

f ( v i ) = { + 1 , i 0 , 2 ( mod 3 ) 1 , i 1 ( mod 3 )

这里 i Ζ n

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

f ( V ( G ) ) = s t = 2 n 3

因此,有

γ s t ( P ( n , k ) ) 2 n 3

定理2:证毕。

定理3:设图G是Double广义Petesen图 D P ( n , k ) n 0 ( mod 3 ) , k 0 ( mod 3 ) 。那么

γ s t ( D P ( n , k ) ) = 4 n 3

证明:令图G是Double广义Petesen图 D P ( n , k ) ,这里 n 0 ( mod 3 ) , k 0 ( mod 3 ) 。记

V ( P ( n , k ) ) = { x i , u i , v i , y i | i Ζ n } E ( P ( n , k ) ) = { 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 Ζ n }

因此,有

| V ( P ( n , k ) ) | = 4 n , | E ( P ( n , k ) ) | = 5 n

由定理1,有

γ s t ( P ( n , k ) ) 4 n 3

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

f ( x i ) = { + 1 , i 0 , 2 ( mod 3 ) 1 , i 1 ( mod 3 )

f ( u i ) = { + 1 , i 0 , 2 ( mod 3 ) 1 , i 1 ( mod 3 )

f ( v i ) = { + 1 , i 0 , 2 ( mod 3 ) 1 , i 1 ( mod 3 )

f ( y i ) = { + 1 , i 0 , 2 ( mod 3 ) 1 , i 1 ( mod 3 )

这里 i Ζ n

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

f ( V ( G ) ) = s t = 4 n 3

因此,有

γ s t ( P ( n , k ) ) 4 n 3

定理3证毕。

基金项目

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

文章引用:
红霞, 高峰, 张彩环, 魏春艳. 图的符号全控制数[J]. 应用数学进展, 2018, 7(12): 1543-1548. https://doi.org/10.12677/AAM.2018.712180

参考文献

[1] Bondy, J.A. and Murty, U.S.R. (1977) Graph Theory with Applications. Macmillan, London.
[2] Dunbar, J.E., He-detniemi, S.T. and Al Henning, M. (2006) Signed Domination in Graphs. Journal of Shanghai University, 10, 4-8.
[3] 尚华辉, 苗连英. 关于图的两类符号控制数的下界[J]. 数学的实践与认识, 2017, 47(21): 223-230.
[4] Zhang, Z.F., Xu, B.G. and Liu, L.Z. (1999) A Note on the Lower Bounds of Signed Domination Number of a Graph. Discrete Mathematics, 195, 295-298.
https://doi.org/10.1016/S0012-365X(98)00189-7
[5] 徐保根. 图的控制与染色理论[M]. 武汉: 华中科技大学出版社, 2013.
[6] Zelinka, B. (2001) Signed Total Domination Number of a Graph. Czechoslovak Mathematical Journal, 51, 225-229.
[7] Henning, M.A. (2004) Signed Total Domination in Graphs. Discrete Mathematics, 278, 109-125.
https://doi.org/10.1016/j.disc.2003.06.002
[8] Xu, B.G. (2009) On Signed Cycle Domination Numbers in Graphs. Discrete Mathematics, 309, 1007-1012.
https://doi.org/10.1016/j.disc.2008.01.007
[9] Volkmann, L. (2016) On the Signed Total Roman Domination and Domatic Numbers of Graphs. Discrete Applied Mathematics, 214, 179-186.
https://doi.org/10.1016/j.dam.2016.06.006
[10] Asgharsharghi, L. and Sheikholeslami, S.M. (2017) Signed Total Roman Edge Domination in Graphs. Discussiones Mathematicae Graph Theory, 37, 1039-1053.
https://doi.org/10.7151/dmgt.1984
[11] Moghaddam, S.M.H. (2016) New Bounds on the Signed Total Domination Number of Graphs. Discussiones Mathematicae. Graph Theory, 36, 467-477.
https://doi.org/10.7151/dmgt.1871
[12] 尚华辉, 谢凤艳. 关于图的两类符号全控制数[J]. 四川文理学院学报, 2016, 26(5): 17-20.
[13] Li, W.S., Xing, H.M. and Sohn, M.Y. (2013) On the Signed Total Domination Number of Generalized Petersen Graphs P(n,2). Bulletin of the Korean Mathematical Society, 50, 2021-2026.
https://doi.org/10.4134/BKMS.2013.50.6.2021
[14] Sakamoto, Y. (2019) Hamilton Cycles in Double Generalized Petersen Graphs. Discussiones Mathematicae Graph Theory, 39, 117-123.
https://doi.org/10.7151/dmgt.2062