Discussiones Mathematicae Graph Theory · 2018 · 19 citations · 14 references
Natural SciencesMathematicsCombinatoricsGraph VisualizationSeparation Of PowersDominance HierarchiesGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsDominating SetsF-functionLower Bounds
A total Roman dominating function on a graph G is a function f : V (G) {0, 1, 2} satisfying the following conditions: (i) every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which 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 (G)) = uV (G) f (u). The total Roman domination number tR (G) is the minimum weight of a total Roman dominating function of G. Ahangar et al. in [H.A. Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016) 501-517] recently showed that for any graph G without isolated vertices, 2(G) tR (G) 3(G), where (G) is the domination number of G, and they raised the problem of characterizing the graphs G achieving these upper and lower bounds. In this paper, we provide a constructive characterization of these trees.
14
E. J. Cockayne, Paul Dreyer, Sandra M. Hedetniemi et al. · Discrete Mathematics · 2003 · 556 citations
Ian Stewart · Scientific American · 1999 · 359 citations
Humanities, Classics, History +8
Robert A. Beeler, Teresa W. Haynes, Stephen T. Hedetniemi · Discrete Applied Mathematics · 2016 · 188 citations