PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2002 | 22 | 2 | 325-334
Tytuł artykułu

A characterization of roman trees

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
22
Numer
2
Strony
325-334
Opis fizyczny
Daty
wydano
2002
otrzymano
2001-05-12
poprawiono
2002-04-25
Twórcy
  • School of Mathematics, Statistics, &, Information Technology, University of Natal, Private Bag X01, Pietermaritzburg, 3209 South Africa
Bibliografia
  • [1] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, manuscript.
  • [2] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi and A. McRae, Roman domination in graphs II, manuscript.
  • [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998).
  • [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, Inc. New York, 1998).
  • [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] I. Stewart, Defend the Roman Empire!, Scientific American, December 1999, 136-138, doi: 10.1038/scientificamerican1299-136.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1178
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.