A short and unified proof of Yu et al.?s two results on the eccentric distance sum

The eccentric distance sum (EDS) is a novel topological index that offers a vast potential for structure activity/property relationships. For a connected graph G, the eccentric distance sum is defined as ξd(G)=_∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of a vertex v in G and DG(v) is the sum of distances of all vertices in G from v. More recently, Yu et al. [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107] proved that for an n-vertex tree T, ξd(T)?4n²−9n+5, with equality holding if and only if T is the n-vertex star Sn, and for an n-vertex unicyclic graph G, ξd(G)?4n²−9n+1, with equality holding if and only if G is the graph obtained by adding an edge between two pendent vertices of n-vertex star. In this note, we give a short and unified proof of the above two results.     

On the eccentric distance sum of graphs

The eccentric distance sum is a novel topological index that offers a vast potential for structure activity/property relationships. For a graph G, it is defined as ξd(G)=_∑v∈Vε(v)D(v), where ε(v) is the eccentricity of the vertex v and D(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. Motivated by [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 934-944], in this paper we characterize the extremal trees and graphs with maximal eccentric distance sum. Various lower and upper bounds for the eccentric distance sum in terms of other graph invariants including the Wiener index, the degree distance, eccentric connectivity index, independence number, connectivity, matching number, chromatic number and clique number are established. In addition, we present explicit formulae for the values of eccentric distance sum for the Cartesian product, applied to some graphs of chemical interest (like nanotubes and nanotori).     

Laplacian integral graphs in S(a, b)

Let G_n,m be the family of graphs with n vertices and m edges, when n and m are previously given. It is well-known that there is a subset of G_n,m constituted by graphs G such that the vertex connectivity, the edge connectivity, and the minimum degree are all equal. In this paper, S(a, b)-classes of connected (a, b)-linear graphs with n vertices and m edges are described, where m is given as a function of a,b∈N/2. Some of them have extremal graphs for which the equalities above are extended to algebraic connectivity. These graphs are Laplacian integral although they are not threshold graphs. However, we do build threshold graphs in S(a, b).     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

On Eccentric Connectivity Index of Eccentric Graph of Regular Dendrimer

The eccentric connectivity index \(\xi ^c(G)\) of a connected graph G is defined as \(\xi ^c(G) =\sum _{v \in V(G)}{deg(v) e(v)},\) where deg(v) is the degree of vertex v and e(v) is the eccentricity of v. The eccentric graph, \(G_e\), of a graph G has the same set of vertices as G,  with two vertices u, v adjacent in \(G_e\) if and only if either u is an eccentric vertex of v or v is an eccentric vertex of u. In this paper, we obtain a formula for the eccentric connectivity index of the eccentric graph of a regular dendrimer. We also derive a formula for the eccentric connectivity index for the second iteration of eccentric graph of regular dendrimer.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

The Connected Monophonic Number of a Graph

For a connected graph G = (V, E) of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A set S of vertices of G is a monophonic set of G if each vertex v of G lies on an x ? y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic set of G is defined as the monophonic number of G, denoted by m(G). A connected monophonic set of G is a monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by m _c (G). We determine bounds for it and characterize graphs which realize these bounds. For any two vertices u and v in G, the monophonic distance d _m (u, v) from u to v is defined as the length of a longest u ? v monophonic path in G. The monophonic eccentricity e _m (v) of a vertex v in G is the maximum monophonic distance from v to a vertex of G. The monophonic radius rad _m G of G is the minimum monophonic eccentricity among the vertices of G, while the monophonic diameter diam _m G of G is the maximum monophonic eccentricity among the vertices of G. It is shown that for positive integers r, d and n ≥ 5 with r <  d, there exists a connected graph G with rad _m G =  r, diam _m G =  d and m _c (G) =  n. Also, if a,b and p are positive integers such that 2 ≤  a <  b ≤  p, then there exists a connected graph G of order p, m(G) =  a and m _c (G) =  b.     

Graph Equation for Line Graphs and m-Step Graphs

Given a graph G, the m-step graph of G, denoted by S _m (G), has the same vertex set as G and an edge between two distinct vertices u and v if there is a walk of length m from u to v. The line graph of G, denoted by L(G), is a graph such that the vertex set of L(G) is the edge set of G and two vertices u and v of L(G) are adjacent if the edges corresponding to u and v share a common end vertex in G. We characterize connected graphs G such that S _m (G) and L(G) are isomorphic.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

Rainbow Connection Number and Radius

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) ≤  r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K _1,n for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) ≤  rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 ? 1, where n is order of the graph (Caro et al. in Electron J Comb 15(1):Research paper 57, 13, 2008). It is known that computing rc(G) is NP-Hard (Chakraborty and fischer in J Comb Optim 1–18, 2009). Here, we present a (r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r.     

On a conjecture of the Randi? index

The Randi? index of a graph G is defined as , where d(u) is the degree of vertex u and the summation goes over all pairs of adjacent vertices u, v. A conjecture on R(G) for connected graph G is as follows: R(G)≥r(G)−1, where r(G) denotes the radius of G. We proved that the conjecture is true for biregular graphs, connected graphs with order n≤10 and tricyclic graphs.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

Lollipop graphs are extremal for commute times

Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=max_{u, v∈V}C(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪_m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=max_{H∈𝒢(n, m)}C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=max_H∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000     

Sharp bounds of the zeroth-order general Randi? index of bicyclic graphs with given pendent vertices

Let G be a simple connected graph and α be a given real number. The zeroth-order general Randi? index of ⁰R_α(G) is defined as ∑_v∈V(G)[d_G(v)]^α, where d_G(v) denotes the degree of the vertex v of G. In this paper, for any α(≠0,1), we give sharp bounds of the zeroth-order general Randi? index ⁰R_α of all bicyclic graphs with n vertices and k pendent vertices.     

Degree Distance of Unicyclic Graphs with Given Matching Number

Let G be a connected graph with vertex set V(G). The degree distance of G is defined as ${D'(G) = \sum_{\{u, v\}\subseteq V(G)} (d_G(u) + d_G (v))\, d(u,v)}$ , where d _G (u) is the degree of vertex u, d(u, v) denotes the distance between u and v, and the summation goes over all pairs of vertices in G. In this paper, we characterize n-vertex unicyclic graphs with given matching number and minimal degree distance.     

Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

More on “Connected (n, m)-graphs with minimum and maximum zeroth-order general Randi? index”

Let G be a graph and d(u) denote the degree of a vertex u in G. The zeroth-order general Randi? index ⁰R_α(G) of the graph G is defined as ∑_u∈V(G)d(u)^α, where the summation goes over all vertices of G and α is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected (n,m)-graphs with minimum and maximum zeroth-order general Randi? index, Discrete Appl. Math. 155 (8) (2007) 1044-1054] and give a more general Theorem. We finally characterize ¹ for α<0 the connected G(n,m)-graphs with maximum value ⁰R_α(G(n,m)), where G(n,m) is a simple connected graph with n vertices and m edges.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.