|
Pure Mathematics 2023
区间图Total-罗马控制性质研究
|
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.
[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. |