Nader Jafari Rad (2016)
Discussiones Mathematicae Graph Theory
Similarity:
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
Mieczysław Borowiecki, Danuta Michalak, Elżbieta Sidorowicz (1997)
Discussiones Mathematicae Graph Theory
Similarity:
The purpose of this paper is to present some basic properties of 𝓟-dominating, 𝓟-independent, and 𝓟-irredundant sets in graphs which generalize well-known properties of dominating, independent and irredundant sets, respectively.
Bert L. Hartnell, Douglas F. Rall (2004)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and...
Tobias Gerlach, Jochen Harant (2002)
Discussiones Mathematicae Graph Theory
Similarity:
DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.
Lutz Volkmann (2015)
Discussiones Mathematicae Graph Theory
Similarity:
Let G be a graph with vertex set V (G), and let f : V (G) → {−1, 1} be a two-valued function. If k ≥ 1 is an integer and Σx∈N(v) f(x) ≥ k for each v ∈ V (G), where N(v) is the neighborhood of v, then f is a signed total k-dominating function on G. A set {f1, f2, . . . , fd} of distinct signed total k-dominating functions on G with the property that Σdi=1 fi(x) ≤ k for each x ∈ V (G), is called a signed total (k, k)-dominating family (of functions) on G. The maximum number of functions...
S. Fitzpatrick, B. Hartnell (1998)
Discussiones Mathematicae Graph Theory
Similarity:
We are interested in dominating sets (of vertices) with the additional property that the vertices in the dominating set can be paired or matched via existing edges in the graph. This could model the situation of guards or police where each has a partner or backup. This paper will focus on those graphs in which the number of matched pairs of a minimum dominating set of this type equals the size of some maximal matching in the graph. In particular, we characterize the leafless graphs of...
Gerd H. Fricke, Sandra M. Hedetniemi, Stephen T. Hedetniemi, Kevin R. Hutson (2011)
Discussiones Mathematicae Graph Theory
Similarity:
A set S ⊆ V is a dominating set of a graph G = (V,E) if every vertex in V -S is adjacent to at least one vertex in S. The domination number γ(G) of G equals the minimum cardinality of a dominating set S in G; we say that such a set S is a γ-set. In this paper we consider the family of all γ-sets in a graph G and we define the γ-graph G(γ) = (V(γ), E(γ)) of G to be the graph whose vertices V(γ) correspond 1-to-1 with the γ-sets of G, and two γ-sets, say D₁ and D₂, are adjacent in E(γ)...
Mostafa Blidia, Mustapha Chellali, Lutz Volkmann (2005)
Discussiones Mathematicae Graph Theory
Similarity:
Let p be a positive integer and G = (V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times. The minimum cardinality of a p-dominating set a of G is the p-domination number γₚ(G). It is proved for a cactus graph G that γₚ(G) ⩽ (|V| + |Lₚ(G)| + c(G))/2, for every positive integer p ⩾ 2, where Lₚ(G) is the set of vertices of G of degree at most p-1 and c(G) is the number of odd cycles in G.
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...
Juan Alberto Rodríguez-Velázquez, Erick David Rodríguez-Bazan, Alejandro Estrada-Moreno (2017)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we obtain closed formulae for several parameters of generalized Sierpiński graphs S(G, t) in terms of parameters of the base graph G. In particular, we focus on the chromatic, vertex cover, clique and domination numbers.
Anders Sune Pedersen (2005)
Discussiones Mathematicae Graph Theory
Similarity:
The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are...
José D. Alvarado, Simone Dantas, Dieter Rautenbach (2017)
Discussiones Mathematicae Graph Theory
Similarity:
For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize...
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,...
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...
Majid Hajian, Nader Jafari Rad (2017)
Discussiones Mathematicae Graph Theory
Similarity:
A Roman dominating function (or just RDF) on a graph G = (V,E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = Pu2V (G) f(u). The Roman domination number of a graph G, denoted by R(G), is the minimum weight of a Roman dominating function on G. A graph G is Roman domination stable if the Roman domination number of G remains unchanged under...
Gábor Bacsó, Danuta Michalak, Zsolt Tuza (2005)
Discussiones Mathematicae Graph Theory
Similarity:
A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
Lazebnik, F., Ustimenko, V.A., Woldar, A.J. (1997)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
William F. Klostermeyer, Gary MacGillivray (2017)
Discussiones Mathematicae Graph Theory
Similarity:
We show that for every minimum eternal dominating set, D, of a graph G and every vertex v ∈ D, there is a sequence of attacks at the vertices of G which can be defended in such a way that an eternal dominating set not containing v is reached. The study of the stronger assertion that such a set can be reached after a single attack is defended leads to the study of graphs which are critical in the sense that deleting any vertex reduces the eternal domination number. Examples of these graphs...
Bert L. Hartnell, Douglas F. Rall (2003)
Discussiones Mathematicae Graph Theory
Similarity:
The study of domination in Cartesian products has received its main motivation from attempts to settle a conjecture made by V.G. Vizing in 1968. He conjectured that γ(G)γ(H) is a lower bound for the domination number of the Cartesian product of any two graphs G and H. Most of the progress on settling this conjecture has been limited to verifying the conjectured lower bound if one of the graphs has a certain structural property. In addition, a number of authors have established bounds...
Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Spacapan (2006)
Discussiones Mathematicae Graph Theory
Similarity:
Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
Włodzimierz Ulatowski (2009)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective...