Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Roman dominating function

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

A characterization of roman trees

100%

Henning M.

Discussiones Mathematicae Graph Theory

2002

tom 22

nr 2

325-334

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.

The Distance Roman Domination Numbers of Graphs

80%

Aram H., Norouzian S., Sheikholeslami S. M.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 4

717-730

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-distance Roman dominating function on G is a labeling f : V (G) → {0, 1, 2} such that for every vertex with label 0, there is a vertex with label 2 at distance at most k from each other. The weight of a k-distance Roman dominating function f is the value w(f) =∑v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γkR (D), equals the minimum weight of a k-distance Roman dominating function on G. Note that the 1-distance Roman domination number γ1R (G) is the usual Roman domination number γR(G). In this paper, we investigate properties of the k-distance Roman domination number. In particular, we prove that for any connected graph G of order n ≥ k +2, γkR (G) ≤ 4n/(2k +3) and we characterize all graphs that achieve this bound. Some of our results extend these ones given by Cockayne et al. in 2004 and Chambers et al. in 2009 for the Roman domination number.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Aram H.

1 Henning M.

1 Norouzian S.

1 Sheikholeslami S. M.

1 2013

1 2002

Wyniki wyszukiwania

A characterization of roman trees

The Distance Roman Domination Numbers of Graphs