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.     

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.     

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

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

Algebraic and combinatorial properties of ideals and algebras of uniform clutters of TDI systems

Let \(\mathcal{C}\) be a uniform clutter and let A be the incidence matrix of \(\mathcal{C}\). We denote the column vectors of A by v ₁,…,v _q . Under certain conditions we prove that \(\mathcal{C}\) is vertex critical. If \(\mathcal{C}\) satisfies the max-flow min-cut property, we prove that A diagonalizes over ? to an identity matrix and that v ₁,…,v _q form a Hilbert basis. We also prove that if \(\mathcal{C}\) has a perfect matching such that \(\mathcal{C}\) has the packing property and its vertex covering number is equal to 2, then A diagonalizes over ? to an identity matrix. If A is a balanced matrix we prove that any regular triangulation of the cone generated by v ₁,…,v _q is unimodular. Some examples are presented to show that our results only hold for uniform clutters. These results are closely related to certain algebraic properties, such as the normality or torsion-freeness, of blowup algebras of edge ideals and to finitely generated abelian groups. They are also related to the theory of Gröbner bases of toric ideals and to Ehrhart rings.     

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.     

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

On the odd girth and the circular chromatic number of generalized Petersen graphs

A class \(\mathcal{G}\) of simple graphs is said to be girth-closed (odd-girth-closed) if for any positive integer g there exists a graph \(\mathrm {G} \in \mathcal{G}\) such that the girth (odd-girth) of \(\mathrm {G}\) is \(\ge g\). A girth-closed (odd-girth-closed) class \(\mathcal{G}\) of graphs is said to be pentagonal (odd-pentagonal) if there exists a positive integer \(g^*\) depending on \(\mathcal{G}\) such that any graph \(\mathrm {G} \in \mathcal{G}\) whose girth (odd-girth) is greater than \(g^*\) admits a homomorphism to the five cycle (i.e. is \(\mathrm {C}_{_{5}}\)-colourable). Although, the question “Is the class of simple 3-regular graphs pentagonal?” proposed by Ne?et?il (Taiwan J Math 3:381–423, 1999) is still a central open problem, Gebleh (Theorems and computations in circular colourings of graphs, 2007) has shown that there exists an odd-girth-closed subclass of simple 3-regular graphs which is not odd-pentagonal. In this article, motivated by the conjecture that the class of generalized Petersen graphs is odd-pentagonal, we show that finding the odd girth of generalized Petersen graphs can be transformed to an integer programming problem, and using the combinatorial and number theoretic properties of this problem, we explicitly compute the odd girth of such graphs, showing that the class is odd-girth-closed. Also, we obtain upper and lower bounds for the circular chromatic number of these graphs, and as a consequence, we show that the subclass containing generalized Petersen graphs \(\mathrm {Pet}(n,k)\) for which either k is even, n is odd and \(n\mathop {\equiv }\limits ^{k-1}\pm 2\) or both n and k are odd and \(n\ge 5k\) is odd-pentagonal. This in particular shows the existence of nontrivial odd-pentagonal subclasses of 3-regular simple graphs.     

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

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.     

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

Nordhaus–Gaddum bounds for total Roman domination

A Nordhaus–Gaddum-type result is a lower or an upper bound on the sum or the product of a parameter of a graph and its complement. In this paper we continue the study of Nordhaus–Gaddum bounds for the total Roman domination number \(\gamma _{tR}\). Let G be a graph on n vertices and let \(\overline{G}\) denote the complement of G, and let \(\delta ^*(G)\) denote the minimum degree among all vertices in G and \(\overline{G}\). For \(\delta ^*(G)\ge 1\), we show that (i) if G and \(\overline{G}\) are connected, then \((\gamma _{tR}(G)-4)(\gamma _{tR}(\overline{G})-4)\le 4\delta ^*(G)-4\), (ii) if \(\gamma _{tR}(G), \gamma _{tR}(\overline{G})\ge 8\), then \(\gamma _{tR}(G)+\gamma _{tR}(\overline{G})\le 2\delta ^*(G)+5\) and (iii) \(\gamma _{tR}(G)+\gamma _{tR}(\overline{G})\le n+5\) and \(\gamma _{tR}(G)\gamma _{tR}(\overline{G})\le 6n-5\).     

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.     

Special cases of the quadratic shortest path problem

The quadratic shortest path problem (QSPP) is the problem of finding a path with prespecified start vertex s and end vertex t in a digraph such that the sum of weights of arcs and the sum of interaction costs over all pairs of arcs on the path is minimized. We first consider a variant of the QSPP known as the adjacent QSPP. It was recently proven that the adjacent QSPP on cyclic digraphs cannot be approximated unless \(\hbox {P}=\hbox {NP}\). Here, we give a simple proof for the same result. We also show that if the quadratic cost matrix is a symmetric weak sum matrix and all s–t paths have the same length, then an optimal solution for the QSPP can be obtained by solving the corresponding instance of the shortest path problem. Similarly, it is shown that the QSPP with a symmetric product cost matrix is solvable in polynomial time. Further, we provide sufficient and necessary conditions for a QSPP instance on a complete symmetric digraph with four vertices to be linearizable. We also characterize linearizable QSPP instances on complete symmetric digraphs with more than four vertices. Finally, we derive an algorithm that examines whether a QSPP instance on the directed grid graph \(G_{pq}\) (\(p,q\ge 2\)) is linearizable. The complexity of this algorithm is \({\mathcal {O}(p^{3}q^{2}+p^{2}q^{3})}\).     

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

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

Distance domination in graphs with given minimum and maximum degree

For an integer \(k \ge 1\), a distance k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V(G) is at distance at most k from some vertex of S. The distance k-domination number \(\gamma _k(G)\) of G is the minimum cardinality of a distance k-dominating set of G. In this paper, we establish an upper bound on the distance k-domination number of a graph in terms of its order, minimum degree and maximum degree. We prove that for \(k \ge 2\), if G is a connected graph with minimum degree \(\delta \ge 2\) and maximum degree \(\Delta \) and of order \(n \ge \Delta + k - 1\), then \(\gamma _k(G) \le \frac{n + \delta - \Delta }{\delta + k - 1}\). This result improves existing known results.     

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

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.     

Upper bounds for adjacent vertex-distinguishing edge coloring

An adjacent vertex-distinguishing edge coloring of a graph is a proper edge coloring such that no pair of adjacent vertices meets the same set of colors. The adjacent vertex-distinguishing edge chromatic number is the minimum number of colors required for an adjacent vertex-distinguishing edge coloring, denoted as \(\chi '_{as}(G)\). In this paper, we prove that for a connected graph G with maximum degree \(\Delta \ge 3\), \(\chi '_{as}(G)\le 3\Delta -1\), which proves the previous upper bound. We also prove that for a graph G with maximum degree \(\Delta \ge 458\) and minimum degree \(\delta \ge 8\sqrt{\Delta ln \Delta }\), \(\chi '_{as}(G)\le \Delta +1+5\sqrt{\Delta ln \Delta }\).     

Bounds on the domination number of a digraph

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of D, denoted by \(\gamma (D)\), is the minimum cardinality of a dominating set of D. The Slater number \(s\ell (D)\) is the smallest integer t such that t added to the sum of the first t terms of the non-increasing out-degree sequence of D is at least as large as the order of D. For any digraph D of order n with maximum out-degree \(\Delta ^+\), it is known that \(\gamma (D)\ge \lceil n/(\Delta ^++1)\rceil \). We show that \(\gamma (D)\ge s\ell (D)\ge \lceil n/(\Delta ^++1)\rceil \) and the difference between \(s\ell (D)\) and \(\lceil n/(\Delta ^++1)\rceil \) can be arbitrarily large. In particular, for an oriented tree T of order n with \(n_0\) vertices of out-degree 0, we show that \((n-n_0+1)/2\le s\ell (T)\le \gamma (T)\le 2s\ell (T)-1\) and moreover, each value between the lower bound \(s\ell (T)\) and the upper bound \(2s\ell (T)-1\) is attainable by \(\gamma (T)\) for some oriented trees. Further, we characterize the oriented trees T for which \(s\ell (T)=(n-n_0+1)/2\) hold and show that the difference between \(s\ell (T)\) and \((n-n_0+1)/2\) can be arbitrarily large. Some other elementary properties involving the Slater number are also presented.