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.     

Signed mixed Roman domination numbers in graphs

Let \(G = (V;E)\) be a simple graph with vertex set \(V\) and edge set \(E\). A signed mixed Roman dominating function (SMRDF) of \(G\) is a function \(f: V\cup E\rightarrow \{-1,1,2\}\) satisfying the conditions that (i) \(\sum _{y\in N_m[x]}f(y)\ge 1\) for each \(x\in V\cup E\), where \(N_m[x]\) is the set, called mixed closed neighborhood of \(x\), consists of \(x\) and the elements of \(V\cup E\) adjacent or incident to \(x\) (ii) every element \(x\in V\cup E\) for which \(f(x) = -1\) is adjacent or incident to at least one element \(y\in V\cup E\) for which \(f(y) = 2\). The weight of a SMRDF \(f\) is \(\omega (f)=\sum _{x\in V\cup E}f(x)\). The signed mixed Roman domination number \(\gamma _{sR}^*(G)\) of \(G\) is the minimum weight of a SMRDF of \(G\). In this paper we initiate the study of the signed mixed Roman domination number and we present bounds for this parameter. In particular, we determine this parameter for some classes of 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}\).     

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.     

Disjunctive total domination in graphs

Let \(G\) be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, \(\gamma _t(G)\). A set \(S\) of vertices in \(G\) is a disjunctive total dominating set of \(G\) if every vertex is adjacent to a vertex of \(S\) or has at least two vertices in \(S\) at distance \(2\) from it. The disjunctive total domination number, \(\gamma ^d_t(G)\), is the minimum cardinality of such a set. We observe that \(\gamma ^d_t(G) \le \gamma _t(G)\). We prove that if \(G\) is a connected graph of order \(n \ge 8\), then \(\gamma ^d_t(G) \le 2(n-1)/3\) and we characterize the extremal graphs. It is known that if \(G\) is a connected claw-free graph of order \(n\), then \(\gamma _t(G) \le 2n/3\) and this upper bound is tight for arbitrarily large \(n\). We show this upper bound can be improved significantly for the disjunctive total domination number. We show that if \(G\) is a connected claw-free graph of order \(n > 14\), then \(\gamma ^d_t(G) \le 4n/7\) and we characterize the graphs achieving equality in this bound.     

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.     

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.     

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.     

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

An $$O(n\log n)$$ algorithm for finding edge span of cacti

Let \(G=(V,E)\) be a nonempty graph and \(\xi :E\rightarrow \mathbb {N}\) be a function. In the paper we study the computational complexity of the problem of finding vertex colorings \(c\) of \(G\) such that:

1. (1)
   \(|c(u)-c(v)|\ge \xi (uv)\) for each edge \(uv\in E\);
    
2. (2)
   the edge span of \(c\), i.e. \(\max \{|c(u)-c(v)|:uv\in E\}\), is minimal.
    

We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for cycles and bipartite graphs. Next, we use the last two results to construct an algorithm that solves the problem for a given cactus \(G\) in \(O(n\log n)\) time, where \(n\) is the number of vertices of \(G\).

     

On the vertex cover $$P_3$$ problem parameterized by treewidth

Consider a graph G. A subset of vertices, F, is called a vertex cover \(P_t\) (\(VCP_t\)) set if every path of order t contains at least one vertex in F. Finding a minimum \(VCP_t\) set in a graph is is NP-hard for any integer \(t\ge 2\) and is called the \(MVCP_3\) problem. In this paper, we study the parameterized algorithms for the \(MVCP_3\) problem when the underlying graph G is parameterized by the treewidth. Given an n-vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time \(4^{p}\cdot n^{O(1)}\) for the \(MVCP_3\) problem. Moreover, we show that for the \(MVCP_3\) problem on planar graphs, there is a subexponential parameterized algorithm running in time \(2^{O(\sqrt{k})}\cdot n^{O(1)}\) where k is the size of the optimal solution.     

Algorithms for connected <Emphasis Type="Italic">p</Emphasis>-centdian problem on block graphs

We consider the facility location problem of locating a set \(X_p\) of p facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set \(X_p\) is connected. Two problems on a block graph G are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of G to \(X_p\), another problem is to minimize the maximum distance from each vertex that is not in \(X_p\) to \(X_p\) and, at the same time, to minimize the sum of its distances from all vertices of G to \(X_p\). We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in \(O(n^2)\) time, where n is the number of vertices of the block graph G.     

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

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

Kernelization and randomized Parameterized algorithms for Co-path Set problem

The \(L(p, q)\)-labeling arises from the optimization problem of channel assignment in communication networks. For two non-negative integers \(p\) and \(q\), an \(L(p,q)\)-labeling \(c\) of a graph \(G\) is an assignment of non-negative integers to the vertices of \(G\) such that adjacent vertices are labelled using colors at least \(p\) apart, and vertices with distance two are labelled using colors at least \(q\) apart. In this paper we establish a connection between an \(L(p, q)\)-labeling and an integer tension of a graph, which extends a corresponding result for planar graphs. This connection provides us with an effective way to design an \(L(p, q)\)-labeling for non-planar graphs, in particular for graphs embedded on torus, by choosing a proper cycle basis consisting of facial cycles and some specified cycles of the embedded graph. As an application, we use this method to optimize the edge span for the Cartesian product of two cycles.     

The entire choosability of plane graphs

A plane graph \(G\) is entirely \(k\)-choosable if, for every list \(L\) of colors satisfying \(L(x)=k\) for all \(x\in V(G)\cup E(G) \cup F(G)\), there exists a coloring which assigns to each vertex, each edge and each face a color from its list so that any adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph \(G\) with maximum degree \(\Delta \ge 12\) is entirely \((\Delta +2)\)-choosable. In this paper, we improve this result by replacing 12 by 10.     

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.     

The extremal spectral radii of $$$$-uniform supertrees

In this paper, we study some extremal problems of three kinds of spectral radii of \(k\)-uniform hypergraphs (the adjacency spectral radius, the signless Laplacian spectral radius and the incidence \(Q\)-spectral radius). We call a connected and acyclic \(k\)-uniform hypergraph a supertree. We introduce the operation of “moving edges” for hypergraphs, together with the two special cases of this operation: the edge-releasing operation and the total grafting operation. By studying the perturbation of these kinds of spectral radii of hypergraphs under these operations, we prove that for all these three kinds of spectral radii, the hyperstar \(\mathcal {S}_{n,k}\) attains uniquely the maximum spectral radius among all \(k\)-uniform supertrees on \(n\) vertices. We also determine the unique \(k\)-uniform supertree on \(n\) vertices with the second largest spectral radius (for these three kinds of spectral radii). We also prove that for all these three kinds of spectral radii, the loose path \(\mathcal {P}_{n,k}\) attains uniquely the minimum spectral radius among all \(k\)-th power hypertrees of \(n\) vertices. Some bounds on the incidence \(Q\)-spectral radius are given. The relation between the incidence \(Q\)-spectral radius and the spectral radius of the matrix product of the incidence matrix and its transpose is discussed.     

On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph \(G=(V,E)\), the complete width of G is the minimum k such that there exist k independent sets \(\mathtt {N}_i\subseteq V\), \(1\le i\le k\), such that the graph \(G'\) obtained from G by adding some new edges between certain vertices inside the sets \(\mathtt {N}_i\), \(1\le i\le k\), is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on \(3K_2\)-free bipartite graphs and polynomially solvable on \(2K_2\)-free bipartite graphs and on \((2K_2,C_4)\)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on \(\overline{3K_2}\)-free co-bipartite graphs and polynomially solvable on \(C_4\)-free co-bipartite graphs and on \((2K_2, C_4)\)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most \(2^k\) vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most \(2^k\) vertices. Finally we determine all graphs of small complete width \(k\le 3\).     

The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance

This paper addresses the problem of modifying the edge lengths of a tree in minimum total cost such that a prespecified vertex becomes the 1-center of the perturbed tree. This problem is called the inverse 1-center problem on trees. We focus on the problem under Chebyshev norm and Hamming distance. From special properties of the objective functions, we can develop combinatorial algorithms to solve the problem. Precisely, if there does not exist any vertex coinciding with the prespecified vertex during the modification of edge lengths, the problem under Chebyshev norm or bottleneck Hamming distance is solvable in \(O(n\log n)\) time, where \(n+1\) is the number of vertices of the tree. Dropping this condition, the problem can be solved in \(O(n^{2})\) time.