Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Algorithmic aspects of total-subdomination in graphs

100%

Harris L., Hattingh J., Henning M.

Discussiones Mathematicae Graph Theory

2006

tom 26

nr 1

5-18

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.

Restrained domination in unicyclic graphs

88%

Hattingh J., Joubert E., Loizeaux M., Plummer A., van der Merwe L.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 1

71-86

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_r(G)$, is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_r(U) ≥ ⎡n/3⎤$, and provide a characterization of graphs achieving this bound.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Hattingh J.

1 Harris L.

1 Henning M.

1 Joubert E.

1 Loizeaux M.

1 Plummer A.

1 van der Merwe L.

1 2009

1 2006

Wyniki wyszukiwania

Algorithmic aspects of total-subdomination in graphs

Restrained domination in unicyclic graphs