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

$$$$-labeling number of Cartesian product of path and cycle

For positive numbers \(j\) and \(k\), an \(L(j,k)\)-labeling \(f\) of \(G\) is an assignment of numbers to vertices of \(G\) such that \(|f(u)-f(v)|\ge j\) if \(d(u,v)=1\), and \(|f(u)-f(v)|\ge k\) if \(d(u,v)=2\). The span of \(f\) is the difference between the maximum and the minimum numbers assigned by \(f\). The \(L(j,k)\)-labeling number of \(G\), denoted by \(\lambda _{j,k}(G)\), is the minimum span over all \(L(j,k)\)-labelings of \(G\). In this article, we completely determine the \(L(j,k)\)-labeling number (\(2j\le k\)) of the Cartesian product of path and cycle.     

Cacti with the smallest,second smallest,and third smallest Gutman index

The Gutman index (also known as Schultz index of the second kind) of a graph \(G\) is defined as \(Gut(G)=\sum \nolimits _{u,v\in V(G)}d(u)d(v)d(u, v)\). A graph \(G\) is called a cactus if each block of \(G\) is either an edge or a cycle. Denote by \(\mathcal {C}(n, k)\) the set of connected cacti possessing \(n\) vertices and \(k\) cycles. In this paper, we give the first three smallest Gutman indices among graphs in \(\mathcal {C}(n, k)\), the corresponding extremal graphs are characterized as well.     

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.     

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.     

$$$$-labeling for brick product graphs

Let \(G=(V, E)\) be a graph. Denote \(d_G(u, v)\) the distance between two vertices \(u\) and \(v\) in \(G\). An \(L(2, 1)\)-labeling of \(G\) is a function \(f: V \rightarrow \{0,1,\cdots \}\) such that for any two vertices \(u\) and \(v\), \(|f(u)-f(v)| \ge 2\) if \(d_G(u, v) = 1\) and \(|f(u)-f(v)| \ge 1\) if \(d_G(u, v) = 2\). The span of \(f\) is the difference between the largest and the smallest number in \(f(V)\). The \(\lambda \)-number of \(G\), denoted \(\lambda (G)\), is the minimum span over all \(L(2,1 )\)-labelings of \(G\). In this article, we confirm Conjecture 6.1 stated in X. Li et al. (J Comb Optim 25:716–736, 2013) in the case when (i) \(\ell \) is even, or (ii) \(\ell \ge 5\) is odd and \(0 \le r \le 8\).     

Improved upper bound for the degenerate and star chromatic numbers of graphs

Let \(G=G(V,E)\) be a graph. A proper coloring of G is a function \(f:V\rightarrow N\) such that \(f(x)\ne f(y)\) for every edge \(xy\in E\). A proper coloring of a graph G such that for every \(k\ge 1\), the union of any k color classes induces a \((k-1)\)-degenerate subgraph is called a degenerate coloring; a proper coloring of a graph with no two-colored \(P_{4}\) is called a star coloring. If a coloring is both degenerate and star, then we call it a degenerate star coloring of graph. The corresponding chromatic number is denoted as \(\chi _{sd}(G)\). In this paper, we employ entropy compression method to obtain a new upper bound \(\chi _{sd}(G)\le \lceil \frac{19}{6}\Delta ^{\frac{3}{2}}+5\Delta \rceil \) for general graph G.     

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.     

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

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.     

The $$(k,\ell )$$-proper index of graphs

A tree T in an edge-colored graph is called a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be an integer with \(2\le k \le n\). For \(S\subseteq V(G)\) and \(|S| \ge 2\), an S-tree is a tree containing the vertices of S in G. A set \(\{T_1,T_2,\ldots ,T_\ell \}\) of S-trees is called internally disjoint if \(E(T_i)\cap E(T_j)=\emptyset \) and \(V(T_i)\cap V(T_j)=S\) for \(1\le i\ne j\le \ell \). For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by \(\kappa (S)\). The k-connectivity \(\kappa _k(G)\) of G is defined by \(\kappa _k(G)=\min \{\kappa (S)\mid S\) is a k-subset of \(V(G)\}\). For a connected graph G of order n and for two integers k and \(\ell \) with \(2\le k\le n\) and \(1\le \ell \le \kappa _k(G)\), the \((k,\ell )\)-proper index \(px_{k,\ell }(G)\) of G is the minimum number of colors that are required in an edge-coloring of G such that for every k-subset S of V(G), there exist \(\ell \) internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and \(\ell \) with \(k \ge 3\) and \(\ell \le \kappa _k(K_{n,n})\), there exists a positive integer \(N_1=N_1(k,\ell )\) such that \(px_{k,\ell }(K_n) = 2\) for every integer \(n \ge N_1\), and there exists also a positive integer \(N_2=N_2(k,\ell )\) such that \(px_{k,\ell }(K_{m,n}) = 2\) for every integer \(n \ge N_2\) and \(m=O(n^r) (r \ge 1)\). In addition, we show that for every \(p \ge c\root k \of {\frac{\log _a n}{n}}\) (\(c \ge 5\)), \(px_{k,\ell }(G_{n,p})\le 2\) holds almost surely, where \(G_{n,p}\) is the Erd?s–Rényi random graph model.     

A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorable

A graph G is \((d_1, d_2)\)-colorable if its vertices can be partitioned into subsets \(V_1\) and \(V_2\) such that in \(G[V_1]\) every vertex has degree at most \(d_1\) and in \(G[V_2]\) every vertex has degree at most \(d_2\). Let \(\mathcal {G}_5\) denote the family of planar graphs with minimum cycle length at least 5. It is known that every graph in \(\mathcal {G}_5\) is \((d_1, d_2)\)-colorable, where \((d_1, d_2)\in \{(2,6), (3,5),(4,4)\}\). We still do not know even if there is a finite positive d such that every graph in \(\mathcal {G}_5\) is (1, d)-colorable. In this paper, we prove that every graph in \(\mathcal {G}_5\) without adjacent 5-cycles is (1, 7)-colorable. This is a partial positive answer to a problem proposed by Choi and Raspaud that is every graph in \(\mathcal {G}_5\;(1, 7)\)-colorable?.     

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.     

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

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.     

The 3-rainbow index and connected dominating sets

A tree in an edge-colored graph is said to be rainbow if no two edges on the tree share the same color. An edge-coloring of \(G\) is called a 3-rainbow coloring if for any three vertices in \(G\), there exists a rainbow tree connecting them. The 3-rainbow index \(rx_3(G)\) of \(G\) is defined as the minimum number of colors that are needed in a 3-rainbow coloring of \(G\). This concept, introduced by Chartrand et al., can be viewed as a generalization of the rainbow connection. In this paper, we study the 3-rainbow index by using connected 3-way dominating sets and 3-dominating sets. We show that for every connected graph \(G\) on \(n\) vertices with minimum degree at least \(\delta \, (3\le \delta \le 5)\), \(rx_{3}(G)\le \frac{3n}{\delta +1}+4\), and the bound is tight up to an additive constant; whereas for every connected graph \(G\) on \(n\) vertices with minimum degree at least \(\delta \, (\delta \ge 3)\), we get that \(rx_{3}(G)\le \frac{\ln (\delta +1)}{\delta +1}(1+o_{\delta }(1))n+5\). In addition, we obtain some tight upper bounds of the 3-rainbow index for some special graph classes, including threshold graphs, chain graphs and interval graphs.     

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.     

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

A greedy algorithm for the minimum 2-connected m-fold dominating set problem

To save energy and alleviate interference in a wireless sensor network, connected dominating set (CDS) has been proposed as the virtual backbone. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a \(k\)-connected \(m\)-fold dominating set \(((k,m)\)-CDS for short): a subset of nodes \(C\subseteq V(G)\) is a \((k,m)\)-CDS of \(G\) if every node in \(V(G)\setminus C\) is adjacent with at least \(m\) nodes in \(C\) and the subgraph of \(G\) induced by \(C\) is \(k\)-connected.In this paper, we present an approximation algorithm for the minimum \((2,m)\)-CDS problem with \(m\ge 2\). Based on a \((1,m)\)-CDS, the algorithm greedily merges blocks until the connectivity is raised to two. The most difficult problem in the analysis is that the potential function used in the greedy algorithm is not submodular. By proving that an optimal solution has a specific decomposition, we managed to prove that the approximation ratio is \(\alpha +2(1+\ln \alpha )\), where \(\alpha \) is the approximation ratio for the minimum \((1,m)\)-CDS problem. This improves on previous approximation ratios for the minimum \((2,m)\)-CDS problem, both in general graphs and in unit disk graphs.     

Pac king spanning trees and spanning 2-connected k-edge-connected essentially $$(2 k-1)$$(2 k-1)-edge-connected subgraphs

Let \(k\ge 2, p\ge 1, q\ge 0\) be integers. We prove that every \((4kp-2p+2q)\)-connected graph contains p spanning subgraphs \(G_i\) for \(1\le i\le p\) and q spanning trees such that all \(p+q\) subgraphs are pairwise edge-disjoint and such that each \(G_i\) is k-edge-connected, essentially \((2k-1)\)-edge-connected, and \(G_i -v\) is \((k-1)\)-edge-connected for all \(v\in V(G)\). This extends the well-known result of Nash-Williams and Tutte on packing spanning trees, a theorem that every 6p-connected graph contains p pairwise edge-disjoint spanning 2-connected subgraphs, and a theorem that every \((6p+2q)\)-connected graph contains p spanning 2-connected subgraphs and q spanning trees, which are all pairwise edge-disjoint. As an application, we improve a result on k-arc-connected orientations.