Special Issue for FAW 2014

For a graph \(G=(V,E)\), a dominating set is a set \(D\subseteq V\) such that every vertex \(v\in V\setminus D\) has a neighbor in \(D\). The minimum outer-connected dominating set (Min-Outer-Connected-Dom-Set) problem for a graph \(G\) is to find a dominating set \(D\) of \(G\) such that \(G[V\setminus D]\), the induced subgraph by \(G\) on \(V\setminus D\), is connected and the cardinality of \(D\) is minimized. In this paper, we consider the complexity of the Min-Outer-Connected-Dom-Set problem. In particular, we show that the decision version of the Min-Outer-Connected-Dom-Set problem is NP-complete for split graphs, a well known subclass of chordal graphs. We also consider the approximability of the Min-Outer-Connected-Dom-Set problem. We show that the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of \((1-\varepsilon ) \ln |V|\) for any \(\varepsilon >0\), unless NP \(\subseteq \) DTIME(\(|V|^{\log \log |V|}\)). For sufficiently large values of \(\varDelta \), we show that for graphs with maximum degree \(\varDelta \), the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of \(\ln \varDelta -C \ln \ln \varDelta \) for some constant \(C\), unless P \(=\) NP. On the positive side, we present a \(\ln (\varDelta +1)+1\)-factor approximation algorithm for the Min-Outer-Connected-Dom-Set problem for general graphs. We show that the Min-Outer-Connected-Dom-Set problem is APX-complete for graphs of maximum degree 4.     

An $$O^{*}(1.4366^n)$$-time exact algorithm for maximum $$P_2$$P2-packing in cubic graphs

Given a graph \(G=(V, E)\), a \(P_2\)-packing \(\mathcal {P}\) is a collection of vertex disjoint copies of \(P_2\)s in \(G\) where a \(P_2\) is a simple path with three vertices and two edges. The Maximum \(P_2\)-Packing problem is to find a \(P_2\)-packing \(\mathcal {P}\) in the input graph \(G\) of maximum cardinality. This problem is NP-hard for cubic graphs. In this paper, we give a branch-and-reduce algorithm for the Maximum \(P_2\)-Packing problem in cubic graphs. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time \(O^{*}(1.4366^n)\) which is faster than previous known exact algorithms where \(n\) is the number of vertices in the input graph.     

An efficient algorithm for distance total domination in block graphs

The \(k\)-distance total domination problem is to find a minimum vertex set \(D\) of a graph such that every vertex of the graph is within distance \(k\) from some vertex of \(D\) other than itself, where \(k\) is a fixed positive integer. In the present paper, by using a labeling method, we design an efficient algorithm for solving the \(k\)-distance total domination problem on block graphs, a superclass of trees.     

Strong minimum energy hierarchical topology in wireless sensor networks

Given a set of \(n\) sensors, the strong minimum energy topology (SMET) problem in a wireless sensor network is to assign transmit powers to all sensors such that (i) the graph induced only using the bi-directional links is connected, that is, there is a path between every pair of sensors, and (ii) the sum of the transmit powers of all the sensors is minimum. This problem is known to be NP-hard. In this paper, we study a special case of the SMET problem, namely , the \(k\)-strong minimum energy hierarchical topology (\(k\)-SMEHT) problem. Given a set of \(n\) sensors and an integer \(k\), the \(k\)-SMEHT problem is to assign transmission powers to all sensors such that (i) the graph induced using only bi-directional links is connected, (ii) at most \(k\) nodes of the graph induced using only bi-directional links have two or more neighbors, that is they are non-pendant nodes, and (iii) the sum of the transmit powers of all the sensors in \(G\) is minimum. We show that \(k\)-SMEHT problem is NP-hard for arbitrary \(k\). However, we propose a \(\frac{k+1}{2}\)-approximation algorithm for \(k\)-SMEHT problem, when \(k\) is a fixed constant. Finally, we propose a polynomial time algorithm for the \(k\)-SMEHT problem for \(k=2\).     

An approximation algorithm for maximum weight budgeted connected set cover

This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set \(X\), a collection of sets \({\mathcal {S}}\subseteq 2^X\), a weight function \(w\) on \(X\), a cost function \(c\) on \({\mathcal {S}}\), a connected graph \(G_{\mathcal {S}}\) (called communication graph) on vertex set \({\mathcal {S}}\), and a budget \(L\), the MWBCSC problem is to select a subcollection \({\mathcal {S'}}\subseteq {\mathcal {S}}\) such that the cost \(c({\mathcal {S'}})=\sum _{S\in {\mathcal {S'}}}c(S)\le L\), the subgraph of \(G_{\mathcal {S}}\) induced by \({\mathcal {S'}}\) is connected, and the total weight of elements covered by \({\mathcal {S'}}\) (that is \(\sum _{x\in \bigcup _{S\in {\mathcal {S'}}}S}w(x)\)) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio \(O((\delta +1)\log n)\), where \(\delta \) is the maximum degree of graph \(G_{\mathcal {S}}\) and \(n\) is the number of sets in \({\mathcal {S}}\). In particular, if every set has cost at most \(L/2\), the performance ratio can be improved to \(O(\log n)\).     

$$$$-labeling for brick product graphs

Let \(G=(V, E)\) be a graph. Denote \(d_G(u, v)\) the distance between two vertices \(u\) and \(v\) in \(G\). An \(L(2, 1)\)-labeling of \(G\) is a function \(f: V \rightarrow \{0,1,\cdots \}\) such that for any two vertices \(u\) and \(v\), \(|f(u)-f(v)| \ge 2\) if \(d_G(u, v) = 1\) and \(|f(u)-f(v)| \ge 1\) if \(d_G(u, v) = 2\). The span of \(f\) is the difference between the largest and the smallest number in \(f(V)\). The \(\lambda \)-number of \(G\), denoted \(\lambda (G)\), is the minimum span over all \(L(2,1 )\)-labelings of \(G\). In this article, we confirm Conjecture 6.1 stated in X. Li et al. (J Comb Optim 25:716–736, 2013) in the case when (i) \(\ell \) is even, or (ii) \(\ell \ge 5\) is odd and \(0 \le r \le 8\).     

Partial degree bounded edge pacing problem for graphs and $$$$-uniform hypergraphs

Given a graph \(G=(V,E)\) and a non-negative integer \(c_u\) for each \(u\in V\), partial degree bounded edge packing problem is to find a subgraph \(G^{\prime }=(V,E^{\prime })\) with maximum \(|E^{\prime }|\) such that for each edge \((u,v)\in E^{\prime }\), either \(deg_{G^{\prime }}(u)\le c_u\) or \(deg_{G^{\prime }}(v)\le c_v\). The problem has been shown to be NP-hard even for uniform degree constraint (i.e., all \(c_u\) being equal). In this work we study the general degree constraint case (arbitrary degree constraint for each vertex) and present two combinatorial approximation algorithms with approximation factors \(4\) and \(2\). Then we give a \(\log _2 n\) approximation algorithm for edge-weighted version of the problem and an efficient exact algorithm for edge-weighted trees with time complexity \(O(n\log n)\). We also consider a generalization of this problem to \(k\)-uniform hypergraphs and present a constant factor approximation algorithm based on linear programming using Lagrangian relaxation.     

On the algorithmic aspects of strong subcoloring

A partition of the vertex set V(G) of a graph G into \(V(G)=V_1\cup V_2\cup \cdots \cup V_k\) is called a k-strong subcoloring if \(d(x,y)\ne 2\) in G for every \(x,y\in V_i\), \(1\le i \le k\) where d(x, y) denotes the length of a shortest x-y path in G. The strong subchromatic number is defined as \(\chi _{sc}(G)=\text {min}\{ k:G \text { admits a }k\)-\(\text {strong subcoloring}\}\). In this paper, we explore the complexity status of the StrongSubcoloring problem: for a given graph G and a positive integer k, StrongSubcoloring is to decide whether G admits a k-strong subcoloring. We prove that StrongSubcoloring is NP-complete for subcubic bipartite graphs and the problem is polynomial time solvable for trees. In addition, we prove the following dichotomy results: (i) for the class of \(K_{1,r}\)-free split graphs, StrongSubcoloring is in P when \(r\le 3\) and NP-complete when \(r>3\) and (ii) for the class of H-free graphs, StrongSubcoloring is polynomial time solvable only if H is an induced subgraph of \(P_4\); otherwise the problem is NP-complete. Next, we consider a lower bound on the strong subchromatic number. A strong set is a set S of vertices of a graph G such that for every \(x,y\in S\), \(d(x,y)= 2\) in G and the cardinality of a maximum strong set in G is denoted by \(\alpha _{s}(G)\). Clearly, \(\alpha _{s}(G)\le \chi _{sc}(G)\). We consider the complexity status of the StrongSet problem: given a graph G and a positive integer k, StrongSet asks whether G contains a strong set of cardinality k. We prove that StrongSet is NP-complete for (i) bipartite graphs and (ii) \(K_{1,4}\)-free split graphs, and it is polynomial time solvable for (i) trees and (ii) \(P_4\)-free graphs.     

The 2-surviving rate of planar graphs without 5-cycles

Let \(G\) be a connected graph with \(n\ge 2\) vertices. Let \(k\ge 1\) be an integer. Suppose that a fire breaks out at a vertex \(v\) of \(G\). A firefighter starts to protect vertices. At each step, the firefighter protects \(k\)-vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let \(\hbox {sn}_k(v)\) denote the maximum number of vertices in \(G\) that the firefighter can save when a fire breaks out at vertex \(v\). The \(k\)-surviving rate \(\rho _k(G)\) of \(G\) is defined to be \(\frac{1}{n^2}\sum _{v\in V(G)} {\hbox {sn}}_{k}(v)\), which is the average proportion of saved vertices. In this paper, we prove that if \(G\) is a planar graph with \(n\ge 2\) vertices and without 5-cycles, then \(\rho _2(G)>\frac{1}{363}\).     

Neighbor sum distinguishing total coloring of graphs embedded in surfaces of nonnegative Euler characteristic

A total coloring of a graph \(G\) is a coloring of its vertices and edges such that adjacent or incident vertices and edges are not colored with the same color. A total \([k]\)-coloring of a graph \(G\) is a total coloring of \(G\) by using the color set \([k]=\{1,2,\ldots ,k\}\). Let \(f(v)\) denote the sum of the colors of a vertex \(v\) and the colors of all incident edges of \(v\). A total \([k]\)-neighbor sum distinguishing-coloring of \(G\) is a total \([k]\)-coloring of \(G\) such that for each edge \(uv\in E(G)\), \(f(u)\ne f(v)\). Let \(G\) be a graph which can be embedded in a surface of nonnegative Euler characteristic. In this paper, it is proved that the total neighbor sum distinguishing chromatic number of \(G\) is \(\Delta (G)+2\) if \(\Delta (G)\ge 14\), where \(\Delta (G)\) is the maximum degree of \(G\).     

On computing a minimum secure dominating set in block graphs

In a graph \(G=(V,E)\), a set \(D \subseteq V\) is said to be a dominating set of G if for every vertex \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\). A secure dominating set of the graph G is a dominating set D of G such that for every \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\) and \((D{\setminus }\{v\})\cup \{u\}\) is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.     

Signed total Roman domination in graphs

Let \(G\) be a finite and simple graph with vertex set \(V(G)\). A signed total Roman dominating function (STRDF) on a graph \(G\) is a function \(f:V(G)\rightarrow \{-1,1,2\}\) satisfying the conditions that (i) \(\sum _{x\in N(v)}f(x)\ge 1\) for each vertex \(v\in V(G)\), where \(N(v)\) is the neighborhood of \(v\), and (ii) every vertex \(u\) for which \(f(u)=-1\) is adjacent to at least one vertex \(v\) for which \(f(v)=2\). The weight of an SRTDF \(f\) is \(\sum _{v\in V(G)}f(v)\). The signed total Roman domination number \(\gamma _{stR}(G)\) of \(G\) is the minimum weight of an STRDF on \(G\). In this paper we initiate the study of the signed total Roman domination number of graphs, and we present different bounds on \(\gamma _{stR}(G)\). In addition, we determine the signed total Roman domination number of some classes of graphs.     

$$$$-labeling number of Cartesian product of path and cycle

For positive numbers \(j\) and \(k\), an \(L(j,k)\)-labeling \(f\) of \(G\) is an assignment of numbers to vertices of \(G\) such that \(|f(u)-f(v)|\ge j\) if \(d(u,v)=1\), and \(|f(u)-f(v)|\ge k\) if \(d(u,v)=2\). The span of \(f\) is the difference between the maximum and the minimum numbers assigned by \(f\). The \(L(j,k)\)-labeling number of \(G\), denoted by \(\lambda _{j,k}(G)\), is the minimum span over all \(L(j,k)\)-labelings of \(G\). In this article, we completely determine the \(L(j,k)\)-labeling number (\(2j\le k\)) of the Cartesian product of path and cycle.     

On (s,t)-relaxed L(2,1)-labeling of graphs

We initiate the study of relaxed \(L(2,1)\)-labelings of graphs. Suppose \(G\) is a graph. Let \(u\) be a vertex of \(G\). A vertex \(v\) is called an \(i\)-neighbor of \(u\) if \(d_G(u,v)=i\). A \(1\)-neighbor of \(u\) is simply called a neighbor of \(u\). Let \(s\) and \(t\) be two nonnegative integers. Suppose \(f\) is an assignment of nonnegative integers to the vertices of \(G\). If the following three conditions are satisfied, then \(f\) is called an \((s,t)\)-relaxed \(L(2,1)\)-labeling of \(G\): (1) for any two adjacent vertices \(u\) and \(v\) of \(G, f(u)\not =f(v)\); (2) for any vertex \(u\) of \(G\), there are at most \(s\) neighbors of \(u\) receiving labels from \(\{f(u)-1,f(u)+1\}\); (3) for any vertex \(u\) of \(G\), the number of \(2\)-neighbors of \(u\) assigned the label \(f(u)\) is at most \(t\). The minimum span of \((s,t)\)-relaxed \(L(2,1)\)-labelings of \(G\) is called the \((s,t)\)-relaxed \(L(2,1)\)-labeling number of \(G\), denoted by \(\lambda ^{s,t}_{2,1}(G)\). It is clear that \(\lambda ^{0,0}_{2,1}(G)\) is the so called \(L(2,1)\)-labeling number of \(G\). \(\lambda ^{1,0}_{2,1}(G)\) is simply written as \(\widetilde{\lambda }(G)\). This paper discusses basic properties of \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of graphs. For any two nonnegative integers \(s\) and \(t\), the exact values of \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of paths, cycles and complete graphs are determined. Tight upper and lower bounds for \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of complete multipartite graphs and trees are given. The upper bounds for \((s,1)\)-relaxed \(L(2,1)\)-labeling number of general graphs are also investigated. We introduce a new graph parameter called the breaking path covering number of a graph. A breaking path \(P\) is a vertex sequence \(v_1,v_2,\ldots ,v_k\) in which each \(v_i\) is adjacent to at least one vertex of \(v_{i-1}\) and \(v_{i+1}\) for \(i=2,3,\ldots ,k-1\). A breaking path covering of \(G\) is a set of disjoint such vertex sequences that cover all vertices of \(G\). The breaking path covering number of \(G\), denoted by \(bpc(G)\), is the minimum number of breaking paths in a breaking path covering of \(G\). In this paper, it is proved that \(\widetilde{\lambda }(G)= n+bpc(G^{c})-2\) if \(bpc(G^{c})\ge 2\) and \(\widetilde{\lambda }(G)\le n-1\) if and only if \(bpc(G^{c})=1\). The breaking path covering number of a graph is proved to be computable in polynomial time. Thus, if a graph \(G\) is of diameter two, then \(\widetilde{\lambda }(G)\) can be determined in polynomial time. Several conjectures and problems on relaxed \(L(2,1)\)-labelings are also proposed.     

Parameterized algorithms for min–max 2-cluster editing

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).     

Weak {2}-domination number of Cartesian products of cycles

For a graph \(G=(V, E)\), a weak \(\{2\}\)-dominating function \(f:V\rightarrow \{0,1,2\}\) has the property that \(\sum _{u\in N(v)}f(u)\ge 2\) for every vertex \(v\in V\) with \(f(v)= 0\), where N(v) is the set of neighbors of v in G. The weight of a weak \(\{2\}\)-dominating function f is the sum \(\sum _{v\in V}f(v)\) and the minimum weight of a weak \(\{2\}\)-dominating function is the weak \(\{2\}\)-domination number. In this paper, we introduce a discharging approach and provide a short proof for the lower bound of the weak \(\{2\}\)-domination number of \(C_n \Box C_5\), which was obtained by St?pień, et al. (Discrete Appl Math 170:113–116, 2014). Moreover, we obtain the weak \(\{2\}\)-domination numbers of \(C_n \Box C_3\) and \(C_n \Box C_4\).     

Characterisation of forests with trivial game domination numbers

In the domination game, two players, the Dominator and Staller, take turns adding vertices of a fixed graph to a set, at each turn increasing the number of vertices dominated by the set, until the final set \(A_*\) dominates the whole graph. The Dominator plays to minimise the size of the set \(A_*\) while the Staller plays to maximise it. A graph is \(D\)-trivial if when the Dominator plays first and both players play optimally, the set \(A_*\) is a minimum dominating set of the graph. A graph is \(S\)-trivial if the same is true when the Staller plays first. We consider the problem of characterising \(D\)-trivial and \(S\)-trivial graphs. We give complete characterisations of \(D\)-trivial forests and of \(S\)-trivial forests. We also show that \(2\)-connected \(D\)-trivial graphs cannot have large girth, and conjecture that the same holds without the connectivity condition.     

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

Dynamic matchings in left vertex weighted convex bipartite graphs

A left vertex weighted convex bipartite graph (LWCBG) is a bipartite graph \(G=(X,Y,E)\) in which the neighbors of each \(x\in X\) form an interval in \(Y\) where \(Y\) is linearly ordered, and each \(x\in X\) has an associated weight. This paper considers the problem of maintaining a maximum weight matching in a dynamic LWCBG. The graph is subject to the updates of vertex and edge insertions and deletions. Our dynamic algorithms maintain the update operations in \(O(\log ^2{|V|})\) amortized time per update, obtain the matching status of a vertex (whether it is matched) in constant worst-case time, and find the pair of a matched vertex (with which it is matched) in worst-case \(O(k)\) time, where \(k\) is not greater than the cardinality of the maximum weight matching. That achieves the same time bound as the best known solution for the problem of the unweighted version.     

An improved parameterized algorithm for the <Emphasis Type="Italic">p</Emphasis>-cluster vertex deletion problem

In the p-Cluster Vertex Deletion problem, we are given a graph \(G=(V,E)\) and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let \(r=p/k\). In this paper, we design a branching algorithm with time complexity \(O(\alpha ^k+|V||E|)\), where \(\alpha \) depends on r and has a rough upper bound \(\min \{1.618^{1+r},2\}\). With a more precise analysis, we show that \(\alpha =1.28\cdot 3.57^{r}\) for \(r\le 0.219\); \(\alpha =(1-r)^{r-1}r^{-r}\) for \(0.219< r<1/2\); and \(\alpha =2\) for \(r\ge 1/2\), respectively. Our algorithm also works with the same time complexity for the variant that the number of clusters is at most p. Our result improves the previous best time complexity \(O^*(1.84^{p+k})\) and implies that for fixed p the problem can be solved as efficiently as Vertex Cover.