A characterization of roman trees
Michael A. Henning
Discussiones Mathematicae Graph Theory, Tome 22 (2002), p. 325-334 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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∈Vf(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.

Publié le : 2002-01-01
EUDML-ID : urn:eudml:doc:270477 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1178,
     author = {Michael A. Henning},
     title = {A characterization of roman trees},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {22},
     year = {2002},
     pages = {325-334},
     zbl = {1030.05093},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1178}
}

Michael A. Henning. A characterization of roman trees. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 325-334. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1178/

[000] [1] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, manuscript. | Zbl 1036.05034

[001] [2] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi and A. McRae, Roman domination in graphs II, manuscript. | Zbl 1036.05034

[002] [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998). | Zbl 0890.05002

[003] [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, Inc. New York, 1998). | Zbl 0883.00011

[004] [5] S.T. Hedetniemi, Defending the Roman Empire, principal talk presented at the Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms, and Applications (Western Michigan University, Kalamazoo, USA, June 2000).

[005] [6] I. Stewart, Defend the Roman Empire!, Scientific American, December 1999, 136-138, doi: 10.1038/scientificamerican1299-136.