Total Roman domination and $2$-independence in trees

Abdollahzadeh Ahangar, Hossein; Soroudi, Marzieh; Amjadi, Jafar; Sheikholeslami, Seyed Mahmoud

doi:10.22108/toc.2023.134483.2005

تعداد نشریات	43
تعداد شماره‌ها	1,682
تعداد مقالات	13,758
تعداد مشاهده مقاله	32,167,946
تعداد دریافت فایل اصل مقاله	12,735,801

	Total Roman domination and $2$-independence in trees
Transactions on Combinatorics
مقاله 3، دوره 13، شماره 3، آذر 2024، صفحه 213-223 اصل مقاله (460.04 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2023.134483.2005
نویسندگان
Hossein Abdollahzadeh Ahangar^* ¹؛ Marzieh Soroudi²؛ Jafar Amjadi²؛ Seyed Mahmoud Sheikholeslami²
¹Department of Mathematics Babol Noshirvani University of Technology Shariati Ave., Babol, Iran
²Department of Mathematics Azarbaijan Shahid Madani University Tabriz, Iran
چکیده
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.
کلیدواژه‌ها
total Roman dominating function؛ total Roman domination number؛ $2$-independent set؛ $2$-independence number

مراجع
[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. Brešar, L. Grippo, M. Milanič 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.
آمار تعداد مشاهده مقاله: 146 تعداد دریافت فایل اصل مقاله: 229

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Total Roman domination and $2$-independence in trees