Abstract
Given two real numbers \(b\ge a>0\), an (a, b)-Roman dominating function on a graph \(G=(V,E)\) is a function \(f:V\rightarrow \{0,a,b\}\) satisfying the condition that every vertex v for which \(f(v)=0\) is adjacent to a vertex u for which \(f(u)=b\). In the present paper, we design a linear-time algorithm to produce a minimum (a, b)-Roman dominating function for cacti, a superclass of trees and different from chordal graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Abdollahzadeh Ahangar, H., Henning, M.A., L\(\ddot{o}\)wenstein, C., Zhao, Y., Samodivkin, V.: Signed Roman domination in graphs J. Comb. Optim. 27(2), 241–255 (2014)
Atapour, M., Sheikholeslami, S.M., Volkmann, L.: Global Roman domination in trees. Graphs Comb. 31(4), 813–825 (2015)
Chellali, M., Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., McRae, A.A.: A Roman domination chain. Graphs Comb. 32(1), 79–92 (2016)
Cockayne, E.J., Dreyer Jr., P.A., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discrete Math. 278, 11–22 (2004)
Fernau, H.: Roman domination: a parameterized perspective. Int. J. Comput. Math. 85, 25–38 (2008)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)
Hedetniemi, S., Laskar, R., Pfaff, J.: A linear algorithm for finding a minimum dominating set in a cactus. Discrete Appl. Math. 13, 287–292 (1986)
Henning, M.A.: Defending the Roman Empire from multiple attacks. Discrete Math. 271, 101–115 (2003)
Henning, M.A., Hedetniemi, S.T.: Defending the Roman Empire-a new strategy. Discrete Math. 266, 239–251 (2003)
Liedloff, M., Kloks, T., Liu, J., Peng, S.L.: Efficient algorithms for Roman domination on some classes of graphs. Discrete Appl. Math. 156, 3400–3415 (2008)
Liu, C.H., Chang, G.J.: Roman domination on strongly chordal graphs. J. Comb. Optim. 26, 608–619 (2013)
Acknowledgements
This paper is partially supported by the Natural Science Foundation of Jiangsu Province (No. BK20151117), and the second author was supported by the Babol Noshirvani University of Technology under research grant number BNUT/385001/97.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhao, Y., Ahangar, H.A., Liao, Z., Chellali, M. (2019). (a, b)-Roman Domination on Cacti. In: Cao, BY., Zhong, YB. (eds) Fuzzy Sets and Operations Research. ICFIE 2017. Advances in Intelligent Systems and Computing, vol 872. Springer, Cham. https://doi.org/10.1007/978-3-030-02777-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-030-02777-3_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-02776-6
Online ISBN: 978-3-030-02777-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)