Pure Mathematics
Vol.
11
No.
03
(
2021
), Article ID:
41029
,
6
pages
10.12677/PM.2021.113041
特殊图类的符号罗马控制数
马艺晓*,红霞#
洛阳师范学院数学科学学院,河南 洛阳
收稿日期:2021年2月11日;录用日期:2021年3月11日;发布日期:2021年3月18日
摘要
设图 为一个简单无向图,若 ,则记 。若实值函数 满足以下两个条件:(i) 对于任意的顶点 ,均有 成立;(ii) 如果对任意的顶点 ,若 ,则存在一个与v相邻的顶点 满足 ,则称该函数为图G的符号罗马控制函数。图G的符号罗马控制数定义为 。本文利用构造法及穷标法主要得到了特殊图类 的符号罗马控制数的精确值。
关键词
符号罗马控制函数,符号罗马控制数,图
The Signed Roman Domination Number of a Special Graph
Yixiao Ma*, Xia Hong#
School of Mathematical Sciences, Luoyang Normal University, Luoyang Henan
Received: Feb. 11th, 2021; accepted: Mar. 11th, 2021; published: Mar. 18th, 2021
ABSTRACT
Let be a simple undirected graph and denotes for . A signed Roman domination function satisfying the conditions that (i) for any , and (ii) every vertex v for which is adjacent to a vertex u for which is . The signed Roman domination number of G is . In this paper, we determine exact values of the signed Roman domination number of a special graph by constructive method and exhaustive method.
Keywords:Signed Roman Domination Function, Signed Roman Domination Number, Graph
Copyright © 2021 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文所涉及到的图均为无向简单图,且文中没有说明的术语和符号见 [1]。
设 是一个简单图,用 和 表示顶点集和边集。对 ,记 和 为u点在G中的邻域和闭邻域,用 表示u点在G中的度,而用 和 分别表示图G的最小度和最大度。把 ,,, 分别简单记为 ,,,。用 表示n阶圈图。
近几十年来,国内外很多学者越来越投入研究图的控制理论中的问题,如今其研究内容越来越丰富。第一次提出的符号控制数概念是在1995年 [2],通过几十年的发展,到目前为止已经繁衍出了各种形式的符号控制 [3] - [8]。符号罗马控制数的研究主要集中在研究其上下界 [9] 以及对特殊图的研究。Zhao [10] 等人得到了特殊图完全二部图、轮图的符号(全)罗马控制数。尹凯 [11] 等人把完全二部图的符号罗马控制数的结果推广到了完全多部图上。本文中主要计算出了图 的符号罗马控制数的精确值。
对于图 ,定义一个函数 和G的一个子集 ,记 。下文中,为简单起见,记 表示所有标号为i的顶点集合,其中 。对于 ,把 简单记为 。
2. 基本概念
定义1 [9] 设图 为一个图,若 ,则记 。若 满足:(i) 对于任意的顶点 ,均有 成立;(ii) 如果对任意的顶点 ,若 ,则存在一个与v相邻的顶点 满足 ,则称该函数为图G的符号罗马控制函数。图G的符号罗马控制数定义为 。若符号罗马控制函数f满足 ,则称函数f为图G的 -函数。
定义2 图 表示恰有一个公共点的两个圈的拷贝。
引理1 [9] 对 时,有 。
从引理1容易看出下面的注释。
注释:对于圈 , 达到最小仅当 上某连续3k个顶点中每3个点标号之和至少为2 (事实上,恰好为2)且剩下点标号至少为1 (如果有的话)。
3. 主要结果
定理 设 ,则
证明:设 ,,其中
。
。
。
设f是图G的一个最小符号罗马控制函数,则 。不难看出,当 时, ;当 时, 。下面只考虑 时的情况。
情况1 当 且 时,由注释以及定义1,有
另一方面,通过给出一个符号罗马控制函数 来证明上界。令
,
容易验证,对于任意顶点 ,有 。从而图G中有
,,,
故,有
。
综上所述,有
。
情况2 当 且 时
情况2.1 当 时, 中至少有一个标号为+2,剩余的只能标+1 (若有一个标−1,不妨设 ,则 ,与定义1矛盾),并且有 。故,有 。由注释以及定义1,有
情况2.2当 时,由注释以及定义1,有
情况2.3 当 时,由注释以及定义1,有
综上所述,有
。
另一方面,通过给出一个符号罗马控制函数 来证明上界。令
,
容易验证,对于任意顶点 ,有 。从而图G中有
,,,
故,有
。
综上所述,有
。
情况3 当 且 时,由注释,定义1以及引理1,有
另一方面,通过给出一个符号罗马控制函数 来证明上界。令
,
容易验证,对于任意顶点 ,有 。从而图G中有
,,,
故,有
。
综上所述,有
。
定理证毕。
基金项目
国家自然科学基金(No. 11701257);校级教改项目(No. 2020xjgj016,No. 2019xjjj002);河南省高校青年骨干教师培训计划(No. 2020GGJS194,No. 2019GGJS202);洛阳师范学院青年骨干教师培训计划(2019XJGGJS-10) (2020-JSJYYB-053)。
文章引用
马艺晓,红 霞. 特殊图类的符号罗马控制数
The Signed Roman Domination Number of a Special Graph[J]. 理论数学, 2021, 11(03): 313-318. https://doi.org/10.12677/PM.2021.113041
参考文献
- 1. Bondy, J.A. and Murty, U.S.R. (1977) Graph Theory with Applications. Macmillan, London.
- 2. Dunbar, J.E., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (1995) Signed Domination in Graphs. Combinatorics, Graph Theory, Applications, 311-322.
- 3. 徐保根. 图的控制理论[M]. 北京: 科学出版社, 2008.
- 4. Henning, M.A. (2004) Signed Total Domination in Graphs. Discrete Mathematics, 278, 109-125. https://doi.org/10.1016/j.disc.2003.06.002
- 5. Xu, B.G. (2009) On Signed Cycle Domination in Graphs. Discrete Mathematics, 309, 1007-1012. https://doi.org/10.1016/j.disc.2008.01.007
- 6. 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
- 7. Abdollahzadeh Ahangar, H., Amjadi, J., Sheikholeslami, S.M., Volkmann, L. and Zhao, Y. (2016) Signed Roman Edge Domination Numbers in Graphs. Journal of Combinatorial Optimization, 31, 333-346. https://doi.org/10.1007/s10878-014-9747-8
- 8. 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
- 9. Abdollahzadeh Ahangar, H., Henning, M.A., Löwenstein, C., Zhao, Y.C. and Samodivkin, V. (2014) Signed Roman Domination in Graphs. Journal of Combinatorial Optimization, 27, 241-255. https://doi.org/10.1007/s10878-012-9500-0
- 10. Zhao, Y.C. and Miao, L.Y. (2017) Signed Roman (Total) Dom-ination Numbers of Complete Bipartite Graphs and Wheels. Communications in Mathematical Research, 33, 318-326.
- 11. 尹凯, 陈学刚. 完全多部图的符号罗马控制数[J]. 汕头大学学报, 2017, 31(4): 25-34.
NOTES
*第一作者。
#通讯作者。