Total Roman domination and $2$-independence in trees

Document Type : Research Paper

Authors

1 Department of Mathematics Babol Noshirvani University of Technology Shariati Ave., Babol, Iran

2 Department of Mathematics Azarbaijan Shahid Madani University Tabriz, Iran

Abstract

Let $G=(V, E)$ be a simple graph with vertex set $V$ and edge set $E$. A {\em total Roman dominating function} on a graph $G$ is a function $f:V\rightarrow \{0,1,2\}$ satisfying the following conditions: (i) every vertex $u$ {\color{blue}such that} $f(u)=0$ is adjacent to at least one vertex $v$ {\color{blue}such that} $f(v)=2$ and (ii) the subgraph of $G$ induced by the set of all vertices of positive weight has no isolated vertex. The weight of a total Roman dominating function $f$ is the value, $f(V)=\Sigma_{u\in V(G)}f(u)$. The {\em total Roman domination number} $\gamma_{tR}(G)$ of $G$ is the minimum weight of a total Roman dominating function of $G$. A subset $S$ of $V$ is a $2$-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S$. The maximum cardinality of a $2$-independent set of $G$ is the $2$-independence number $\beta_2(G)$. These two parameters are incomparable in general, however, we show that if $T$ is a tree, then $\gamma_{tR}(T)\le \frac{3}{2}\beta_2(T)$ and we characterize all trees attaining the equality.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, Trees with total Roman domination number equal to Roman domination number plus its domination number: complexity and structural properties, AKCE Int. J. Graphs and Combin., 19 (2022) 74–78.
[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] H. Abdollahzadeh Ahangar, J. Amjadi, S. M. Sheikholeslami and M. Soroudi, On the total Roman domi-nation number of graphs, Ars Combin., 150 (2020) 225–240.
[4] J. Amjadi, N. Dehgardi, S. M. Sheikholeslami and M. Valinavaz, Independent Roman domination and 2-independence in trees, Discrete Math. Algorithms Appl., 10 (2018) 10 pp.
[5] J. Amjadi, S. Nazari-Moghaddam, S. M. Sheikholeslami and L. Volkmann, Total Roman domination number of trees, Australas. J. Combin., 69 (2017) 271–285.
[6] J. Amjadi, S. M. Sheikholeslami and M. Soroudi, Nordhaus–Gaddum bounds for total Roman domination, J. Comb. Optim., 35 (2018) 126–133.
[7] J. Amjadi, S.M. Sheikholeslami and M. Soroudi, On the total Roman domination in trees, Discuss. Math. Graph Theory, 39 (2019) 519–532.
[8] J. Amjadi and M. Soroudi, Twin signed total Roman domination numbers in digraphs, Asian-European J. Math., 11 (2018) 22 pp.
[9] F. Bonomo, B. Brešar, L. Grippo, M. Milanič and M. Safe, Domination parameters with number 2: inter-relations and algorithmic consequences, Discrete Appl. Math., 235 (2018) 23–50.
[10] E. W. Chambers, B. Kinnersley, N. Prince and D. B. West, Extremal problems for Roman domination, SIAM J. Discrete Math., 23 (2009) 1575–1586.
[11] M. Chellali and N. Meddah, Trees with equal 2-domination and 2-independence numbers, Discuss. Math. Graph Theory., 32 (2012) 263–270.
[12] M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-domination and k-independence in graphs: a survey, Graphs Combin., 28 (2012) 1–55.
[13] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math., 278 (2004) 11–22.
[14] N. Dehgardi, Mixed Roman domination and 2-independence in trees, Commun. Comb. Optim., 3 (2018) 79–91.
[15] O. Favaron, On a conjecture of Fink and Jacobson concerning k-domination and k-dependence, J. Combin. Theory Ser., 39 (1985) 101–102.
[16] O. Favaron, H. Karami, R. Khoeilar and S. M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math., 309 (2009) 3447–3451.
[17] J. F. Fink and M. S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, Graph theory with applications to algorithms and computer science (Kalamazoo, Mich., 1984), Wiley-Intersci. Publ., Wiley, New York, 1985 301–311.
[18] T. W. Haynes, S.T. Hedetniemi and P. J. Slater (Eds.), Fundamentals of domination in graphs, Monographs and Textbooks in Pure and Applied Mathematics, 208, Marcel Dekker, Inc., New York, 1998.
[19] T. W. Haynes, S. T. Hedetniemi and P. J. Slater (Eds.), Domination in graphs: advanced topics, Marcel Dekker, Inc. New York, 1998.
[20] M. A. Henning, Recent results on total domination in graphs: A survey, Discrete Math., 309 (2009) 32–63.
[21] M. A. Henning and A. Yeo, Total domination in graphs, (Springer Monographs in Mathematics) (2013).
[22] M. S. Jacobson, K. Peters and D. F. Rall, On n-irredundance and n-domination, Ars. Combin., 29 (1990) 151–160.
[23] C.-H. Liu and G. J. Chang,Roman domination on strongly chordal graphs, J. Comb. Optim., 26 (2013) 608–619.
[24] N. Meddah and M. Chellali, Roman domination and 2-independence in trees, Discrete Math. Algorithms Appl., 9 (2017) 6 pp.
[25] C. S. ReVelle and K. E. Rosing, Defendens imperium romanum: A classical problem in military strategy, Amer. Math. Monthly, 107 (2000) 585–594.
[26] I. Stewart, Defend the Roman empire!, Sci. Amer., 281 (1999) 136–139.
[27] I. G. Yero, On Clark and Suen bound-type results for k-domination and Roman domination of Cartesian product graphs, Int. J. Comput. Math., 90 (2013) 522–526.
Transactions on Combinatorics
Volume 13, Issue 3 - Serial Number 3
September 2024
Pages 213-223

Files

History

  • Receive Date: 21 July 2022
  • Revise Date: 31 May 2023
  • Accept Date: 08 June 2023
  • Published Online: 01 September 2024

Share

How to cite

Statistics