For a graph G, a set D⊆V(G) is called a 1,j-dominating set if every vertex in V(G)∖D has at least one and at most j neighbors in D. A set D⊆V(G) is called a 1,j-total dominating set if every vertex ...in V(G) has at least one and at most j neighbors in D. In the 1,j-(Total) Dominating Set problem we are given a graph G and a positive integer k. The objective is to test whether there exists a 1,j-(total) dominating set of size at most k. The 1,j-Dominating Set problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The 1,2-Total Dominating Set problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the Dominating Set problem, both are W1-hard when parameterized by solution size. In this work, we study the aforementioned problems on various graph classes from the perspective of parameterized complexity and prove the following results:•1,j-Dominating Set parameterized by solution size is W1-hard on d-degenerate graphs for d=j+1.•1,j-Dominating Set parameterized by solution size is FPT on nowhere dense graphs.•The known algorithm for 1,j-Dominating Set on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH).•Assuming SETH, we provide a lower bound for the running time of any algorithm solving the 1,2-Total Dominating Set problem parameterized by pathwidth.•Finally, we study another variant of Dominating Set, called Restrained Dominating Set, that asks if there is a dominating set D of G of size at most k such that no vertex outside of D has all of its neighbors in D. We prove this variant is W1-hard even on 3-degenerate graphs.
Italian domination in trees Henning, Michael A.; Klostermeyer, William F.
Discrete Applied Mathematics,
01/2017, Letnik:
217
Journal Article
Recenzirano
Odprti dostop
The Roman domination number and Italian domination number (also known as the Roman {2}-domination number) are graph labeling problems in which each vertex is labeled with either 0, 1, or 2. In the ...Roman domination problem, each vertex labeled 0 must be adjacent to at least one vertex labeled 2. In the Italian domination problem, each vertex labeled 0 must have the labels of the vertices in its closed neighborhood sum to at least two. The Italian domination number, γI(G), of a graph G is the minimum possible sum of such a labeling, where the sum is taken over all the vertices in G. It is known that if T is a tree with at least two vertices, then γ(T)+1≤γI(T)≤2γ(T). In this paper, we characterize the trees T for which γ(T)+1=γI(T), and we characterize the trees T for which γI(T)=2γ(T).
A locating-dominating set (LDS) of a graph G is a dominating set S of G such that for every two vertices u and v in V(G)∖S, N(u)∩S≠N(v)∩S. The locating-domination number γL(G) is the minimum ...cardinality of a LDS of G. Further if S is a total dominating set then S is called a locating-total dominating set. In this paper we determine the domination, total domination, locating-domination and locating-total domination numbers for hypertrees and sibling trees.
In this paper we consider secondary dominating sets, also named as \((1,k)\)-dominating sets, introduced by Hedetniemi et al. in 2008. In particular, we study intersections of the ...\((1,1)\)-dominating sets and proper \((1,2)\)-dominating sets. We introduce \((1,\overline{2})\)-intersection index as the minimum possible cardinality of such intersection and determine its value for some classes of graphs.
Consider a simple and finite graph G. A subset D of its vertex set V is a dominating set if |(N(v)∪{v})∩D|≥1 for each v∈V. Several “multiple” counterparts of such sets are known. In particular, D is ...said to be a k-dominating set, if every vertex v not in D satisfies |N(v)∩D|≥k, or a k-tuple dominating set if |(N(v)∪{v})∩D|≥k for each v∈V, or a k-tuple total dominating set if every vertex has at least k neighbours in D. We generalize a well known result by Alon and Spencer concerning dominating sets to obtain new upper bounds for the minimum size of their multiple analogues. These also provide upper bounds in a generalized concept of so-called liar’s dominating sets, which were first introduced by Slater.
The problems of determining locating-dominating, open locating-dominating or locating total-dominating sets of minimum cardinality in a graph G are variations of the classical minimum dominating set ...problem in G and are all known to be hard for general graphs. A typical line of attack is therefore to determine the cardinality of minimum such sets in special graphs.
In this work we study the three problems from a polyhedral point of view. We provide the according linear relaxations, discuss their combinatorial structure, and demonstrate how the associated polyhedra can be entirely described or polyhedral arguments can be applied to find minimum such sets for special graphs.
In this paper, the notion of connected end anti-fuzzy equitable dominating set of an anti-fuzzy graph is discussed. The connected end anti-fuzzy equitable domination number for some standard graphs ...are obtained. The relation between anti-fuzzy equitable domination number, end anti-fuzzy equitable domination number and connected end anti-fuzzy equitable domination number are established. Theorems related to these parameters are stated and proved.
A dominating set S of a graph is a metric-locating-dominating set if each vertex of the graph is uniquely distinguished by its distances from the elements of S, and the minimum cardinality of such a ...set is called the metric-location-domination number. In this paper, we undertake a study that, in general graphs and specific families, relates metric-locating-dominating sets to other special sets: resolving sets, dominating sets, locating-dominating sets and doubly resolving sets. We first characterize the extremal trees of the bounds that naturally involve metric-location-domination number, metric dimension and domination number. Then, we prove that there is no polynomial upper bound on the location-domination number in terms of the metric-location-domination number, thus extending a result of Henning and Oellermann. Finally, we show different methods to transform metric-locating-dominating sets into locating-dominating sets and doubly resolving sets. Our methods produce new bounds on the minimum cardinalities of all those sets, some of them concerning parameters that have not been related so far.
PDF
