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

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

Further results on the reciprocal degree distance of graphs

The reciprocal degree distance of a simple connected graph \(G=(V_G, E_G)\) is defined as \(\bar{R}(G)=\sum _{u,v \in V_G}(\delta _G(u)+\delta _G(v))\frac{1}{d_G(u,v)}\), where \(\delta _G(u)\) is the vertex degree of \(u\), and \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G\). The reciprocal degree distance is an additive weight version of the Harary index, which is defined as \(H(G)=\sum _{u,v \in V_G}\frac{1}{d_G(u,v)}\). In this paper, the extremal \(\bar{R}\)-values on several types of important graphs are considered. The graph with the maximum \(\bar{R}\)-value among all the simple connected graphs of diameter \(d\) is determined. Among the connected bipartite graphs of order \(n\), the graph with a given matching number (resp. vertex connectivity) having the maximum \(\bar{R}\)-value is characterized. Finally, sharp upper bounds on \(\bar{R}\)-value among all simple connected outerplanar (resp. planar) graphs are determined.     

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.     

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.     

Equality in a bound that relates the size and the restrained domination number of a graph

Let \(G=(V,E)\) be a graph. A set \(S\subseteq V\) is a restrained dominating set if every vertex in \(V-S\) is adjacent to a vertex in \(S\) and to a vertex in \(V-S\). The restrained domination number of \(G\), denoted \(\gamma _{r}(G)\), is the smallest cardinality of a restrained dominating set of \(G\). The best possible upper bound \(q(n,k)\) is established in Joubert (Discrete Appl Math 161:829–837, 2013) on the size \(m(G)\) of a graph \(G\) with a given order \(n \ge 5\) and restrained domination number \(k \in \{3, \ldots , n-2\}\). We extend this result to include the cases \(k=1,2,n\), and characterize graphs \(G\) of order \(n \ge 1\) and restrained domination number \(k \in \{1,\dots , n-2,n\}\) for which \(m(G)=q(n,k)\).     

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.     

A simplex like approach based on star sets for recognizing convex-QP adverse graphs

A graph \(G\) with convex-\(QP\) stability number (or simply a convex-\(QP\) graph) is a graph for which the stability number is equal to the optimal value of a convex quadratic program, say \(P(G)\). There are polynomial-time procedures to recognize convex-\(QP\) graphs, except when the graph \(G\) is adverse or contains an adverse subgraph (that is, a non complete graph, without isolated vertices, such that the least eigenvalue of its adjacency matrix and the optimal value of \(P(G)\) are both integer and none of them changes when the neighborhood of any vertex of \(G\) is deleted). In this paper, from a characterization of convex-\(QP\) graphs based on star sets associated to the least eigenvalue of its adjacency matrix, a simplex-like algorithm for the recognition of convex-\(QP\) adverse graphs is introduced.     

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

Some extremal properties of the multiplicatively weighted Harary index of a graph

Let \(G=(V_G, E_G)\) be a simple connected graph. The multiplicatively weighted Harary index of \(G\) is defined as \(H_M(G)=\sum _{\{u,v\}\subseteq V_G}\delta _G(u)\delta _G(v)\frac{1}{d_G(u,v)},\) where \(\delta _G(u)\) is the vertex degree of \(u\) and \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G.\) This novel invariant is in fact the modification of the Harary index in which the contributions of vertex pairs are weighted by the product of their degrees. Deng et al. (J Comb Optim 2014, doi: 10.1007/s10878-013-9698-5) determined the extremal values on \(H_M\) of graphs among \(n\)-vertex trees (resp. unicyclic graphs). In this paper, as a continuance of it, the monotonicity of \(H_M(G)\) under some graph transformations were studied. Using these nice mathematical properties, the extremal graphs among \(n\)-vertex trees with given graphic parameters, such as pendants, matching number, domination number, diameter, vertex bipartition, et al. are characterized, respectively. Some sharp upper bounds on the multiplicatively weighted Harary index of trees with given parameters are determined.     

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

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

More bounds for the Grundy number of graphs

A coloring of a graph \(G=(V,E)\) is a partition \(\{V_1, V_2, \ldots , V_k\}\) of V into independent sets or color classes. A vertex \(v\in V_i\) is a Grundy vertex if it is adjacent to at least one vertex in each color class \(V_j\) for every \(j<i\). A coloring is a Grundy coloring if every vertex is a Grundy vertex, and the Grundy number \(\Gamma (G)\) of a graph G is the maximum number of colors in a Grundy coloring. We provide two new upper bounds on Grundy number of a graph and a stronger version of the well-known Nordhaus-Gaddum theorem. In addition, we give a new characterization for a \(\{P_{4}, C_4\}\)-free graph by supporting a conjecture of Zaker, which says that \(\Gamma (G)\ge \delta (G)+1\) for any \(C_4\)-free graph G.     

Atoms of cyclic edge connectivity in regular graphs

A cyclic edge-cut of a connected graph \(G\) is an edge set, the removal of which separates two cycles. If \(G\) has a cyclic edge-cut, then it is called cyclically separable. For a cyclically separable graph \(G\), the cyclic edge connectivity of a graph \(G\), denoted by \(\lambda _c(G)\), is the minimum cardinality over all cyclic edge cuts. Let \(X\) be a non-empty proper subset of \(V(G)\). If \([X,\overline{X}]=\{xy\in E(G)\ |\ x\in X, y\in \overline{X}\}\) is a minimum cyclic edge cut of \(G\), then \(X\) is called a \(\lambda _c\) -fragment of \(G\). A \(\lambda _c\)-fragment with minimum cardinality is called a \(\lambda _c\) -atom. Let \(G\) be a \(k (k\ge 3)\)-regular cyclically separable graph with \(\lambda _c(G)<g(k-2)\), where \(g\) is the girth of \(G\). A combination of the results of Nedela and Skoviera (Math Slovaca 45:481–499, 1995) and Xu and Liu (Australas J Combin 30:41–49, 2004) gives that if \(k\ne 5\) then any two distinct \(\lambda _c\)-atoms of \(G\) are disjoint. The remaining case of \(k=5\) is considered in this paper, and a new proof for Nedela and ?koviera’s result is also given. As a result, we obtain the following result. If \(X\) and \(X'\) are two distinct \(\lambda _c\)-atoms of \(G\) such that \(X\cap X'\ne \emptyset \), then \((k,g)=(5,3)\) and \(G[X]\cong K_4\). As corollaries, several previous results are easily obtained.     

A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles

Let \(G=(V,E)\) be a graph and \(\phi \) be a total \(k\)-coloring of \(G\) using the color set \(\{1,\ldots , k\}\). Let \(\sum _\phi (u)\) denote the sum of the color of the vertex \(u\) and the colors of all incident edges of \(u\). A \(k\)-neighbor sum distinguishing total coloring of \(G\) is a total \(k\)-coloring of \(G\) such that for each edge \(uv\in E(G)\), \(\sum _\phi (u)\ne \sum _\phi (v)\). By \(\chi ^{''}_{nsd}(G)\), we denote the smallest value \(k\) in such a coloring of \(G\). Pil?niak and Wo?niak first introduced this coloring and conjectured that \(\chi _{nsd}^{''}(G)\le \Delta (G)+3\) for any simple graph \(G\). In this paper, we prove that the conjecture holds for planar graphs without intersecting triangles with \(\Delta (G)\ge 7\). Moreover, we also show that \(\chi _{nsd}^{''}(G)\le \Delta (G)+2\) for planar graphs without intersecting triangles with \(\Delta (G) \ge 9\). Our approach is based on the Combinatorial Nullstellensatz and the discharging method.     

Further properties on the degree distance of graphs

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

An improved bound on 2-distance coloring plane graphs with girth 5

A vertex coloring is called \(2\)-distance if any two vertices at distance at most \(2\) from each other get different colors. The minimum number of colors in 2-distance colorings of \(G\) is its 2-distance chromatic number, denoted by \(\chi _2(G)\). Let \(G\) be a plane graph with girth at least \(5\). In this paper, we prove that \(\chi _2(G)\le \Delta +8\) for arbitrary \(\Delta (G)\), which partially improves some known results.     

Total and paired domination numbers of $$C_m$$ bundles over a cycle $$C_n$$Cn

Let \(G=(V,E)\) be a simple graph without isolated vertices. A set \(S\) of vertices is a total dominating set of a graph \(G\) if every vertex of \(G\) is adjacent to some vertex in \(S\). A paired dominating set of \(G\) is a dominating set whose induced subgraph has a perfect matching. The minimum cardinality of a total dominating set (respectively, a paired dominating set) is the total domination number (respectively, the paired domination number). Hu and Xu (J Combin Optim 27(2):369–378, 2014) computed the exact values of total and paired domination numbers of Cartesian product \(C_n\square C_m\) for \(m=3,4\). Graph bundles generalize the notions of covering graphs and Cartesian products. In this paper, we generalize these results given in Hu and Xu (J Combin Optim 27(2):369–378, 2014) to graph bundle and compute the total domination number and the paired domination number of \(C_m\) bundles over a cycle \(C_n\) for \(m=3,4\). Moreover, we give the exact value for the total domination number of Cartesian product \(C_n\square C_5\) and some upper bounds of \(C_m\) bundles over a cycle \(C_n\) where \(m\ge 5\).     

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

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.