2-Edge connected dominating sets and 2-Connected dominating sets of a graph

A \(k\)-connected (resp. \(k\)-edge connected) dominating set \(D\) of a connected graph \(G\) is a subset of \(V(G)\) such that \(G[D]\) is \(k\)-connected (resp. \(k\)-edge connected) and each \(v\in V(G)\backslash D\) has at least one neighbor in \(D\). The \(k\) -connected domination number (resp. \(k\) -edge connected domination number) of a graph \(G\) is the minimum size of a \(k\)-connected (resp. \(k\)-edge connected) dominating set of \(G\), and denoted by \(\gamma _k(G)\) (resp. \(\gamma '_k(G)\)). In this paper, we investigate the relation of independence number and 2-connected (resp. 2-edge-connected) domination number, and prove that for a graph \(G\), if it is \(2\)-edge connected, then \(\gamma '_2(G)\le 4\alpha (G)-1\), and it is \(2\)-connected, then \(\gamma _2(G)\le 6\alpha (G)-3\), where \(\alpha (G)\) is the independent number of \(G\).     

Reconfiguration of dominating sets

We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph G is a set S of vertices such that each vertex is either in S or has a neighbour in S. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions s and t such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of k, we consider properties of \(D_k(G)\), the graph consisting of a node for each dominating set of size at most k and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that \(D_{\varGamma (G)+1}(G)\) is not necessarily connected, for \(\varGamma (G)\) the maximum cardinality of a minimal dominating set in G. The result holds even when graphs are constrained to be planar, of bounded tree-width, or b-partite for \(b \ge 3\). Moreover, we construct an infinite family of graphs such that \(D_{\gamma (G)+1}(G)\) has exponential diameter, for \(\gamma (G)\) the minimum size of a dominating set. On the positive side, we show that \(D_{n-\mu }(G)\) is connected and of linear diameter for any graph G on n vertices with a matching of size at least \(\mu +1\).     

Independent dominating sets in regular graphs

Let G be a simple, regular graph of order n and degree δ. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish new upper bounds, as functions of n and δ, for the independent domination number of regular graphs with $n/6<\delta< (3-\sqrt{5})n/2$ . Our two main theorems complement recent results of Goddard et al. (Ann. Comb., 2011) for larger values of δ.     

Independent dominating sets in triangle-free graphs

The independent domination number of a graph is the smallest cardinality of an independent set that dominates the graph. In this paper we consider the independent domination number of triangle-free graphs. We improve several of the known bounds as a function of the order and minimum degree, thereby answering conjectures of Haviland.     

A characterization of graphs with disjoint dominating and paired-dominating sets

A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set and the subgraph induced by the set contains a perfect matching. In this paper, we provide a constructive characterization of graphs whose vertex set can be partitioned into a dominating set and a paired-dominating set.     

New analysis and computational study for the planar connected dominating set problem

The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790–810 2010) introduce a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in \(O(2^{9.822\sqrt{n}}n+n^3)\) time and \(O(2^{8.11\sqrt{n}}n+n^3)\) time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in \(O(2^{9.8\sqrt{n}}n+n^3)\) time with a conventional method and in \(O(2^{8.08\sqrt{n}}n+n^3)\) time with a fast matrix multiplication. For a graph \(G\), let \({\hbox {bw}}(G)\) be the branchwidth of \(G\) and \(\gamma _c(G)\) be the connected dominating number of \(G\). We prove \({\hbox {bw}}(G)\le 2\sqrt{10\gamma _c(G)}+32\). From this result, the planar CDS problem admits an \(O(2^{23.54\sqrt{\gamma _c(G)}}\gamma _c(G)+n^3)\) time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.     

Algorithms for the minimum weight k-fold (connected) dominating set problem

In this paper, we study the problem of computing a minimum weight k-fold dominating set (MWkDS) or a minimum weight k-fold connected dominating set (MWkCDS) in a unit ball graph (UBG). Using slab decomposition and dynamic programming, we give two exact algorithms for the computation of MWkDS and MWkCDS which can be executed in polynomial time if the thickness of the graph is bounded above.     

A greedy algorithm for the fault-tolerant connected dominating set in a general graph

Using a connected dominating set (CDS) to serve as the virtual backbone of a wireless network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to an accidental damage or energy depletion, it is desirable that the virtual backbone is fault tolerant. A node set \(C\) is an \(m\) -fold connected dominating set ( \(m\) -fold CDS) of graph \(G\) if every node in \(V(G)\setminus C\) has at least \(m\) neighbors in \(C\) and the subgraph of \(G\) induced by \(C\) is connected. In this paper, we will present a greedy algorithm to compute an \(m\) -fold CDS in a general graph, which has size at most \(2+\ln (\Delta +m-2)\) times that of a minimum \(m\) -fold CDS, where \(\Delta \) is the maximum degree of the graph. This result improves on the previous best known performance ratio of \(2H(\Delta +m-1)\) for this problem, where \(H(\cdot )\) is the Harmonic number.     

The <Emphasis Type="Italic">k</Emphasis>-hop connected dominating set problem: approximation and hardness

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (\({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\)). We prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {NP}\)-hard on planar bipartite graphs of maximum degree 4. We also prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {APX}\)-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\). Finally, when \(k=1\), we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.     

The second largest number of maximal independent sets in connected graphs with at most one cycle

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all graphs (respectively, connected graphs) of order n??4 with at most one cycle. We also characterize those extremal graphs achieving these values.     

The connected disk covering problem

Let P be a convex polygon with n vertices. We consider a variation of the K-center problem called the connected disk covering problem (CDCP), i.e., finding K congruent disks centered in P whose union covers P with the smallest possible radius, while a connected graph is generated by the centers of the K disks whose edge length can not exceed the radius. We give a 2.81-approximation algorithm in O(Kn) time.     

Spanning 3-connected index of graphs

For an integer $s>0$ and for $u,v\in V(G)$ with $u\ne v$ , an $(s;u,v)$ -path-system of G is a subgraph H of G consisting of s internally disjoint (u, v)-paths, and such an H is called a spanning $(s;u,v)$ -path system if $V(H)=V(G)$ . The spanning connectivity $\kappa ^{*}(G)$ of graph G is the largest integer s such that for any integer k with $1\le k \le s$ and for any $u,v\in V(G)$ with $u\ne v$ , G has a spanning ( $k;u,v$ )-path-system. Let G be a simple connected graph that is not a path, a cycle or a $K_{1,3}$ . The spanning k-connected index of G, written $s_{k}(G)$ , is the smallest nonnegative integer m such that $L^m(G)$ is spanning k-connected. Let $l(G)=\max \{m:\,G$ has a divalent path of length m that is not both of length 2 and in a $K_{3}$ }, where a divalent path in G is a path whose interval vertices have degree two in G. In this paper, we prove that $s_{3}(G)\le l(G)+6$ . The key proof to this result is that every connected 3-triangular graph is 2-collapsible.     

The multiple sequence sets: problem and heuristic algorithms

“Sequence set” is a mathematical model used in many applications such as biological sequences analysis and text processing. However, “single” sequence set model is not appropriate for the rapidly increasing problem size. For example, very large genome sequences should be separated and processed chunk by chunk. For these applications, the underlying mathematical model is “Multiple Sequence Sets” (MSS). To process multiple sequence sets, sequences are distributed to different sets and then sequences on each set are processed in parallel. Deriving effective algorithm for MSS processing is challenging.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

A PTAS for minimum weighted connected vertex cover $$P_3$$ problem in 3-dimensional wireless sensor networks

Given a connected and weighted graph \(G=(V, E)\) with each vertex v having a nonnegative weight w(v), the minimum weighted connected vertex cover \(P_{3}\) problem \((MWCVCP_{3})\) is required to find a subset C of vertices of the graph with minimum total weight, such that each path with length 2 has at least one vertex in C, and moreover, the induced subgraph G[C] is connected. This kind of problem has many applications concerning wireless sensor networks and ad hoc networks. When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor network is a unit ball graph instead of a unit disk graph. In this paper, we propose a new concept called weak c-local and give the first polynomial time approximation scheme (PTAS) for \(MWCVCP_{3}\) in unit ball graphs when the weight is smooth and weak c-local.