Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Algorithmic aspects of total-subdomination in graphs

Laura M. Harris;  Johannes H. Hattingh;  Michael A. Henning — 2006

Discussiones Mathematicae Graph Theory

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

Restrained domination in unicyclic graphs

Johannes H. Hattingh;  Ernst J. Joubert;  Marc Loizeaux;  Andrew R. Plummer;  Lucas van der Merwe — 2009

Discussiones Mathematicae Graph Theory

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.

Page 1

Download Results (CSV)