全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

区间图Total-罗马控制性质研究
Total-Roman Domination Property on Interval Graphs

DOI: 10.12677/PM.2023.1312365, PP. 3505-3513

Keywords: 区间图,Total-罗马控制函数,团,路径
Interval Graph
, Total-Roman Domination Function, Clique, Path

Full-Text   Cite this paper   Add to My Lib

Abstract:

Total-罗马控制函数是函数f:V(G)→{0,1,2},满足条件:1) 对G中任意函数值f(u)=0的顶点u,至少存在一个邻居v使得函数值f(v)=2;2) 由控制集{k|f(k)≥1且k∈V(G)}诱导的子图没有孤立点存在。结合3阶及以上区间图,本文主要探索了基于total-罗马对的定理,研究了团和路径的不同结合图类中total-罗马控制数等内容,以示例辅助理解,证明了任意阶团的total-罗马控制数为3、相交团的并的total-罗马控制数不超过4等性质。
Total-Roman Domination Function is the function f:V(G)→{0,1,2}, which satisfies the following two conditions: 1) for any vertex u with f(u)=0, there is at least one neighbor v with f(v)=2;2) No outliers exist for a subgraph induced by a control set {k|f(k)≥1 and k∈V(G)}. Combined with interval graphs of order 3 and above, this paper mainly explores the Total-Roman control number based on the theorem of Total-Roman pairs, studies the Total-Roman control number of different associative graph classes of groups and paths, and proves that the total-Roman control number of any order group is 3, and the Total-Roman control number of union of intersecting groups is not more than 4 and other properties.

References

[1]  原晋江, 康丽英. 单位区间图的一种刻划及其应用[J]. 石家庄铁道学院学报, 1994(2): 50-54.
[2]  林浩, 林澜. 区间图最小伸展支撑树问题的最优性刻画[J]. 运筹学学报, 2020, 24(4): 153-158.
[3]  周星宏, 李鹏, 王爱法, 等. 区间图最小连通支配集问题的最优算法[J]. 重庆理工大学学报(自然科学), 2023, 37(1): 309-314.
[4]  Stewart, I. (1999) Defend the Roman Empire. Scientific American, 281, 136-138.
https://doi.org/10.1038/scientificamerican1299-136
[5]  Michael, A.H. and Stephen, T.H. (2003) Defending the Roman Empire-A New Strategy. Discrete Mathematics, 266, 239-251.
https://doi.org/10.1016/S0012-365X(02)00811-7
[6]  Michael, A.H. (2003) Defending the Roman Empire from Multiple Attacks. Discrete Mathematics, 271, 101-115.
https://doi.org/10.1016/S0012-365X(03)00040-2
[7]  Liedloff, M., Kloks, T., Liu, J.P., et al. (2008) Efficient Algorithms for Roman Domination on Some Classes of Graphs. Discrete Applied Mathematics, 156, 3400-3415.
https://doi.org/10.1016/j.dam.2008.01.011
[8]  尚卫苹. 图的函数控制参数[D]: [硕士学位论文]. 郑州: 郑州大学, 2006.
[9]  陈越奋, 杨剑. 图的弱罗马控制[J]. 信阳师范学院学报(自然科学版), 2012, 25(1): 9-13+30.
[10]  宋晓新, 卞京召, 殷伟. 割边, 割点, 弱罗马控制和六个安全级别[J]. 河南大学学报(自然科学版), 2013, 43(5): 478-482.
[11]  张利贤. 图的参数控制研究[D]: [硕士学位论文]. 金华: 浙江师范大学, 2016.
[12]  Liu, C.H. and Chang, G.J. (2013) Roman Domination on Strongly Chordal Graphs. Journal of Combinatorial Optimization, 26, 608-619.
https://doi.org/10.1007/s10878-012-9482-y
[13]  Chambers, E.W., Kinnersley, B., Prince, N. and West, D.B. (2009) Extremal Problems for Roman Domination. SIAM Journal on Discrete Mathematics, 23, 1575-1586.
https://doi.org/10.1137/070699688
[14]  Cockayne, E.J., Dreyer Jr., P.A., Hedetniemic, S.M. and Hedetniemic, S.T. (2004) Roman Domination in Graphs. Discrete Mathematics, 278, 11-22.
https://doi.org/10.1016/j.disc.2003.06.004
[15]  杨洪, 张修军, 吴璞, 等. 求解区间图上的罗马控制数的动态规划算法[J]. 计算机应用研究, 2018, 35(7): 1986-1988.
[16]  Amjadi, J., Sheikholeslami, S.M. and Soroudi M. (2018) Nordhaus-Gaddum Bounds for Roman Domination. Journal of Combinatorial Optimization, 35, 126-133.
https://doi.org/10.1007/s10878-017-0158-5
[17]  Amjadi, J. (2020) Total Roman Domination Subdivision Number in Graphs. Communications in Combinatorics and Optimization, 5, 157-168.
[18]  李鹏. 区间图相关图类若干结构与算法问题[D]: [博士学位论文]. 上海: 上海交通大学, 2014.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133