Total Roman domination for proper interval graphs
Abstract
A function f:V → {0,1,2} is a total Roman dominating function (TRDF) on a graph G=(V,E) if for every vertex v ∈ V with f(v) = 0 there is a vertex u adjacent to v with f(u) = 2 and for every vertex v ∈ V with f(v) > 0 there exists a vertex u ∈ NG(v) with f(u) > 0. The weight of a total Roman dominating function f on G is equal to f(V)=Σv ∈ Vf(v). The minimum weight of a total Roman dominating function on G is called the total Roman domination number of G. In this paper, we give an algorithm to compute the total Roman domination number of a given proper interval graph G=(V,E) in O(|V|) time.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.2.16
References
H. Abdollahzadeh Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016), 501–517.
M.H. Akhbari and N. Jafari Rad, Bounds on weak and strong total domination number in graphs, Electron. J. Graph Theory Appl. 4 (2016), 111–118.
J. Amjadi, S. Nazari-Moghaddam, S.M. Sheikholeslami and L. Volkmann, Total Roman domination number of trees, Australas. J. Combin. 69 (2017), 271–285.
[J. Amjadi, S.M. Sheikholeslami and M. Soroudi, Nordhaus-Gaddum bounds for total Roman domination, J. Comb. Optim. 35 (2018), 126–133.
J. Amjadi, S.M. Sheikholeslami and M. Soroudi, On the total Roman domination in trees Discuss. Math. Graph Theory 39 (2019), 519–532.
T. Araki and H. Miyazaki, Secure domination in proper interval graphs, Discrete Appl. Math. 247 (2018), 70–76.
A. Braga, C.C. de Souza and O. Lee. The eternal dominating set problem for proper interval graphs, Inform. Process. Lett. 115 (2015), 582–587.
N. Chiarelli, T.R. Hartinger, V.A. Leoni, M.I.L. Pujato and M. Milaniˇc, New algorithms for weighted k-domination and total k-domination problems in proper interval graphs, Theoret. Comput. Sci. 795 (2019), 128–141.
N. Jafari Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5 (2017), 1–6.
N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019), 41–53.
C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), 608–619.
P.J. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Comput. Math. Appl. 25 (1993), 15–25.
B.S. Panda and S. Paul, A linear time algorithm for liar’s domination problem in proper interval graphs, Inform. Process. Lett. 113 (2013), 815–822.
C.S. Revelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy. Amer. Math. Monthly 107 (2000), 585–594.
I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), 136–139.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.