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.     

Semi-online scheduling on two uniform machines with the known largest size

This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s _j the speed of each machine, j=1,2. Assume 0<s ₁≤s ₂, and let s=s ₂/s ₁ be the speed ratio. First, for the speed ratio \(s\in [1,\sqrt{2}]\), we present an optimal semi-online algorithm \(\mathcal{LSMP}\) with the competitive ratio \(\mathrm{max}\{\frac {2(s+1)}{2s+1},s\}\). Second, we present a semi-online algorithm \(\mathcal{HSMP}\). And for \(s\in(\sqrt{2},1+\sqrt{3})\), the competitive ratio of \(\mathcal{HSMP}\) is strictly smaller than that of the online algorithm \(\mathcal{LS}\). Finally, for the speed ratio s≥s ^*≈3.715, we show that the known largest size cannot help us to design a semi-online algorithm with the competitive ratio strictly smaller than that of \(\mathcal{LS}\). Moreover, we show a lower bound for \(s\in(\sqrt{2},s^{*})\).     

Perfect graphs involving semitotal and semipaired domination

Let G be a graph with vertex set V and no isolated vertices, and let S be a dominating set of V. The set S is a semitotal dominating set of G if every vertex in S is within distance 2 of another vertex of S. And, S is a semipaired dominating set of G if S can be partitioned into 2-element subsets such that the vertices in each 2-set are at most distance two apart. The semitotal domination number \(\gamma _\mathrm{t2}(G)\) is the minimum cardinality of a semitotal dominating set of G, and the semipaired domination number \(\gamma _\mathrm{pr2}(G)\) is the minimum cardinality of a semipaired dominating set of G. For a graph without isolated vertices, the domination number \(\gamma (G)\), the total domination \(\gamma _t(G)\), and the paired domination number \(\gamma _\mathrm{pr}(G)\) are related to the semitotal and semipaired domination numbers by the following inequalities: \(\gamma (G) \le \gamma _\mathrm{t2}(G) \le \gamma _t(G) \le \gamma _\mathrm{pr}(G)\) and \(\gamma (G) \le \gamma _\mathrm{t2}(G) \le \gamma _\mathrm{pr2}(G) \le \gamma _\mathrm{pr}(G) \le 2\gamma (G)\). Given two graph parameters \(\mu \) and \(\psi \) related by a simple inequality \(\mu (G) \le \psi (G)\) for every graph G having no isolated vertices, a graph is \((\mu ,\psi )\)-perfect if every induced subgraph H with no isolated vertices satisfies \(\mu (H) = \psi (H)\). Alvarado et al. (Discrete Math 338:1424–1431, 2015) consider classes of \((\mu ,\psi )\)-perfect graphs, where \(\mu \) and \(\psi \) are domination parameters including \(\gamma \), \(\gamma _t\) and \(\gamma _\mathrm{pr}\). We study classes of perfect graphs for the possible combinations of parameters in the inequalities when \(\gamma _\mathrm{t2}\) and \(\gamma _\mathrm{pr2}\) are included in the mix. Our results are characterizations of several such classes in terms of their minimal forbidden induced subgraphs.     

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

On the b-coloring of tight graphs

A coloring c of a graph \(G=(V,E)\) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least \(m-1\). A graph G is tight if it has exactly m(G) vertices of degree \(m(G)-1\), and any other vertex has degree at most \(m(G)-2\). In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least \(m(G)-1\) and characterize the graphs G such that \(b(G)=m(G)\). Lin and Chang (2013) conjectured that the b-chromatic number of any graph in \(\mathcal {B}_{m}\) is m or \(m-1\) where \(\mathcal {B}_{m}\) is the class of tight bipartite graphs \((D,D{^\prime })\) of girth 6 such that D is the set of vertices of degree \(m-1\). We verify the conjecture of Lin and Chang for some subclass of \(\mathcal {B}_{m}\), and we give a lower bound for any graph in \(\mathcal {B}_{m}\).     

On zero-sum $$\mathbb {Z}_{2j}^k$$-magic graphs

Let \(G = (V,E)\) be a finite graph and let \((\mathbb {A},+)\) be an abelian group with identity 0. Then G is \(\mathbb {A}\)-magic if and only if there exists a function \(\phi \) from E into \(\mathbb {A} - \{0\}\) such that for some \(c \in \mathbb {A}, \sum _{e \in E(v)} \phi (e) = c\) for every \(v \in V\), where E(v) is the set of edges incident to v. Additionally, G is zero-sum \(\mathbb {A}\)-magic if and only if \(\phi \) exists such that \(c = 0\). We consider zero-sum \(\mathbb {A}\)-magic labelings of graphs, with particular attention given to \(\mathbb {A} = \mathbb {Z}_{2j}^k\). For \(j \ge 1\), let \(\zeta _{2j}(G)\) be the smallest positive integer c such that G is zero-sum \(\mathbb {Z}_{2j}^c\)-magic if c exists; infinity otherwise. We establish upper bounds on \(\zeta _{2j}(G)\) when \(\zeta _{2j}(G)\) is finite, and show that \(\zeta _{2j}(G)\) is finite for all r-regular \(G, r \ge 2\). Appealing to classical results on the factors of cubic graphs, we prove that \(\zeta _4(G) \le 2\) for a cubic graph G, with equality if and only if G has no 1-factor. We discuss the problem of classifying cubic graphs according to the collection of finite abelian groups for which they are zero-sum group-magic.     

Paired-domination number of claw-free odd-regular graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph, denoted by \(\gamma _{pr}(G)\). Let G be a connected \(\{K_{1,3}, K_{4}-e\}\)-free cubic graph of order n. We show that \(\gamma _{pr}(G)\le \frac{10n+6}{27}\) if G is \(C_{4}\)-free and that \(\gamma _{pr}(G)\le \frac{n}{3}+\frac{n+6}{9(\lceil \frac{3}{4}(g_o+1)\rceil +1)}\) if G is \(\{C_{4}, C_{6}, C_{10}, \ldots , C_{2g_o}\}\)-free for an odd integer \(g_o\ge 3\); the extremal graphs are characterized; we also show that if G is a 2 -connected, \(\gamma _{pr}(G) = \frac{n}{3} \). Furthermore, if G is a connected \((2k+1)\)-regular \(\{K_{1,3}, K_4-e\}\)-free graph of order n, then \(\gamma _{pr}(G)\le \frac{n}{k+1} \), with equality if and only if \(G=L(F)\), where \(F\cong K_{1, 2k+2}\), or k is even and \(F\cong K_{k+1,k+2}\).     

Roman game domination number of a graph

The Roman game domination number of an undirected graph G is defined by the following game. Players \(\mathcal {A}\) and \(\mathcal {D}\) orient the edges of the graph G alternately, with \(\mathcal {D}\) playing first, until all edges are oriented. Player \(\mathcal {D}\) (frequently called Dominator) tries to minimize the Roman domination number of the resulting digraph, while player \(\mathcal {A}\) (Avoider) tries to maximize it. This game gives a unique number depending only on G, if we suppose that both \(\mathcal {A}\) and \(\mathcal {D}\) play according to their optimal strategies. This number is called the Roman game domination number of G and is denoted by \(\gamma _{Rg}(G)\). In this paper we initiate the study of the Roman game domination number of a graph and we establish some bounds on \(\gamma _{Rg}(G)\). We also determine the Roman game domination number for some classes of graphs.     

First-Fit colorings of graphs with no cycles of a prescribed even length

The First-Fit (or Grundy) chromatic number of a graph G denoted by \(\chi _{{_\mathsf{FF}}}(G)\), is the maximum number of colors used by the First-Fit (greedy) coloring algorithm when applied to G. In this paper we first show that any graph G contains a bipartite subgraph of Grundy number \(\lfloor \chi _{{_\mathsf{FF}}}(G) /2 \rfloor +1\). Using this result we prove that for every \(t\ge 2\) there exists a real number \(c>0\) such that in every graph G on n vertices and without cycles of length 2t, any First-Fit coloring of G uses at most \(cn^{1/t}\) colors. It is noted that for \(t=2\) this bound is the best possible. A compactness conjecture is also proposed concerning the First-Fit chromatic number involving the even girth of graphs.     

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.     

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

Almost separable matrices

An \(m\times n\) matrix \(\mathsf {A}\) with column supports \(\{S_i\}\) is k-separable if the disjunctions \(\bigcup _{i \in \mathcal {K}} S_i\) are all distinct over all sets \(\mathcal {K}\) of cardinality k. While a simple counting bound shows that \(m > k \log _2 n/k\) rows are required for a separable matrix to exist, in fact it is necessary for m to be about a factor of k more than this. In this paper, we consider a weaker definition of ‘almost k-separability’, which requires that the disjunctions are ‘mostly distinct’. We show using a random construction that these matrices exist with \(m = O(k \log n)\) rows, which is optimal for \(k = O(n^{1-\beta })\). Further, by calculating explicit constants, we show how almost separable matrices give new bounds on the rate of nonadaptive group testing.     

List 2-distance $$\varDelta +3$$-coloring of planar graphs without 4,5-cycles

Let \(\chi _2(G)\) and \(\chi _2^l(G)\) be the 2-distance chromatic number and list 2-distance chromatic number of a graph G, respectively. Wegner conjectured that for each planar graph G with maximum degree \(\varDelta \) at least 4, \(\chi _2(G)\le \varDelta +5\) if \(4\le \varDelta \le 7\), and \(\chi _2(G)\le \lfloor \frac{3\varDelta }{2}\rfloor +1\) if \(\varDelta \ge 8\). Let G be a planar graph without 4,5-cycles. We show that if \(\varDelta \ge 26\), then \(\chi _2^l(G)\le \varDelta +3\). There exist planar graphs G with girth \(g(G)=6\) such that \(\chi _2^l(G)=\varDelta +2\) for arbitrarily large \(\varDelta \). In addition, we also discuss the list L(2, 1)-labeling number of G, and prove that \(\lambda _l(G)\le \varDelta +8\) for \(\varDelta \ge 27\).     

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.     

L(2,1)-labelings of the edge-multiplicity-paths-replacement of a graph

An L(2,1)-labeling of a graph \(G\) is an assignment of nonnegative integers to \(V(G)\) such that the difference between labels of adjacent vertices is at least \(2\), and the difference between labels of vertices that are distance two apart is at least 1. The span of an L(2,1)-labeling of a graph \(G\) is the difference between the maximum and minimum integers used by it. The minimum span of an L(2,1)-labeling of \(G\) is denoted by \(\lambda (G)\). This paper focuses on L(2,1)-labelings-number of the edge-multiplicity-paths-replacement \(G(rP_{k})\) of a graph \(G\). In this paper, we obtain that \( r\Delta +1 \le \lambda (G(rP_{5}))\le r\Delta +2\), \(\lambda (G(rP_{k}))= r\Delta +1\) for \(k\ge 6\); and \(\lambda (G(rP_{4}))\le (\Delta +1)r+1\), \(\lambda (G(rP_{3}))\le (\Delta +1)r+\Delta \) for any graph \(G\) with maximum degree \(\Delta \). And the L(2,1)-labelings-numbers of the edge-multiplicity-paths-replacement \(G(rP_{k})\) are completely determined for \(1\le \Delta \le 2\). And we show that the class of graphs \(G(rP_{k})\) with \(k\ge 3 \) satisfies the conjecture: \(\lambda ^{T}_{2}(G)\le \Delta +2\) by Havet and Yu (Technical Report 4650, 2002).     

Algorithmic aspects of <Emphasis Type="Italic">b</Emphasis>-disjunctive domination in graphs

For a fixed integer \(b>1\), a set \(D\subseteq V\) is called a b-disjunctive dominating set of the graph \(G=(V,E)\) if for every vertex \(v\in V{\setminus }D\), v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The Minimum b-Disjunctive Domination Problem (MbDDP) is to find a b-disjunctive dominating set of minimum cardinality. The cardinality of a minimum b-disjunctive dominating set of G is called the b-disjunctive domination number of G, and is denoted by \(\gamma _{b}^{d}(G)\). Given a positive integer k and a graph G, the b-Disjunctive Domination Decision Problem (bDDDP) is to decide whether G has a b-disjunctive dominating set of cardinality at most k. In this paper, we first show that for a proper interval graph G, \(\gamma _{b}^{d}(G)\) is equal to \(\gamma (G)\), the domination number of G for \(b \ge 3\) and observe that \(\gamma _{b}^{d}(G)\) need not be equal to \(\gamma (G)\) for \(b=2\). We then propose a polynomial time algorithm to compute a minimum cardinality b-disjunctive dominating set of a proper interval graph for \(b=2\). Next we tighten the NP-completeness of bDDDP by showing that it remains NP-complete even in chordal graphs. We also propose a \((\ln ({\varDelta }^{2}+(b-1){\varDelta }+b)+1)\)-approximation algorithm for MbDDP, where \({\varDelta }\) is the maximum degree of input graph \(G=(V,E)\) and prove that MbDDP cannot be approximated within \((1-\epsilon ) \ln (|V|)\) for any \(\epsilon >0\) unless NP \(\subseteq \) DTIME\((|V|^{O(\log \log |V|)})\). Finally, we show that MbDDP is APX-complete for bipartite graphs with maximum degree \(\max \{b,4\}\).     

Complexity properties of complementary prisms

The complementary prism \(G\bar{G}\) of a graph G arises from the disjoint union of the graph G and its complement \(\bar{G}\) by adding the edges of a perfect matching joining pairs of corresponding vertices of G and \(\bar{G}\). Haynes, Henning, Slater, and van der Merwe introduced the complementary prism and as a variation of the well-known prism. We study algorithmic/complexity properties of complementary prisms with respect to cliques, independent sets, k-domination, and especially \(P_3\)-convexity. We establish hardness results and identify some efficiently solvable cases.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

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.     

An upper bound on the double Roman domination number

A double Roman dominating function (DRDF) on a graph \(G=(V,E)\) is a function \(f : V \rightarrow \{0, 1, 2, 3\}\) having the property that if \(f(v) = 0\), then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with \(f(w)=3\), and if \(f(v)=1\), then vertex v must have at least one neighbor w with \(f(w)\ge 2\). The weight of a DRDF f is the value \(f(V) = \sum _{u \in V}f(u)\). The double Roman domination number \(\gamma _{dR}(G)\) of a graph G is the minimum weight of a DRDF on G. Beeler et al. (Discrete Appl Math 211:23–29, 2016) observed that every connected graph G having minimum degree at least two satisfies the inequality \(\gamma _{dR}(G)\le \frac{6n}{5}\) and posed the question whether this bound can be improved. In this paper, we settle the question and prove that for any connected graph G of order n with minimum degree at least two, \(\gamma _{dR}(G)\le \frac{8n}{7}\).