Advances in Applied Mathematics
Vol.
07
No.
12
(
2018
), Article ID:
27994
,
6
pages
10.12677/AAM.2018.712180
Signed Total Domination Number of Graphs
Xia Hong, Feng Gao, Caihuan Zhang, Chunyan Wei
Department of Mathematics, Luoyang Normal University, Luoyang Henan
Received: Nov. 16th, 2018; accepted: Dec. 6th, 2018; published: Dec. 13th, 2018
ABSTRACT
Let be a graph and denotes for . A function is said to be a signed total domination function (STDF), if for . The signed total domination number is . In this paper, a lower bound of the signed total domination number are obtained and we determine a exact value of signed total domination number of two classes graphs generalized Petesen graph and Double generalized Petesen graph by exhaustived method and classified discussion, where .
Keywords:Signed Total Domination Function, Signed Total Domination Number, Generalized Petesen Graph , Double Generalized Petesen Graph
图的符号全控制数
红霞,高峰,张彩环,魏春艳
洛阳师范学院数学科学学院,河南 洛阳
收稿日期:2018年11月16日;录用日期:2018年12月6日;发布日期:2018年12月13日
摘 要
设图 为一个图,一个双值函数 ,若 ,则记 。如果对任意的顶点 ,均有 成立,则称f为图G的一个符号全控制函数。图G的符号全控制数定义为 。本文首先给出一般图的符号全控制数的下界,然后用分类讨论和穷标法得到了两类图广义Petesen图 和Double广义Petesen图 的符号全控制数的精确值,这里 。
关键词 :符号全控制函数,符号全控制数,广义Petesen图 ,Double广义Petesen图
Copyright © 2018 by authors and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文所指定的图均为无向简单图,文中未说明的符号和术语同文献 [1] 。设 是一个图,其顶点集 和边集 。对任意 ,则 表示为u点在G中的领域, 为u点在G中的闭领域, 为u点在G中的度,而 和 分别为图G的最小度和最大度。在不致混淆情况下,可将 分别简单记为 。图G中两个顶点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图 和Double广义Petesen图 的符号全控制数的精确值,这里 。
对于图 ,定义一个函数 和G的一个子集 ,记 。为简单起见,下文中适合 的顶点称为+1点,适合 的顶点称为-1点,用 表示模n的剩余类。
2. 基本概念
定义1 [6] :设图 为一个图,一个双值函数 ,若 ,则记 。
如果对任意的顶点 ,均有 成立,则称f为图G的一个符号全控制函数,图G的符号全控制数定义为 并将使得 的符号全控制函数称f为图G的一个最小符号全控制函数。
从定义1可以看出以下性质。
性质:设G是 个顶点的简单图。若 是图G一个最小符号全控制函数,则有以下结论成立。
i)
ii)
定义2 [5] :设 都是正整数且 。广义Petersen图 是具有2n个顶点的图,它的顶点集 和边集 分别为:
定义3 [14] :设n和k是正整数且 。Double广义Petesen图 是4n个顶点的简单图,它的顶点集 和边集 分别为:
显然,广义Petersen图 和Double广义Petesen图 都是3-正则图。
引理 [6] :设G是一个r-正则图。若r是奇数,则 ;若r是偶数,则 。
3. 主要定理及其证明
定理1:设图G是 个顶点的简单图。若 是图G一个最小符号全控制函数,且 , ,则有以下结论成立。
i) ;
ii) ;
iii) ;
证明:i) 假设 是图G一个最小符号全控制函数,由性质,有
从而有
ii) 由性质和i),推导出
通过移项,得
iii) 由性质和i),有
故,有
推论:设G是一个r-正则图,那么有 。
注:定理1的结果与引理的结论一致。
定理2:设图G是广义Petersen图 且 。那么
证明:令图G是广义Petersen图 ,这里 。记
因此,有
由定理1,有
下面我们定义图G的一个符号全控制数f:
这里
容易验证,对于每个顶点 ,有 。注意到此时图G中-1点个数t为 ,+1点个数s为 。从而
因此,有
定理2:证毕。
定理3:设图G是Double广义Petesen图 且 。那么
证明:令图G是Double广义Petesen图 ,这里 。记
因此,有
由定理1,有
下面我们定义图G的一个符号全控制数f:
这里
容易验证,对于每个顶点 ,有 。注意到此时图G中-1点个数t为 ,+1点个数s为 。从而
因此,有
定理3证毕。
基金项目
国家自然科学基金(No. 11701257, No.11801253, No. 11571005),河南省教育厅高校重点项目(No. 18A110025, No. 18A110026)、河南省科技计划项目(182102310930, 182102310955)、(2017-JSJYYB-074)。
文章引用
红 霞,高 峰,张彩环,魏春艳. 图的符号全控制数
Signed Total Domination Number of Graphs[J]. 应用数学进展, 2018, 07(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