×

Defending the Roman Empire—a new strategy. (English) Zbl 1024.05068

Let \(G= (V,E)\) be a graph and let \(f\) be a function \(f: V\to \{0,1,2\}\). A vertex \(u\) with \(f(u)= 0\) is undefended with respect to \(f\) if it is not adjacent to a vertex of positive weight. A function \(f\) is a weak Roman domination function if each \(u\in V\) with \(f(u)= 0\) is adjacent to a vertex \(v\) with \(f(v)> 0\) such that the function \(f': V\to\{0,1,2\}\) defined by \(f'(u)= 1\), \(f'(v)= f(v)- 1\) and \(f'(w)= f(w)\), \(w\in V- \{u,v\}\) has no undefended vertex. The weight of \(f\) is \(w(f)= \sum_{v\in V} f(v)\). The weak Roman domination number \(\gamma_r(G)\) is the minimum weight of a weak Roman domination function of \(G\). It is proved that \(\gamma(G)\leq \gamma_r(G)\leq 2\gamma(G)\) for every graph \(G\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K.S. Booth, Dominating sets in chordal graphs, Research Report CS-80-34, University of Waterloo, 1980.; K.S. Booth, Dominating sets in chordal graphs, Research Report CS-80-34, University of Waterloo, 1980. · Zbl 0485.05055
[2] Booth, K. S.; Johnson, J. H., Dominating sets in chordal graphs, SIAM J. Comput., 11, 191-199 (1982) · Zbl 0485.05055
[3] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, manuscript.; E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, manuscript. · Zbl 1036.05034
[4] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, A. McRae, Roman domination in graphs II, manuscript.; E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, A. McRae, Roman domination in graphs II, manuscript. · Zbl 1036.05034
[5] A.K. Dewdney, Fast Turing reductions between problems in NP 4, Report 71, University of Western Ontario, 1981.; A.K. Dewdney, Fast Turing reductions between problems in NP 4, Report 71, University of Western Ontario, 1981.
[6] P. Dreyer, Defending the Roman Empire, Ph.D. Thesis, Rutgers University, New Brunswick, NJ, 2000.; P. Dreyer, Defending the Roman Empire, Ph.D. Thesis, Rutgers University, New Brunswick, NJ, 2000.
[7] Gunther, G.; Hartnell, B. L.; Markus, L.; Rall, D. F., Graphs with unique minimum dominating sets, Congr. Numer., 101, 55-63 (1994) · Zbl 0836.05045
[8] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.; T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998. · Zbl 0890.05002
[9] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, Inc. New York, 1998.; T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, Inc. New York, 1998. · Zbl 0883.00011
[10] Henning, M. A., A characterization of Roman trees, Discussiones Mathematicae Graph Theory, 22, 2, 225-234 (2002)
[11] I. Stewart, Defend the Roman Empire!, Scientific American, December 1999, pp. 136-138.; I. Stewart, Defend the Roman Empire!, Scientific American, December 1999, pp. 136-138.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.