Displaying similar documents to “Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree”

Trees with unique minimum total dominating sets

Teresa W. Haynes, Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

Similarity:

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.

Trees with equal restrained domination and total restrained domination numbers

Joanna Raczek (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G = (V,E), a set D ⊆ V(G) is a total restrained dominating set if it is a dominating set and both ⟨D⟩ and ⟨V(G)-D⟩ do not have isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. A set D ⊆ V(G) is a restrained dominating set if it is a dominating set and ⟨V(G)-D⟩ does not contain an isolated vertex. The cardinality of a minimum restrained dominating set in G is the restrained domination number. We...

Trees with equal total domination and total restrained domination numbers

Xue-Gang Chen, Wai Chee Shiu, Hong-Yu Chen (2008)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G = (V,E), a set S ⊆ V(G) is a total dominating set if it is dominating and both ⟨S⟩ has no isolated vertices. The cardinality of a minimum total dominating set in G is the total domination number. A set S ⊆ V(G) is a total restrained dominating set if it is total dominating and ⟨V(G)-S⟩ has no isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. We characterize all trees for which total domination...

Vertices contained in all minimum paired-dominating sets of a tree

Xue-Gang Chen (2007)

Czechoslovak Mathematical Journal

Similarity:

A set S of vertices in a graph G is called a paired-dominating set if it dominates V and 〈 S 〉 contains at least one perfect matching. We characterize the set of vertices of a tree that are contained in all minimum paired-dominating sets of the tree.

Trees with equal 2-domination and 2-independence numbers

Mustapha Chellali, Nacéra Meddah (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization...

Caterpillars

Bohdan Zelinka (1977)

Časopis pro pěstování matematiky

Similarity: