Mirka Miller, R. Sundara Rajan, R. Jayagopal, Indra Rajasingh, Paul Manuel (2017)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we obtain a sharp (improved) lower bound on the locating-total domination number of a graph, and show that the decision problem for the locating-total domination is NP-complete.
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...
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.
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.
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.
S. F. Kapoor, Linda M. Lesniak (1976)
Colloquium Mathematicae
Similarity:
François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2010)
RAIRO - Operations Research
Similarity:
The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still...
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...
Hujter, M., Tuza, Zs. (1993)
Acta Mathematica Universitatis Comenianae. New Series
Similarity:
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.
Tomáš Vetrík (2012)
Discussiones Mathematicae Graph Theory
Similarity:
The choice number of a graph G is the smallest integer k such that for every assignment of a list L(v) of k colors to each vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from L(v). We present upper and lower bounds on the choice number of complete multipartite graphs with partite classes of equal sizes and complete r-partite graphs with r-1 partite classes of order two.
Robert Janczewski, Michał Małafiejski, Anna Małafiejska (2018)
Discussiones Mathematicae Graph Theory
Similarity:
Michael D. Plummer (2006)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; ...
Mieczysław Borowiecki, Anna Fiedorowicz (2006)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper a concept 𝓠-Ramsey Class of graphs is introduced, where 𝓠 is a class of bipartite graphs. It is a generalization of well-known concept of Ramsey Class of graphs. Some 𝓠-Ramsey Classes of graphs are presented (Theorem 1 and 2). We proved that 𝓣₂, the class of all outerplanar graphs, is not 𝓓₁-Ramsey Class (Theorem 3). This results leads us to the concept of acyclic reducible bounds for a hereditary property 𝓟 . For 𝓣₂ we found two bounds (Theorem 4). An improvement,...
DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)
The Electronic Journal of Combinatorics [electronic only]
Similarity: