Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 7

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A characterization of roman trees

100%
Henning M.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
325-334
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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graphs with large double domination numbers

100%
Henning M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
13-28
EN
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{×2}(G)$. If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that $γ_{×2}(G) ≤ 3n/4$ and we characterize those graphs achieving equality.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Trees with unique minimum total dominating sets

64%
Haynes T., Henning M.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
233-246
EN
A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On double domination in graphs

64%
Harant J., Henning M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
29-34
EN
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{×2}(G)$. A function f(p) is defined, and it is shown that $γ_{×2}(G) = min f(p)$, where the minimum is taken over the n-dimensional cube $Cⁿ = {p = (p₁,...,pₙ) | p_i ∈ IR, 0 ≤ p_i ≤ 1,i = 1,...,n}$. Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then $γ_{×2}(G) ≤ ((ln(1+d) + lnδ + 1)/δ)n$.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total domination subdivision numbers of graphs

51%
Haynes T., Henning M., Hopkins L.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
457-467
EN
A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. The total domination subdivision number of G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. First we establish bounds on the total domination subdivision number for some families of graphs. Then we show that the total domination subdivision number of a graph can be arbitrarily large.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Partitioning a graph into a dominating set, a total dominating set, and something else

51%
Henning M., Löwenstein C., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
563-574
EN
A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Algorithmic aspects of total-subdomination in graphs

51%
Harris L., Hattingh J., Henning M.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
5-18
EN
Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → {-1,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total k-subdomination number of a tree and also show that the associated decision problem is NP-complete for general graphs.
first rewind previous Strona / 1 next fast forward last
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ć.