Total Roman domination subdivision number in graphs

Document Type : Original paper

Author

Azarbaijan Shahid Madani University

Abstract

A Roman dominating function on a graph $G$ is a function $f:V(G)\rightarrow \{0,1,2\}$ satisfying the condition that every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ for which $f(v)=2$. A  total Roman dominating function is a Roman dominating function with the additional property that the subgraph of $G$ induced by the set of all vertices of positive weight has no isolated vertices. The weight of a total Roman dominating function $f$ is the value $\Sigma_{u\in V(G)}f(u)$. The  total Roman domination number of $G$, $\gamma_{tR}(G)$, is the minimum weight of a total Roman dominating function on $G$. The  total Roman domination subdivision number ${\rm sd}_{\gamma_{tR}}(G)$ of a graph $G$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the total Roman domination number. In this paper, we initiate the study of total Roman domination subdivision number in graphs and we present sharp bounds for this parameter. 

Keywords

References

[1] H. Abdollahzadeh Ahangar, J. Amjadi, , S.M. Sheikholeslami, and M. Soroudi, Bounds on the total Roman domination number of graphs, Ars Combin. (to appear).
[2] 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.
[3] J. Amjadi, S. Nazari-Moghaddam, S.M. Sheikholeslami, and L. Volkmann, Total Roman domination number of trees, Australas. J. Combin. 69 (2017), 271–285.
[4] J. Amjadi, S.M. Sheikholeslami, and M. Soroudi, Nordhaus–gaddum bounds for total Roman domination, J. Comb. Optim. 35 (2018), no. 1, 126–133.
[5] H. Aram, O. Favaron, and S.M. Sheikholeslami, Domination subdivision numbers of trees, Discrete Math. 309 (2009), no. 4, 622–628.
[6] M. Atapour, A. Hansberg, A. Khodkar, S.M. Sheikholeslami, and L. Volkmann, 2-domination subdivision number of graphs, AKCE Int. J. Graphs. Combin. 5 (2008), no. 2, 165–173.
[7] M. Atapour, S.M. Sheikholeslami, and A. Khodkar, Roman domination subdivision number of graphs, Aequationes Math. 78 (2009), no. 3, 237–245.
[8] M. Atapour, S.M. Sheikholeslami, Trees whose Roman domination subdivision number is 2, Util. Math. 82 (2010), 227–240.
[9] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[10] N. Dehgardi, S.M. Sheikholeslami, and L. Volkmann, The rainbow domination subdivision numbers of graphs, Mat. Vesnik 67 (2015), no. 2, 102–114.
[11] M. Dettlaff, S. Kosary, M. Lemańska, and S.M. Sheikholeslami, Weakly convex domination subdivision number of a graph, Filomat 30 (2016), no. 8, 2101–2110.
[12] M. Dettlaff, M. Lemańska, S. Kosary, and S.M. Sheikholeslami, The convex domination subdivision number of a graph, Commun. Comb. Optim. 1 (2016), no. 1, 43–56.
[13] M. Falahat, S.M. Sheikholeslami, and L. Volkmann, New bounds on the rainbow domination subdivision number, Filomat 28 (2014), no. 3, 615–622.
[14] O. Favaron, H. Karami, and S.M. Sheikholeslami, Connected domination subdivision numbers of graphs, Util. Math. 77 (2008), 101–111.
[15] O. Favaron, H. Karami, and S.M. Sheikholeslami, Total domination and total domination subdivision number of a graph and its complement, Discrete Math. 308 (2008), no. 17, 4018–4023.
[16] O. Favaron, H. Karami, and S.M. Sheikholeslami, Bounding the total domination subdivision number of a graph in terms of its order, J. Comb. Optim. 21 (2011), no. 2, 209–218.
[17] J.F. Fink, M.S. Jacobson, L.F. Kinch, and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990), no. 1-3, 47–57.
[18] T.W. Haynes, S.T. Hedetniemi, S.T. Hedetniemi, D. Jacobs, J. Knisely, and L. van der Merwe, Domination subdivision numbers, Discuss. Math. Graph Theory 21 (2001), no. 2, 239–253.
[19] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs, Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[20] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York,
1998.
[21] T.W. Haynes, M.A. Henning, and L. Hopkins, Total domination subdivision numbers of graphs, Discuss. Math. Graph Theory 24 (2004), no. 3, 457–467.
[22] T.W. Haynes, M.A. Henning, and L. Hopkins, Total domination subdivision numbers of graphs, Discuss. Math. Graph
Theory 24 (2004), no. 3, 457–467.
[23] M.A. Henning and A. Yeo, Total domination in graphs, Springer, 2013.
[24] J. Kok and C.M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79 (1990), 225–231.
[25] C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), no. 3, 608–619.
[26] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
[27] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138.
[28] S. Velammal, Studies in graph theory: Covering, independence, domination and related topics, (1997).
 
Communications in Combinatorics and Optimization
Volume 5, Issue 2
December 2020
Pages 157-168

Files

Share

How to cite

Statistics