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.     

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

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.     

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

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

On the <Emphasis Type="Italic">L</Emphasis>(2, 1)-labeling conjecture 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,\ldots \}\) 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 \(\lambda (G)\) of G is the minimum span over all L(2, 1)-labelings of G. In this paper, we conclude that the \(\lambda \)-number of each brick product graph is 5 or 6, which confirms Conjecture 6.1 stated in Li et al. (J Comb Optim 25:716–736, 2013).     

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

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.     

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.     

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.     

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.     

Extremal polyomino chains with respect to general Randić index

For a (molecular) graph \(G,\) the general Randi? index \(R_{\alpha }(G)\) is defined as the sum of the weights \([d_{u}d_{v}]^{\alpha }\) of all edges \(uv\) of \(G,\) where \(d_{u}\) (or \(d_{v}\)) denotes the degree of a vertex \(u\) (or \(v\)) in \(G\) and \(\alpha \) is an arbitrary real number. In this paper, we give an efficient formula for computing the general Randi? index of polyomino chains and characterize the extremal polyomino chains with respect to this index, which generalizes one of the main results in (Yarahmadi et al. Appl Math Lett 25:166–171, 2012).     

Relation between the skew-rank of an oriented graph and the independence number of its underlying graph

An oriented graph \(G^\sigma \) is a digraph without loops or multiple arcs whose underlying graph is G. Let \(S\left( G^\sigma \right) \) be the skew-adjacency matrix of \(G^\sigma \) and \(\alpha (G)\) be the independence number of G. The rank of \(S(G^\sigma )\) is called the skew-rank of \(G^\sigma \), denoted by \(sr(G^\sigma )\). Wong et al. (Eur J Comb 54:76–86, 2016) studied the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. In this paper, the correlation involving the skew-rank, the independence number, and some other parameters are considered. First we show that \(sr(G^\sigma )+2\alpha (G)\geqslant 2|V_G|-2d(G)\), where \(|V_G|\) is the order of G and d(G) is the dimension of cycle space of G. We also obtain sharp lower bounds for \(sr(G^\sigma )+\alpha (G),\, sr(G^\sigma )-\alpha (G)\), \(sr(G^\sigma )/\alpha (G)\) and characterize all corresponding extremal graphs.     

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.     

An $$O(n\log n)$$ algorithm for finding edge span of cacti

Let \(G=(V,E)\) be a nonempty graph and \(\xi :E\rightarrow \mathbb {N}\) be a function. In the paper we study the computational complexity of the problem of finding vertex colorings \(c\) of \(G\) such that:

1. (1)
   \(|c(u)-c(v)|\ge \xi (uv)\) for each edge \(uv\in E\);
    
2. (2)
   the edge span of \(c\), i.e. \(\max \{|c(u)-c(v)|:uv\in E\}\), is minimal.
    

We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for cycles and bipartite graphs. Next, we use the last two results to construct an algorithm that solves the problem for a given cactus \(G\) in \(O(n\log n)\) time, where \(n\) is the number of vertices of \(G\).

     

2-Edge connected dominating sets and 2-Connected dominating sets of a graph

A \(k\)-connected (resp. \(k\)-edge connected) dominating set \(D\) of a connected graph \(G\) is a subset of \(V(G)\) such that \(G[D]\) is \(k\)-connected (resp. \(k\)-edge connected) and each \(v\in V(G)\backslash D\) has at least one neighbor in \(D\). The \(k\) -connected domination number (resp. \(k\) -edge connected domination number) of a graph \(G\) is the minimum size of a \(k\)-connected (resp. \(k\)-edge connected) dominating set of \(G\), and denoted by \(\gamma _k(G)\) (resp. \(\gamma '_k(G)\)). In this paper, we investigate the relation of independence number and 2-connected (resp. 2-edge-connected) domination number, and prove that for a graph \(G\), if it is \(2\)-edge connected, then \(\gamma '_2(G)\le 4\alpha (G)-1\), and it is \(2\)-connected, then \(\gamma _2(G)\le 6\alpha (G)-3\), where \(\alpha (G)\) is the independent number of \(G\).     

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.     

1.61-approximation for min-power strong connectivity with two power levels

Given a directed simple graph \(G=(V,E)\) and a cost function \(c:E \rightarrow R_+\), the power of a vertex \(u\) in a directed spanning subgraph \(H\) is given by \(p_H(u) = \max _{uv \in E(H)} c(uv)\), and corresponds to the energy consumption required for wireless node \(u\) to transmit to all nodes \(v\) with \(uv \in E(H)\). The power of \(H\) is given by \(p(H) = \sum _{u \in V} p_H(u)\). Power Assignment seeks to minimize \(p(H)\) while \(H\) satisfies some connectivity constraint. In this paper, we assume \(E\) is bidirected (for every directed edge \(e \in E\), the opposite edge exists and has the same cost), while \(H\) is required to be strongly connected. Moreover, we assume \(c:E \rightarrow \{A,B\}\), where \(0 \le A < B\). We improve the best known approximation ratio from 1.75 (Chen et al. IEEE GLOBECOM 2005) to \(\pi ^2/6 - 1/36 + \epsilon \le 1.61\) using an adaptation of the algorithm developed by Khuller et al. [SIAM J Comput 24(4):859–872 1995, Discr Appl Math 69(3):281–289 1996] for (unweighted) Minimum Strongly Connected Subgraph.     

Power domination with bounded time constraints

Based on the power observation rules, the problem of monitoring a power utility network can be transformed into the graph-theoretic power domination problem, which is an extension of the well-known domination problem. A set \(S\) is a power dominating set (PDS) of a graph \(G=(V,E)\) if every vertex \(v\) in \(V\) can be observed under the following two observation rules: (1) \(v\) is dominated by \(S\), i.e., \(v \in S\) or \(v\) has a neighbor in \(S\); and (2) one of \(v\)’s neighbors, say \(u\), and all of \(u\)’s neighbors, except \(v\), can be observed. The power domination problem involves finding a PDS with the minimum cardinality in a graph. Similar to message passing protocols, a PDS can be considered as a dominating set with propagation that applies the second rule iteratively. This study investigates a generalized power domination problem, which limits the number of propagation iterations to a given positive integer; that is, the second rule is applied synchronously with a bounded time constraint. To solve the problem in block graphs, we propose a linear time algorithm that uses a labeling approach. In addition, based on the concept of time constraints, we provide the first nontrivial lower bound for the power domination problem.     

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.