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.     

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.     

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.     

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

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.     

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

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

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

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

Neighbor sum distinguishing list total coloring of subcubic graphs

Let \(G=(V, E)\) be a simple graph and denote the set of edges incident to a vertex v by E(v). The neighbor sum distinguishing (NSD) total choice number of G, denoted by \(\mathrm{ch}_{\Sigma }^{t}(G)\), is the smallest integer k such that, after assigning each \(z\in V\cup E\) a set L(z) of k real numbers, G has a total coloring \(\phi \) satisfying \(\phi (z)\in L(z)\) for each \(z\in V\cup E\) and \(\sum _{z\in E(u)\cup \{u\}}\phi (z)\ne \sum _{z\in E(v)\cup \{v\}}\phi (z)\) for each \(uv\in E\). In this paper, we propose some reducible configurations of NSD list total coloring for general graphs by applying the Combinatorial Nullstellensatz. As an application, we present that \(\mathrm{ch}^{t}_{\Sigma }(G)\le \Delta (G)+3\) for every subcubic graph G.     

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

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.     

Total and forcing total edge-to-vertex monophonic number of a graph

For a connected graph \(G = \left( V,E\right) \), a set \(S\subseteq E(G)\) is called a total edge-to-vertex monophonic set of a connected graph G if the subgraph induced by S has no isolated edges. The total edge-to-vertex monophonic number \(m_{tev}(G)\) of G is the minimum cardinality of its total edge-to-vertex monophonic set of G. The total edge-to-vertex monophonic number of certain classes of graphs is determined and some of its general properties are studied. Connected graphs of size \(q \ge 3 \) with total edge-to-vertex monophonic number q is characterized. It is shown that for positive integers \(r_{m},d_{m}\) and \(l\ge 4\) with \(r_{m}< d_{m} \le 2 r_{m}\), there exists a connected graph G with \(\textit{rad}_ {m} G = r_{m}\), \(\textit{diam}_ {m} G = d_{m}\) and \(m_{tev}(G) = l\) and also shown that for every integers a and b with \(2 \le a \le b\), there exists a connected graph G such that \( m_{ev}\left( G\right) = b\) and \(m_{tev}(G) = a + b\). A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing total edge-to-vertex monophonic number of S, denoted by \(f_{tev}(S)\) is the cardinality of a minimum forcing subset of S. The forcing total edge-to-vertex monophonic number of G, denoted by \(f_{tev}(G) = \textit{min}\{f_{tev}(S)\}\), where the minimum is taken over all total edge-to-vertex monophonic set S in G. The forcing total edge-to-vertex monophonic number of certain classes of graphs are determined and some of its general properties are studied. It is shown that for every integers a and b with \(0 \le a \le b\) and \(b \ge 2\), there exists a connected graph G such that \(f_{tev}(G) = a\) and \( m _{tev}(G) = b\), where \( f _{tev}(G)\) is the forcing total edge-to-vertex monophonic number of G.     

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.     

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.     

Minimum 2-distance coloring of planar graphs and channel assignment

A 2-distance k-coloring of a graph G is a proper k-coloring such that any two vertices at distance two get different colors. \(\chi _{2}(G)\)=min{k|G has a 2-distance k-coloring}. Wegner conjectured that for each planar graph G with maximum degree \(\Delta \), \(\chi _2(G) \le 7\) if \(\Delta \le 3\), \(\chi _2(G) \le \Delta +5\) if \(4\le \Delta \le 7\) and \(\chi _2(G) \le \lfloor \frac{3\Delta }{2}\rfloor +1\) if \(\Delta \ge 8\). In this paper, we prove that: (1) If G is a planar graph with maximum degree \(\Delta \le 5\), then \(\chi _{2}(G)\le 20\); (2) If G is a planar graph with maximum degree \(\Delta \ge 6\), then \(\chi _{2}(G)\le 5\Delta -7\).     

Neighbor-sum-distinguishing edge choosability of subcubic graphs

A graph G is said to be neighbor-sum-distinguishing edge k-choose if, for every list L of colors such that L(e) is a set of k positive real numbers for every edge e, there exists a proper edge coloring which assigns to each edge a color from its list so that for each pair of adjacent vertices u and v the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\) denote the smallest integer k such that G is neighbor-sum-distinguishing edge k-choose. In this paper, we prove that if G is a subcubic graph with the maximum average degree mad(G), then (1) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 7\); (2) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 6\) if \(\hbox {mad}(G)<\frac{36}{13}\); (3) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 5\) if \(\hbox {mad}(G)<\frac{5}{2}\).     

On the difference of two generalized connectivities of a graph

The concept of k-connectivity \(\kappa '_{k}(G)\) of a graph G, introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. Another generalized connectivity of a graph G, named the generalized k-connectivity \(\kappa _{k}(G)\), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of these two parameters by showing that for a connected graph G of order n, if \(\kappa '_k(G)\ne n-k+1\) where \(k\ge 3\), then \(0\le \kappa '_k(G)-\kappa _k(G)\le n-k-1\); otherwise, \(-\lfloor \frac{k}{2}\rfloor +1\le \kappa '_k(G)-\kappa _k(G)\le n-k\). Moreover, all of these bounds are sharp. Some specific study is focused for the case \(k=3\). As results, we characterize the graphs with \(\kappa '_3(G)=\kappa _3(G)=t\) for \(t\in \{1, n-3, n-2\}\), and give a necessary condition for \(\kappa '_3(G)=\kappa _3(G)\) by showing that for a connected graph G of order n and size m, if \(\kappa '_3(G)=\kappa _3(G)=t\) where \(1\le t\le n-3\), then \(m\le {n-2\atopwithdelims ()2}+2t\). Moreover, the unique extremal graph is given for the equality to hold.     

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

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