Displaying similar documents to “Efficient (j,k)-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.

Various Bounds for Liar’s Domination Number

Abdollah Alimadadi, Doost Ali Mojdeh, Nader Jafari Rad (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V...

Domination in Analysis

Denny Gulick (1973)

Publications du Département de mathématiques (Lyon)

Similarity:

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.

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

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

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

Total domination subdivision numbers of graphs

Teresa W. Haynes, Michael A. Henning, Lora S. Hopkins (2004)

Discussiones Mathematicae Graph Theory

Similarity:

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

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

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 the Totalk-Domination in Graphs

Sergio Bermudo, Juan C. Hernández-Gómez, José M. Sigarreta (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V, E) be a graph; a set S ⊆ V is a total k-dominating set if every vertex v ∈ V has at least k neighbors in S. The total k-domination number γkt(G) is the minimum cardinality among all total k-dominating sets. In this paper we obtain several tight bounds for the total k-domination number of a graph. In particular, we investigate the relationship between the total k-domination number of a graph and the order, the size, the girth, the minimum and maximum degree, the diameter,...

The Domination Number of K 3 n

John Georges, Jianwei Lin, David Mauro (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Let K3n denote the Cartesian product Kn□Kn□Kn, where Kn is the complete graph on n vertices. We show that the domination number of K3n is [...]

A Gallai-type equality for the total domination number of a graph

Sanming Zhou (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We prove the following Gallai-type equality γₜ(G) + εₜ(G) = p for any graph G with no isolated vertex, where p is the number of vertices of G, γₜ(G) is the total domination number of G, and εₜ(G) is the maximum integer s such that there exists a spanning forest F with s the number of pendant edges of F minus the number of star components of F.

Cubic Graphs with Total Domatic Number at Least Two

Saieed Akbari, Mohammad Motiei, Sahand Mozaffari, Sina Yazdanbod (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. A total dominating set of G is a set S of vertices of G such that every vertex is adjacent to at least one vertex in S. The total domatic number of a graph is the maximum number of total dominating sets which partition the vertex set of G. In this paper we provide a criterion under which a cubic graph has total domatic number at least two.

The Signed Total Roman k-Domatic Number Of A Graph

Lutz Volkmann (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Let k ≥ 1 be an integer. A signed total Roman k-dominating function on a graph G is a function f : V (G) → {−1, 1, 2} such that Ʃu2N(v) f(u) ≥ k for every v ∈ V (G), where N(v) is the neighborhood of v, and every vertex u ∈ V (G) for which f(u) = −1 is adjacent to at least one vertex w for which f(w) = 2. A set {f1, f2, . . . , fd} of distinct signed total Roman k-dominating functions on G with the property that Ʃdi=1 fi(v) ≤ k for each v ∈ V (G), is called a signed total Roman k-dominating...