Displaying similar documents to “Trees with equal total domination and total restrained domination numbers”

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

Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree

Michael A. Henning, Alister J. Marcon (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γt(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating...

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

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.

Total Domination Multisubdivision Number of a Graph

Diana Avella-Alaminos, Magda Dettlaff, Magdalena Lemańska, Rita Zuazua (2015)

Discussiones Mathematicae Graph Theory

Similarity:

The domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msdγt (G) of a graph G and we show that for any connected graph G of order at least two, msdγt (G) ≤ 3. We show that for trees the total domination multisubdi- vision number is equal to the known total domination...

Efficient (j,k)-domination

Robert R. Rubalcaba, Peter J. Slater (2007)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set S of a graph G is called efficient if |N[v]∩ S| = 1 for every vertex v ∈ V(G). That is, a dominating set S is efficient if and only if every vertex is dominated exactly once. In this paper, we investigate efficient multiple domination. There are several types of multiple domination defined in the literature: k-tuple domination, {k}-domination, and k-domination. We investigate efficient versions of the first two as well as a new type of multiple domination.

Domination Parameters of a Graph and its Complement

Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning (2018)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set in a graph G is a set S of vertices such that every vertex in V (G) S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.

Characterization of trees with equal 2-domination number and domination number plus two

Mustapha Chellali, Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V(G),E(G)) be a simple graph, and let k be a positive integer. A subset D of V(G) is a k-dominating set if every vertex of V(G) - D is dominated at least k times by D. The k-domination number γₖ(G) is the minimum cardinality of a k-dominating set of G. In [5] Volkmann showed that for every nontrivial tree T, γ₂(T) ≥ γ₁(T)+1 and characterized extremal trees attaining this bound. In this paper we characterize all trees T with γ₂(T) = γ₁(T)+2.

A Note on Non-Dominating Set Partitions in Graphs

Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating)...

Optimal Locating-Total Dominating Sets in Strips of Height 3

Ville Junnila (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A set C of vertices in a graph G = (V,E) is total dominating in G if all vertices of V are adjacent to a vertex of C. Furthermore, if a total dominating set C in G has the additional property that for any distinct vertices u, v ∈ V C the subsets formed by the vertices of C respectively adjacent to u and v are different, then we say that C is a locating-total dominating set in G. Previously, locating-total dominating sets in strips have been studied by Henning and Jafari Rad (2012)....

On Graphs with Disjoint Dominating and 2-Dominating Sets

Michael A. Henning, Douglas F. Rall (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices...

On Unique Minimum Dominating Sets in Some Cartesian Product Graphs

Jason T. Hedetniemi (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Unique minimum vertex dominating sets in the Cartesian product of a graph with a complete graph are considered. We first give properties of such sets when they exist. We then show that when the first factor of the product is a tree, consideration of the tree alone is sufficient to determine if the product has a unique minimum dominating set.

Hereditary domination and independence parameters

Wayne Goddard, Teresa Haynes, Debra Knisley (2004)

Discussiones Mathematicae Graph Theory

Similarity:

For a graphical property P and a graph G, we say that a subset S of the vertices of G is a P-set if the subgraph induced by S has the property P. Then the P-domination number of G is the minimum cardinality of a dominating P-set and the P-independence number the maximum cardinality of a P-set. We show that several properties of domination, independent domination and acyclic domination hold for arbitrary properties P that are closed under disjoint unions and subgraphs.

Two Short Proofs on Total Domination

Allan Bickle (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A set of vertices of a graph G is a total dominating set if each vertex of G is adjacent to a vertex in the set. The total domination number of a graph Υt (G) is the minimum size of a total dominating set. We provide a short proof of the result that Υt (G) ≤ 2/3n for connected graphs with n ≥ 3 and a short characterization of the extremal graphs.

Graphs with equal domination and 2-distance domination numbers

Joanna Raczek (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. The distance between two vertices u and v in a connected graph G is the length of the shortest (u-v) path in G. A set D ⊆ V(G) is a dominating set if every vertex of G is at distance at most 1 from an element of D. The domination number of G is the minimum cardinality of a dominating set of G. A set D ⊆ V(G) is a 2-distance dominating set if every vertex of G is at distance at most 2 from an element of D. The 2-distance domination number of G is the minimum...