Search

Abstract In a network or a graph, the total communicability (TC) has been defined as the sum of the entries in the exponential of the adjacency matrix of the network. This quantity offers a good measure of how easily information spreads across the network, and can be useful in the design of networks having certain desirable properties. In this paper, we obtain some bounds for total communicability of a graph G , T C (G) , in terms of spectral radius of the adjacency matrix, number of vertices, number of edges, minimum degree and the maximum degree of G. Moreover, we find some upper bounds for T C (G) when G is the Cartesian product, tensor product or the strong product of two graphs. In addition, Nordhaus–Gaddum-type results for the total communicability of a graph G are established. [ABSTRACT FROM AUTHOR]

Abstract Let G = (V , E) be a simple graph of order n with normalized Laplacian eigenvalues ρ 1 ≥ ρ 2 ≥ ⋯ ≥ ρ n − 1 ≥ ρ n = 0. The normalized Laplacian spread of graph G , denoted by ρ 1 − ρ n − 1 , is the difference between the largest and the second smallest normalized Laplacian eigenvalues of graph G. In this paper, we obtain the first four smallest values on ρ 2 of graphs. Moreover, we give a lower bound on ρ 2 of connected bipartite graph G except the complete bipartite graph and characterize graphs for which the bound is attained. Finally, we present some bounds on the normalized Laplacian spread of graphs and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a simple graph of order n and size m , with vertex set V ( G ) = { v 1 , v 2 , … , v n } , without isolated vertices and sequence of vertex degrees Δ = d 1 ≥ d 2 ≥ ⋯ ≥ d n = δ > 0 , d i = d G ( v i ) . If the vertices v i and v j are adjacent, we denote it as v i v j ∈ E ( G ) or i ∼ j . With TI we denote a topological index that can be represented as T I = T I ( G ) = ∑ i ∼ j F ( d i , d j ) , where F is an appropriately chosen function with the property F ( x , y ) = F ( y , x ) . A general extended adjacency matrix A = ( a i j ) of G is defined as a i j = F ( d i , d j ) if the vertices v i and v j are adjacent, and a i j = 0 otherwise. Denote by f i , i = 1 , 2 , … , n the eigenvalues of A . The “energy” of the general extended adjacency matrix is defined as E T I = E T I ( G ) = ∑ i = 1 n | f i | . Lower and upper bounds on E T I are obtained. By means of the present approach a plethora of earlier established results can be obtained as special cases. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n and size m with Laplacian eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n = 0 . The Kirchhoff index of G , denoted by Kf , is defined as: K f = n ∑ i = 1 n − 1 1 μ i . The Laplacian-energy-like invariant ( L E L ) and the Laplacian energy ( L E ) of the graph G , are defined as: L E L = ∑ i = 1 n − 1 μ i and L E = ∑ i = 1 n | μ i − 2 m n | , respectively. We obtain two relations on LEL with Kf , and LE with Kf . For two classes of graphs, we prove that L E L > K f . Finally, we present an upper bound on the ratio L E / L E L and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph of order n with m edges. Denote by D ( G ) the diagonal matrix of its vertex degrees and by A ( G ) its adjacency matrix. Then the Laplacian matrix of graph G is L ( G ) = D ( G ) − A ( G ) . Among all eigenvalues of the Laplacian matrix L ( G ) of graph G , the most studied is the second smallest, called the algebraic connectivity a ( G ) of a graph. Let d ‾ ( G ) and δ ( G ) be the average degree and the minimum degree of graph G , respectively. In this paper we characterize all graphs for which ( i ) a ( G ) = 1 with δ ( G ) ≥ ⌈ n − 1 2 ⌉ , and ( i i ) a ( G ) = 2 with δ ( G ) ≥ n 2 . In [1] , Aouchiche mentioned a conjecture involving the algebraic connectivity a ( G ) and the average degree d ‾ ( G ) of graph G : a ( G ) − d ‾ ( G ) ≥ 4 − n − 4 n with equality holding if and only if G ‾ ≅ K 1 , n − 2 ∪ K 1 ( K 1 , n − 2 is a star of order n − 1 and G ‾ is the complement of graph G ). Here we prove this conjecture. [ABSTRACT FROM AUTHOR]

Let d ( u, v ) be the distance between u and v of graph G , and let W f ( G ) be the sum of f ( d ( u, v )) over all unordered pairs { u, v } of vertices of G , where f ( x ) is a function of x . In some literatures, W f ( G ) is also called the Q -index of G . In this paper, some unified properties to Q -indices are given, and the majorization theorem is illustrated to be a good tool to deal with the ordering problem of Q -index among trees with n vertices. With the application of our new results, we determine the four largest and three smallest (resp. four smallest and three largest) Q -indices of trees with n vertices for strictly decreasing (resp. increasing) nonnegative function f ( x ), and we also identify the twelve largest (resp. eighteen smallest) Harary indices of trees of order n  ≥ 22 (resp. n  ≥ 38) and the ten smallest hyper-Wiener indices of trees of order n  ≥ 18, which improve the corresponding main results of Xu (2012) and Liu and Liu (2010), respectively. Furthermore, we obtain some new relations involving Wiener index, hyper-Wiener index and Harary index, which gives partial answers to some problems raised in Xu (2012). [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a simple graph of order n . The normalized Laplacian eigenvalues of graph G are denoted by ρ 1 ( G ) ≥ ρ 2 ( G ) ≥ ⋯ ≥ ρ n − 1 ( G ) ≥ ρ n ( G ) = 0 . Also let G and G ′ be two nonisomorphic graphs on n vertices. Define the distance between the normalized Laplacian spectra of G and G ′ as σ N ( G , G ′ ) = ∑ i = 1 n | ρ i ( G ) − ρ i ( G ′ ) | p , p ≥ 1 . Define the cospectrality of G by c s N ( G ) = min ⁡ { σ N ( G , G ′ ) : G ′ not isomorphic to G } . Let c s n N = max ⁡ { c s N ( G ) : G a graph on n vertices } . In this paper, we give an upper bound on c s N ( G ) in terms of the graph parameters. Moreover, we obtain an exact value of c s n N . An upper bound on the distance between the normalized Laplacian spectra of two graphs has been presented in terms of Randić energy. As an application, we determine the class of graphs, which are lying closer to the complete bipartite graph than to the complete graph regarding the distance of normalized Laplacian spectra. [ABSTRACT FROM AUTHOR]

A kite graph Ki n ,  ω is a graph obtained from a clique K ω and a path P n − ω by adding an edge between a vertex from the clique and an endpoint from the path. In this note, we prove that K i n , n − 1 is determined by its signless Laplacian spectrum when n ≠ 5 and n ≥ 4, and K i n , n − 1 is also determined by its distance spectrum when n ≥ 4. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n . For i = 1 , 2 , … , n , let d i be the degree of the vertex v i of G . The extended adjacency matrix A ex of G is defined so that its ( i, j )-entry is equal to 1 2 ( d i d j + d j d i ) if the vertices v i and v j are adjacent, and 0 otherwise,Yang et al. (1994). The spectral radius η 1 and the energy E e x of the A ex -matrix are examined. Lower and upper bounds on η 1 and E e x are obtained, and the respective extremal graphs characterized. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n with maximum degree Δ and minimum degree δ . Let ( d ) = ( d 1 , d 2 , … , d n ) and ( d ⁎ ) = ( d 1 ⁎ , d 2 ⁎ , … , d n ⁎ ) be the sequences of degrees and conjugate degrees of G . We define π = ∑ i = 1 n d i and π ⁎ = ∑ i = 1 n d i ⁎ , and prove that π ⁎ ≤ L E L ≤ I E ≤ π where LEL and IE are, respectively, the Laplacian-energy-like invariant and the incidence energy of G . Moreover, we prove that π − π ⁎ > ( δ / 2 ) ( n − Δ ) for a certain class of graphs. Finally, we compare the energy of G and π , and present an upper bound for the Laplacian energy in terms of degree sequence. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n with m edges and clique number ω . Let μ 1 ≥ μ 2 ≥ … ≥ μ n = 0 be the Laplacian eigenvalues of G and let σ = σ ( G ) ( 1 ≤ σ ≤ n ) be the largest positive integer such that μ σ ≥ 2 m n . In this paper we study the relation between σ and ω . In particular, we provide the answer to Problem 2.3 raised in Pirzada and Ganie (2015) [15] . Moreover, we characterize all connected threshold graphs with σ < ω − 1 , σ = ω − 1 and σ > ω − 1 . We obtain Nordhaus–Gaddum-type results for σ . Some relations between σ with other graph invariants are obtained. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a connected graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The transmission Tr ( v i ) of vertex v i is defined to be the sum of distances from v i to all other vertices. Let Tr ( G ) be the n × n diagonal matrix with its ( i , i ) -entry equal to Tr G ( v i ) . The distance signless Laplacian is defined as D Q ( G ) = Tr ( G ) + D ( G ) , where D ( G ) is the distance matrix of G . Let ∂ 1 ( G ) ≥ ∂ 2 ( G ) ≥ ⋯ ≥ ∂ n ( G ) denote the eigenvalues of distance signless Laplacian matrix of G . In this paper, we first characterize all graphs with ∂ n ( G ) = n − 2 . Secondly, we characterize all graphs with ∂ 2 ( G ) ∈ [ n − 2 , n ] when n ≥ 11 . Furthermore, we give the lower bound on ∂ 2 ( G ) with independence number α and the extremal graph is also characterized. [ABSTRACT FROM AUTHOR]

The energy E ( G ) of a simple graph G is the sum of absolute values of the eigenvalues of its adjacency matrix. The line graph of G is denoted by L G . We obtain a relation between E ( L G ) and E ( G ) , and establish bounds on E ( L G ) . Moreover, we present results pertaining to equienergetic and hyperenergetic graphs. [ABSTRACT FROM AUTHOR]

The Wiener polarity index W p ( G ) of a graph G is the number of unordered pairs of vertices { u ,  v } in G such that the distance between u and v is equal to 3. Very recently, Zhang and Hu studied the Wiener polarity index in [Y. Zhang, Y. Hu, 2016] [38]. In this short paper, we establish an upper bound on the Wiener polarity index in terms of Hosoya index and characterize the corresponding extremal graphs. Moreover, we obtain Nordhaus–Gaddum-type results for W p ( G ). Our lower bound on W p ( G ) + W p ( G ¯ ) is always better than the previous lower bound given by Zhang and Hu. [ABSTRACT FROM AUTHOR]

The energy of a simple graph G , E ( G ) , is the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of line graph and the signless Laplacian energy of graph G are denoted by E ( L G ) ( L G is the line graph of G ) and LE + ( G ) , respectively. In this paper we obtain a relation between E ( L G ) and LE + ( G ) of graph G . From this relation we characterize all the graphs satisfying E ( L G ) = LE + ( G ) + 4 m n − 4 . We also present a relation between E ( G ) and E ( L G ) . Moreover, we give an upper bound on E ( L G ) of graph G and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

The Graovac–Ghorbani index ( ABC GG ), was introduced by Graovac and Ghorbani, (2010). In this paper we present some upper and lower bounds on the ABC GG index and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

The zeroth-order Randić index and the sum-connectivity index are very popular topological indices in mathematical chemistry. These two indices are based on vertex degrees of graphs and attracted a lot of attention in recent years. Recently Li and Li (2015) studied these two indices for trees of order n . In this paper we obtain a relation between the zeroth-order Randić index and the sum-connectivity index for graphs. From this we infer an upper bound for the sum-connectivity index of graphs. Moreover, we prove that the zeroth-order Randić index is greater than the sum-connectivity index for trees. Finally, we show that R 2,  α ( G ) is greater or equal R 1,  α ( G ) ( α ≥ 1) for any graph and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

Let G be a connected threshold graph of order n with m edges and trace T . In this paper we give a lower bound on Laplacian energy in terms of n, m and T of G . From this we determine the threshold graphs with the first four minimal Laplacian energies. Moreover, we obtain the threshold graphs with the largest and the second largest Laplacian energies. [ABSTRACT FROM AUTHOR]

Let G be a bipartite graph of order n with m edges. The energy E ( G ) of G is the sum of the absolute values of the eigenvalues of the adjacency matrix A . In 1974, one of the present authors established lower and upper bounds for E ( G ) in terms of n, m , and det A . Now, more than 40 years later, we correct some details of this result and determine the extremal graphs. In addition, an upper bound on the Laplacian energy of bipartite graphs in terms of n, m , and the first Zagreb index is obtained, and the extremal graphs characterized. [ABSTRACT FROM AUTHOR]

Let W, Sz, PI , and WP be, respectively, the Wiener, Szeged, PI, and Wiener polarity indices of a molecular graph G . Let M 1 and M 2 be the first and second Zagreb indices of G . We obtain relations between these classical distance– and degree–based topological indices. [ABSTRACT FROM AUTHOR]

The distance signless Laplacian spectral radius of a connected graph G is the largest eigenvalue of the distance signless Laplacian matrix of G , defined as D Q ( G ) = T r ( G ) + D ( G ) , where D ( G ) is the distance matrix of G and T r ( G ) is the diagonal matrix of vertex transmissions of G . In this paper we determine upper and lower bounds on the minimal and maximal entries of the principal eigenvector of D Q ( G ) and characterize the extremal graphs. In addition, we obtain a lower bound on the distance signless Laplacian spectral radius of G based on its order and independence number, and characterize the extremal graph. [ABSTRACT FROM AUTHOR]

For G being a graph with n vertices and m edges, and with Laplacian eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n − 1 ≥ μ n = 0 , the Laplacian energy is defined as L E = ∑ i = 1 n | μ i − 2 m / n | . Let σ be the largest positive integer such that μ σ ≥ 2 m / n . We characterize the graphs satisfying σ = n − 1 . Using this, we obtain lower bounds for LE in terms of n, m , and the first Zagreb index. In addition, we present some upper bounds for LE in terms of graph invariants such as n, m , maximum degree, vertex cover number, and spanning tree packing number. [ABSTRACT FROM AUTHOR]

For any real number α , let s α ( G ) denote the sum of the α th power of the non-zero Laplacian eigenvalues of a graph G . In this paper, we first obtain sharp bounds on the largest and the second smallest Laplacian eigenvalues of a graph, and a new spectral characterization of a graph from its Laplacian eigenvalues. Using these results, we then establish sharp bounds for s α ( G ) in terms of the number of vertices, number of edges, maximum vertex degree and minimum vertex degree of the graph G , from which a Nordhaus–Gaddum type result for s α is also deduced. Moreover, we characterize the graphs maximizing s α for α > 1 among all the connected graphs with given matching number. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a simple graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The distance signless Laplacian spectral radius of a connected graph G is the spectral radius of the distance signless Laplacian matrix of G , defined as Q ( G ) = Tr ( G ) + D ( G ) , where Tr ( G ) is the diagonal matrix of vertex transmissions of G and D ( G ) is the distance matrix of G . In [10] , Xing et al. determined the graph with minimum distance signless Laplacian spectral radius among the trees with fixed number of vertices. For n ≥ 3 , let T n − 3 , 1 1 be the n -vertex tree of maximum degree n − 2 . In this paper, we show that T n − 3 , 1 1 gives the second minimum distance signless Laplacian spectral radius among the trees with fixed number of vertices. Moreover, we prove two conjectures involving the second largest eigenvalue of the distance signless Laplacian matrix Q ( G ) of graph G . [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n with vertex set V = { v 1 , v 2 , … , v n } . Also let μ 1 ( G ) ≥ μ 2 ( G ) ≥ ⋯ ≥ μ n − 1 ( G ) ≥ μ n ( G ) = 0 and q 1 ( G ) ≥ q 2 ( G ) ≥ ⋯ ≥ q n ( G ) ≥ 0 be the Laplacian eigenvalues and signless Laplacian eigenvalues of G , respectively. In this paper we obtain μ i ( G ) ≤ i − 1 + min U i ⁡ max ⁡ { | N H ( v k ) ∪ N H ( v j ) | : v k v j ∈ E ( H ) } , where N H ( v k ) is the set of neighbors of vertex v k in V ( H ) = V ( G ) \ U i , U i is any ( i − 1 ) -subset of V ( G ) (here, we agree that i ∈ { 1 , … , n − 1 } and μ i ( G ) ≤ i − 1 if E ( H ) = ∅ ). For any graph G , this bound does not exceed the order of G . Moreover, we prove that max ⁡ { μ i ( G ) , q i ( G ) } ≤ max i ≤ k ≤ n ⁡ { d G ( v k ) + ∑ v j ∈ N G ( v k ) ∩ N d G ( v j ) d G ( v k ) } ≤ 2 d G ( v i ) , where d G ( v i ) is the i -th largest degree of G and N = { v i , v i + 1 , … , v n } . [ABSTRACT FROM AUTHOR]