A characterization relating domination, semitotal domination and total Roman domination in trees

Document Type : Original paper

Authors

1 Universitat Rovira i Virgili, Tarragona, Spain

2 Departamento de Matemática, Universidad de Oriente, Cuba

Abstract

A total Roman dominating function on a graph $G$ is a function $f: V(G) \rightarrow \{0,1,2\}$ such that for every vertex $v\in V(G)$ with $f(v)=0$ there exists a vertex $u\in V(G)$ adjacent to $v$ with $f(u)=2$, and the subgraph induced by the set $\{x\in V(G): f(x)\geq 1\}$ has no isolated vertices. The total Roman domination number of $G$, denoted $\gamma_{tR}(G)$, is the minimum weight $\omega(f)=\sum_{v\in V(G)}f(v)$ among all total Roman dominating functions $f$ on $G$. It is known that $\gamma_{tR}(G)\geq \gamma_{t2}(G)+\gamma(G)$ for any graph $G$ with neither isolated vertex nor components isomorphic to $K_2$, where $\gamma_{t2}(G)$ and $\gamma(G)$ represent the semitotal domination number and the classical domination number, respectively. In this paper we give a constructive characterization of the trees that satisfy the equality above.

Keywords

Main Subjects

References

[1] 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.
[2] J. Amjadi, Total Roman domination subdivision number in graphs, Commun. Comb. Optim. 5 (2020), no. 2, 157–168.
[3] J. Amjadi, S. M. Sheikholeslami, and M. Soroudi, On the total Roman domination in trees, Discuss. Math. Graph Theory 39 (2019), no. 2, 519–532.
[4] A. Cabrera Martínez, S. Cabrera García, and A. Carrión García, Further results on the total Roman domination in graphs, Mathematics 8 (2020), no. 3, 349.
[5] A. Cabrera Martínez, S. Cabrera García, A. Carrión García, and F.A. Hernández Mira, Total Roman domination number of rooted product graphs, Mathematics 8 (2020), no. 10, 1850.
[6] A. Cabrera Martínez, D. Kuziak, I. Peterin, and I.G. Yero, Dominating the direct product of two graphs through total Roman strategies, Mathematics 8 (2020), no. 9, 1438.
[7] N. Campanelli and D. Kuziak, Total Roman domination in the lexicographic product of graphs, Discrete Appl. Math. 263 (2019), 88–95.
[8] W. Goddard, M.A. Henning, and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014), 67–81.
[9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Volume 2: Advanced Topics, Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998.
[10] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998.
[11] M.A. Henning and A.J. Marcon, Semitotal domination in claw-free cubic graphs, Ann. Comb. 20 (2016), no. 4, 799–813.
[12] M.A. Henning and A.J. Marcon, Vertices contained in all or in no minimum semitotal dominating set of a tree, Discuss. Math. Graph Theory 36 (2016), no. 1, 71–93.
[13] C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), no. 3, 608–619.
Communications in Combinatorics and Optimization
Volume 6, Issue 2
December 2021
Pages 197-209

Files

Share

How to cite

Statistics