A characterization of roman trees

Michael A. Henning

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 2, page 325-334
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Michael A. Henning. "A characterization of roman trees." Discussiones Mathematicae Graph Theory 22.2 (2002): 325-334. <http://eudml.org/doc/270477>.

@article{MichaelA2002,
abstract = {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.},
author = {Michael A. Henning},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominating set; Roman dominating function; dominating sets; Roman domination number; domination number; Roman graphs},
language = {eng},
number = {2},
pages = {325-334},
title = {A characterization of roman trees},
url = {http://eudml.org/doc/270477},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Michael A. Henning
TI - A characterization of roman trees
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 2
SP - 325
EP - 334
AB - 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.
LA - eng
KW - dominating set; Roman dominating function; dominating sets; Roman domination number; domination number; Roman graphs
UR - http://eudml.org/doc/270477
ER -

References

top
  1. [1] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, manuscript. Zbl1036.05034
  2. [2] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi and A. McRae, Roman domination in graphs II, manuscript. Zbl1036.05034
  3. [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998). Zbl0890.05002
  4. [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, Inc. New York, 1998). Zbl0883.00011
  5. [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). 
  6. [6] I. Stewart, Defend the Roman Empire!, Scientific American, December 1999, 136-138, doi: 10.1038/scientificamerican1299-136. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.