Geodesic
A characterization of roman trees
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 2, pp. 325-334

Voir la notice de l'article provenant de la source Library of Science

A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is w(f) = ∑_v ∈ V f(v). The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number are called Roman graphs. At the Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms, and Applications held at Western Michigan University in June 2000, Stephen T. Hedetniemi in his principal talk entitled "Defending the Roman Empire" posed the open problem of characterizing the Roman trees. In this paper, we give a characterization of Roman trees.
Keywords: dominating set, Roman dominating function 
@article{DMGT_2002_22_2_a8,
     author = {Henning, Michael},
     title = {A characterization of roman trees},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {325--334},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a8/}
}
TY  - JOUR
AU  - Henning, Michael
TI  - A characterization of roman trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2002
SP  - 325
EP  - 334
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a8/
LA  - en
ID  - DMGT_2002_22_2_a8
ER  - 
%0 Journal Article
%A Henning, Michael
%T A characterization of roman trees
%J Discussiones Mathematicae. Graph Theory
%D 2002
%P 325-334
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a8/
%G en
%F DMGT_2002_22_2_a8
Henning, Michael. A characterization of roman trees. Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 2, pp. 325-334. http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a8/