Approximation algorithms for minimum weight partial connected set cover problem

In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set \(U\), an integer \(q\le |U|\), a collection \(\mathcal {E}\) of subsets of \(U\), and a connected graph \(G_{\mathcal {E}}\) on vertex set \(\mathcal {E}\), the goal is to find a minimum weight subcollection of \(\mathcal {E}\) which covers at least \(q\) elements of \(U\) and induces a connected subgraph in \(G_{\mathcal {E}}\). In this paper, we derive a “partial cover property” for the greedy solution of the Minimum Weight Set Cover problem, based on which we present (a) for the weighted version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are adjacent in \(G_{\mathcal {E}}\) (the Minimum Weight Partial Connected Vertex Cover problem falls into this range), an approximation algorithm with performance ratio \(\rho (1+H(\gamma ))+o(1)\), and (b) for the cardinality version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are at most \(d\)-hops away from each other (the Minimum Partial Connected \(k\)-Hop Dominating Set problem falls into this range), an approximation algorithm with performance ratio \(2(1+dH(\gamma ))+o(1)\), where \(\gamma =\max \{|X|:X\in \mathcal {E}\}\), \(H(\cdot )\) is the Harmonic number, and \(\rho \) is the performance ratio for the Minimum Quota Node-Weighted Steiner Tree problem.     

An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Given a vertex-weighted undirected connected graph \(G = (V, E, \ell , \rho )\), where each edge \(e \in E\) has a length \(\ell (e) > 0\) and each vertex \(v \in V\) has a weight \(\rho (v) > 0\), a subset \(T \subseteq V\) of vertices and a set S containing all the points on edges in a subset \(E' \subseteq E\) of edges, the generalized absolute 1-center problem (GA1CP), an extension of the classic vertex-weighted absolute 1-center problem (A1CP), asks to find a point from S such that the longest weighted shortest path distance in G from it to T is minimized. This paper presents a simple FPTAS for GA1CP by traversing the edges in \(E'\) using a positive real number as step size. The FPTAS takes \(O( |E| |V| + |V|^2 \log \log |V| + \frac{1}{\epsilon } |E'| |T| {\mathcal {R}})\) time, where \({\mathcal {R}}\) is an input parameter size of the problem instance, for any given \(\epsilon > 0\). For instances with a small input parameter size \({\mathcal {R}}\), applying the FPTAS with \(\epsilon = \Theta (1)\) to the classic vertex-weighted A1CP can produce a \((1 + \Theta (1))\)-approximation in at most O(|E| |V|) time when the distance matrix is known and \(O(|E| |V| + |V|^2 \log \log |V|)\) time when the distance matrix is unknown, which are smaller than Kariv and Hakimi’s \(O(|E| |V| \log |V|)\)-time algorithm and \(O(|E| |V| \log |V| + |V|^3)\)-time algorithm, respectively.     

On minimally 2-connected graphs with generalized connectivity $$\kappa _{3}=2$$

For \(S\subseteq G\), let \(\kappa (S)\) denote the maximum number r of edge-disjoint trees \(T_1, T_2, \ldots , T_r\) in G such that \(V(T_i)\cap V(T_j)=S\) for any \(i,j\in \{1,2,\ldots ,r\}\) and \(i\ne j\). For every \(2\le k\le n\), the k-connectivity of G, denoted by \(\kappa _k(G)\), is defined as \(\kappa _k(G)=\hbox {min}\{\kappa (S)| S\subseteq V(G)\ and\ |S|=k\}\). Clearly, \(\kappa _2(G)\) corresponds to the traditional connectivity of G. In this paper, we focus on the structure of minimally 2-connected graphs with \(\kappa _{3}=2\). Denote by \(\mathcal {H}\) the set of minimally 2-connected graphs with \(\kappa _{3}=2\). Let \(\mathcal {B}\subseteq \mathcal {H}\) and every graph in \(\mathcal {B}\) is either \(K_{2,3}\) or the graph obtained by subdividing each edge of a triangle-free 3-connected graph. We obtain that \(H\in \mathcal {H}\) if and only if \(H\in \mathcal {B}\) or H can be constructed from one or some graphs \(H_{1},\ldots ,H_{k}\) in \(\mathcal {B}\) (\(k\ge 1\)) by applying some operations recursively.     

Further properties on the degree distance of graphs

In this paper, we study the degree distance of a connected graph \(G\), defined as \(D^{'} (G)=\sum _{u\in V(G)} d_{G} (u)D_{G} (u)\), where \(D_{G} (u)\) is the sum of distances between the vertex \(u\) and all other vertices in \(G\) and \(d_{G} (u)\) denotes the degree of vertex \(u\) in \(G\). Our main purpose is to investigate some properties of degree distance. We first investigate degree distance of tensor product \(G\times K_{m_0,m_1,\cdots ,m_{r-1}}\), where \(K_{m_0,m_1,\cdots ,m_{r-1}}\) is the complete multipartite graph with partite sets of sizes \(m_0,m_1,\cdots ,m_{r-1}\), and we present explicit formulas for degree distance of the product graph. In addition, we give some Nordhaus–Gaddum type bounds for degree distance. Finally, we compare the degree distance and eccentric distance sum for some graph families.     

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.     

The $$(k,\ell )$$-proper index of graphs

A tree T in an edge-colored graph is called a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be an integer with \(2\le k \le n\). For \(S\subseteq V(G)\) and \(|S| \ge 2\), an S-tree is a tree containing the vertices of S in G. A set \(\{T_1,T_2,\ldots ,T_\ell \}\) of S-trees is called internally disjoint if \(E(T_i)\cap E(T_j)=\emptyset \) and \(V(T_i)\cap V(T_j)=S\) for \(1\le i\ne j\le \ell \). For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by \(\kappa (S)\). The k-connectivity \(\kappa _k(G)\) of G is defined by \(\kappa _k(G)=\min \{\kappa (S)\mid S\) is a k-subset of \(V(G)\}\). For a connected graph G of order n and for two integers k and \(\ell \) with \(2\le k\le n\) and \(1\le \ell \le \kappa _k(G)\), the \((k,\ell )\)-proper index \(px_{k,\ell }(G)\) of G is the minimum number of colors that are required in an edge-coloring of G such that for every k-subset S of V(G), there exist \(\ell \) internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and \(\ell \) with \(k \ge 3\) and \(\ell \le \kappa _k(K_{n,n})\), there exists a positive integer \(N_1=N_1(k,\ell )\) such that \(px_{k,\ell }(K_n) = 2\) for every integer \(n \ge N_1\), and there exists also a positive integer \(N_2=N_2(k,\ell )\) such that \(px_{k,\ell }(K_{m,n}) = 2\) for every integer \(n \ge N_2\) and \(m=O(n^r) (r \ge 1)\). In addition, we show that for every \(p \ge c\root k \of {\frac{\log _a n}{n}}\) (\(c \ge 5\)), \(px_{k,\ell }(G_{n,p})\le 2\) holds almost surely, where \(G_{n,p}\) is the Erd?s–Rényi random graph model.     

Sparse multipartite graphs as partition universal for graphs with bounded degree

For graphs G and H, let \(G\rightarrow (H,H)\) signify that any red/blue edge coloring of G contains a monochromatic H as a subgraph. Denote \(\mathcal {H}(\Delta ,n)=\{H:|V(H)|=n,\Delta (H)\le \Delta \}\). For any \(\Delta \) and n, we say that G is partition universal for \(\mathcal {H}(\Delta ,n)\) if \(G\rightarrow (H,H)\) for every \(H\in \mathcal {H}(\Delta ,n)\). Let \(G_r(N,p)\) be the random spanning subgraph of the complete r-partite graph \(K_r(N)\) with N vertices in each part, in which each edge of \(K_r(N)\) appears with probability p independently and randomly. We prove that for fixed \(\Delta \ge 2\) there exist constants r, B and C depending only on \(\Delta \) such that if \(N\ge Bn\) and \(p=C(\log N/N)^{1/\Delta }\), then asymptotically almost surely \(G_r(N,p)\) is partition universal for \(\mathcal {H}(\Delta ,n)\).     

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.     

Maximum coverage problem with group budget constraints

We study the maximum coverage problem with group budget constraints (MCG). The input consists of a ground set X, a collection \(\psi \) of subsets of X each of which is associated with a combinatorial structure such that for every set \(S_j\in \psi \), a cost \(c(S_j)\) can be calculated based on the combinatorial structure associated with \(S_j\), a partition \(G_1,G_2,\ldots ,G_l\) of \(\psi \), and budgets \(B_1,B_2,\ldots ,B_l\), and B. A solution to the problem consists of a subset H of \(\psi \) such that \(\sum _{S_j\in H} c(S_j) \le B\) and for each \(i \in {1,2,\ldots ,l}\), \(\sum _{S_j \in H\cap G_i}c(S_j)\le B_i\). The objective is to maximize \(|\bigcup _{S_j\in H}S_j|\). In our work we use a new and improved analysis of the greedy algorithm to prove that it is a \((\frac{\alpha }{3+2\alpha })\)-approximation algorithm, where \(\alpha \) is the approximation ratio of a given oracle which takes as an input a subset \(X^{new}\subseteq X\) and a group \(G_i\) and returns a set \(S_j\in G_i\) which approximates the optimal solution for \(\max _{D\in G_i}\frac{|D\cap X^{new}|}{c(D)}\). This analysis that is shown here to be tight for the greedy algorithm, improves by a factor larger than 2 the analysis of the best known approximation algorithm for MCG.     

Information exchange with collision detection on multiple channels

Information exchange is a fundamental communication primitive in radio networks. We study this problem in multi-channel single-hop networks. In particular, given \(k\) pieces of information, initially stored in \(k\) nodes respectively, the task is to broadcast these information pieces to the entire network via a set of \(\mathcal {F}\) channels. We develop efficient distributed algorithms for this task for the scenario where both the identities and the number \(k\) of the initial information holders are unknown to the participating nodes. Assuming nodes with collision detection, we present an efficient randomized algorithm for unrestricted information exchange, where multiple information items can be combined into a single message. The algorithm disseminates all the information items within \(O(\frac{k}{\mathcal {F}}+\mathcal {F}\log ^2n)\) timeslots with high probability. To the best of our knowledge, this is the first algorithm that breaks the \(\varOmega (k)\) lower bound for unrestricted information exchange if only a single channel is available. This result establishes the superiority of multiple channels for the task of unrestricted information exchange. Moreover, for restricted information exchange, where each message can carry only one information item, we devise a randomized algorithm that completes the task in \(O(k+\frac{\log ^2n}{\mathcal {F}}+\log n)\) timeslots. When \(k\) is large, both algorithms are asymptotically optimal, as they can reach the trivial lower bounds of \(\varOmega (\frac{k}{\mathcal {F}})\) and \(\varOmega (k)\) for unrestricted and restricted information exchange, respectively.     

Approximation for maximizing monotone non-decreasing set functions with a greedy method

We study the problem of maximizing a monotone non-decreasing function \(f\) subject to a matroid constraint. Fisher, Nemhauser and Wolsey have shown that, if \(f\) is submodular, the greedy algorithm will find a solution with value at least \(\frac{1}{2}\) of the optimal value under a general matroid constraint and at least \(1-\frac{1}{e}\) of the optimal value under a uniform matroid \((\mathcal {M} = (X,\mathcal {I})\), \(\mathcal {I} = \{ S \subseteq X: |S| \le k\}\)) constraint. In this paper, we show that the greedy algorithm can find a solution with value at least \(\frac{1}{1+\mu }\) of the optimum value for a general monotone non-decreasing function with a general matroid constraint, where \(\mu = \alpha \), if \(0 \le \alpha \le 1\); \(\mu = \frac{\alpha ^K(1-\alpha ^K)}{K(1-\alpha )}\) if \(\alpha > 1\); here \(\alpha \) is a constant representing the “elemental curvature” of \(f\), and \(K\) is the cardinality of the largest maximal independent sets. We also show that the greedy algorithm can achieve a \(1 - (\frac{\alpha + \cdots + \alpha ^{k-1}}{1+\alpha + \cdots + \alpha ^{k-1}})^k\) approximation under a uniform matroid constraint. Under this unified \(\alpha \)-classification, submodular functions arise as the special case \(0 \le \alpha \le 1\).     

A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorable

A graph G is \((d_1, d_2)\)-colorable if its vertices can be partitioned into subsets \(V_1\) and \(V_2\) such that in \(G[V_1]\) every vertex has degree at most \(d_1\) and in \(G[V_2]\) every vertex has degree at most \(d_2\). Let \(\mathcal {G}_5\) denote the family of planar graphs with minimum cycle length at least 5. It is known that every graph in \(\mathcal {G}_5\) is \((d_1, d_2)\)-colorable, where \((d_1, d_2)\in \{(2,6), (3,5),(4,4)\}\). We still do not know even if there is a finite positive d such that every graph in \(\mathcal {G}_5\) is (1, d)-colorable. In this paper, we prove that every graph in \(\mathcal {G}_5\) without adjacent 5-cycles is (1, 7)-colorable. This is a partial positive answer to a problem proposed by Choi and Raspaud that is every graph in \(\mathcal {G}_5\;(1, 7)\)-colorable?.     

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

An inequality that relates the size of a bipartite graph with its order and restrained domination number

Let \(G=(V,E)\) be a graph. A set \(S\subseteq V\) is a restrained dominating set if every vertex in \(V-S\) is adjacent to a vertex in \(S\) and to a vertex in \(V-S\). The restrained domination number of \(G\), denoted \(\gamma _{r}(G)\), is the smallest cardinality of a restrained dominating set of \(G\). Consider a bipartite graph \(G\) of order \(n\ge 4,\) and let \(k\in \{2,3,...,n-2\}.\) In this paper we will show that if \(\gamma _{r}(G)=k\), then \(m\le ((n-k)(n-k+6)+4k-8)/4\). We will also show that this bound is best possible.     

Trinque problem: covering complete graphs by plane degree-bounded hypergraphs

Let \(K_n\) be a complete graph drawn on the plane with every vertex incident to the infinite face. For any integers i and d, we define the (i, d)-Trinque Number of \(K_n\), denoted by \({\mathcal {T}}^d_{i}(K_n)\), as the smallest integer k such that there is an edge-covering of \(K_n\) by k “plane” hypergraphs of degree at most d and size of edge bounded by i. We compute this number for graphs (that is \(i=2\)) and gives some bounds for general hypergraphs.     

Neighbor sum distinguishing total choosability of planar graphs

A total-k-coloring of a graph G is a mapping \(c: V(G)\cup E(G)\rightarrow \{1, 2,\dots , k\}\) such that any two adjacent or incident elements in \(V(G)\cup E(G)\) receive different colors. For a total-k-coloring of G, let \(\sum _c(v)\) denote the total sum of colors of the edges incident with v and the color of v. If for each edge \(uv\in E(G)\), \(\sum _c(u)\ne \sum _c(v)\), then we call such a total-k-coloring neighbor sum distinguishing. The least number k needed for such a coloring of G is the neighbor sum distinguishing total chromatic number, denoted by \(\chi _{\Sigma }^{''}(G)\). Pil?niak and Wo?niak conjectured \(\chi _{\Sigma }^{''}(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that for any planar graph G with maximum degree \(\Delta (G)\), \(ch^{''}_{\Sigma }(G)\le \max \{\Delta (G)+3,16\}\), where \(ch^{''}_{\Sigma }(G)\) is the neighbor sum distinguishing total choosability of G.     

$$$$-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.     

Improved approximations for buy-at-bul and shallow-light $$$$-Steiner trees and $$(,2)$$(,2)-subgraph

In this paper we give improved approximation algorithms for some network design problems. In the bounded-diameter or shallow-light \(k\)-Steiner tree problem (SL\(k\)ST), we are given an undirected graph \(G=(V,E)\) with terminals \(T\subseteq V\) containing a root \(r\in T\), a cost function \(c:E\rightarrow \mathbb {R}^+\), a length function \(\ell :E\rightarrow \mathbb {R}^+\), a bound \(L>0\) and an integer \(k\ge 1\). The goal is to find a minimum \(c\)-cost \(r\)-rooted Steiner tree containing at least \(k\) terminals whose diameter under \(\ell \) metric is at most \(L\). The input to the buy-at-bulk \(k\)-Steiner tree problem (BB\(k\)ST) is similar: graph \(G=(V,E)\), terminals \(T\subseteq V\) containing a root \(r\in T\), cost and length functions \(c,\ell :E\rightarrow \mathbb {R}^+\), and an integer \(k\ge 1\). The goal is to find a minimum total cost \(r\)-rooted Steiner tree \(H\) containing at least \(k\) terminals, where the cost of each edge \(e\) is \(c(e)+\ell (e)\cdot f(e)\) where \(f(e)\) denotes the number of terminals whose path to root in \(H\) contains edge \(e\). We present a bicriteria \((O(\log ^2 n),O(\log n))\)-approximation for SL\(k\)ST: the algorithm finds a \(k\)-Steiner tree with cost at most \(O(\log ^2 n\cdot \text{ opt }^*)\) where \(\text{ opt }^*\) is the cost of an LP relaxation of the problem and diameter at most \(O(L\cdot \log n)\). This improves on the algorithm of Hajiaghayi et al. (2009) (APPROX’06/Algorithmica’09) which had ratio \((O(\log ^4 n), O(\log ^2 n))\). Using this, we obtain an \(O(\log ^3 n)\)-approximation for BB\(k\)ST, which improves upon the \(O(\log ^4 n)\)-approximation of Hajiaghayi et al. (2009). We also consider the problem of finding a minimum cost \(2\)-edge-connected subgraph with at least \(k\) vertices, which is introduced as the \((k,2)\)-subgraph problem in Lau et al. (2009) (STOC’07/SICOMP09). This generalizes some well-studied classical problems such as the \(k\)-MST and the minimum cost \(2\)-edge-connected subgraph problems. We give an \(O(\log n)\)-approximation algorithm for this problem which improves upon the \(O(\log ^2 n)\)-approximation algorithm of Lau et al. (2009).     

Nordhaus–Gaddum type result for the matching number of a graph

For a graph G, \(\alpha '(G)\) is the matching number of G. Let \(k\ge 2\) be an integer, \(K_{n}\) be the complete graph of order n. Assume that \(G_{1}, G_{2}, \ldots , G_{k}\) is a k-decomposition of \(K_{n}\). In this paper, we show that (1)

$$\begin{aligned} \left\lfloor \frac{n}{2}\right\rfloor \le \sum _{i=1}^{k} \alpha '(G_{i})\le k\left\lfloor \frac{n}{2}\right\rfloor . \end{aligned}$$

(2) If each \(G_{i}\) is non-empty for \(i = 1, \ldots , k\), then for \(n\ge 6k\),

$$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n+k-1}{2}\right\rfloor . \end{aligned}$$

(3) If \(G_{i}\) has no isolated vertices for \(i = 1, \ldots , k\), then for \(n\ge 8k\),

$$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n}{2}\right\rfloor +k. \end{aligned}$$

The bounds in (1), (2) and (3) are sharp. (4) When \(k= 2\), we characterize all the extremal graphs which attain the lower bounds in (1), (2) and (3), respectively.