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]

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 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]

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 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 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]

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]

Abstract: Let be a simple graph with vertex set and edge set . The incidence matrix of G is the matrix whose -entry is 1 if is incident to and 0 otherwise. The incidence energy IE of G is the sum of the singular values of . In this paper we give lower and upper bounds for IE in terms of n, m, maximum degree, clique number, independence number, and the first Zagreb index. Moreover, we obtain Nordhaus–Gaddum-type results for IE. [Copyright &y& Elsevier]

Abstract: Let G be a connected graph of order n with Laplacian eigenvalues . The Laplacian-energy-like invariant of the graph G is defined as Lower and upper bounds for LEL are obtained, in terms of n, number of edges, maximum vertex degree, and number of spanning trees. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The Laplacian matrix of G is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Let be the Laplacian eigenvalues of G. For a graph G and a real number , the graph invariant is the sum of the β-th power of the non-zero Laplacian eigenvalues of G, that is, In this paper, we obtain some lower and upper bounds on for G in terms of n, the number of edges m, maximum degree , clique number ω, independence number α and the number of spanning trees t. Moreover, we present some Nordhaus–Gaddum-type results for of G. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The Laplacian matrix of G is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity of a graph [18]. In this paper we give a lower bound on the algebraic connectivity of graphs. Moreover, we mention two conjectures, obtained by the system AutoGraphiX, about the algebraic connectivity , diameter and the minimum degree of graphs (see, [2], available online at http://www.gerad.ca/∼agx/):with equality if and only if G is isomorphic to a graph with and , and (ii) is minimum for a graph composed of 2 cliques on vertices with a common vertex if n is odd, and linked by an edge if n is even. Here we prove conjecture in (i) using the lower bound on the algebraic connectivity of graphs and conjecture in (ii), respectively. [Copyright &y& Elsevier]

Abstract: Let G be a connected graph of order n with Laplacian eigenvalues . The Kirchhoff index and the Laplacian-energy-like invariant of G are defined as and , respectively. We compare Kf and LEL and establish two sufficient conditions under which . The connected graphs of order n with nine greatest Kirchhoff indices are determined; for these holds. [Copyright &y& Elsevier]

Abstract: Let G =(V, E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the signless Laplacian matrix of G is Q(G)= D(G)+ A(G). In [5], Cvetković et al. have given the following conjecture involving the second largest signless Laplacian eigenvalue () and the index () of graph G (see also Aouchiche and Hansen [1]):with equality if and only if G is the star for the lower bound, and if and only if G is the complete bipartite graph for the upper bound. In this paper we prove the lower bound and characterize the extremal graphs. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The adjacency matrix of a graph is denoted by and defined as the matrix , where for and 0 otherwise. The largest eigenvalue () of is called the spectral radius or the index of . The Laplacian matrix of is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity () of a graph [12]. In [1,2], Aouchiche et al. have given a series of conjectures on index () and algebraic connectivity () of (see also [3]). Here we prove two conjectures and disprove one by a counter example. [Copyright &y& Elsevier]

Abstract: Let be a simple graph. Denote by the diagonal matrix of its vertex degrees and by its adjacency matrix. Then the Laplacian matrix of is and the signless Laplacian matrix of is . In this paper we obtain a lower bound on the second largest signless Laplacian eigenvalue and an upper bound on the smallest signless Laplacian eigenvalue of . In , Cvetković et al. have given a series of 30 conjectures on Laplacian eigenvalues and signless Laplacian eigenvalues of (see also ). Here we prove five conjectures. [Copyright &y& Elsevier]

Abstract: Let be a simple graph of order with edges. Let the adjacency spectrum be of , where . The Estrada index of a graph is . In [J.A. Peña, I. Gutman, J. Rada, Estimating the Estrada index, Linear Algebra Appl. 427 (2007) 70–76], Peña et al. posed a conjecture that the star has maximum Estrada index for any tree of order and the path has minimum Estrada index for any tree of order or any connected graph of order . In this paper, we have proved that the star has maximum Estrada index for any tree. Also, we obtain that the path has minimum Estrada index for any connected graph with or . Moreover, we give better lower bound on Estrada index for any connected graph. [Copyright &y& Elsevier]

Abstract: An upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries is investigated in [S. Zhao, Y. Hong, On the bounds of maximal entries in the principal eigenvector of symmetric nonnegative matrix, Linear Algebra Appl. 340 (2002) 245–252]. We obtain a sharp upper bound on the maximal entry in the principal eigenvector of symmetric nonnegative matrix in terms of order, the spectral radius, the largest and the smallest diagonal entries of that matrix. Our bound is applicable for any symmetric nonnegative matrix and the upper bound of Zhao and Hong (2002) for the maximal entry follows as a special case. Moreover, we find an upper bound on maximal entry in the principal eigenvector for the signless Laplacian matrix of a graph. [Copyright &y& Elsevier]

Abstract: We consider weighted graphs, where the edge weights are positive definite matrices. In this paper, we obtain two upper bounds on the spectral radius of the Laplacian matrix of weighted graphs and characterize graphs for which the bounds are attained. Moreover, we show that some known upper bounds on the Laplacian spectral radius of weighted and unweighted graphs can be deduced from our upper bounds. [Copyright &y& Elsevier]

Abstract: The higher Randić index R t (G) of a simple graph G is defined aswhere δ i denotes the degree of the vertex i and i 1 i 2⋯i t+1 runs over all paths of length t in G. In [J.A. Rodríguez, A spectral approach to the Randić index, Linear Algebra Appl. 400 (2005) 339–344], the lower and upper bound on R 1(G) was determined in terms of a kind of Laplacian spectra, and the lower and upper bound on R 2(G) were done in terms of kinds of adjacency and Laplacian spectra. In this paper we characterize the graphs which achieve the upper or lower bounds of R 1(G) and R 2(G), respectively. [Copyright &y& Elsevier]

Abstract: We consider weighted graphs, where the edge weights are positive definite matrices. The Laplacian of the graph is defined in the usual way. We obtain an upper bound on the largest eigenvalue of the Laplacian and characterize graphs for which the bound is attained. The classical bound of Anderson and Morley, for the largest eigenvalue of the Laplacian of an unweighted graph follows as a special case. [Copyright &y& Elsevier]

Let λ1(T) and λ2(T) be the largest and the second largest Laplacian eigenvalues of a tree T. We obtain the following sharp lower bound for λ1(T):λ1(T)&ges;max(di+mi+1)+(di+mi+1)2−4(dimi+1)/2:vi∈V,wheredi and mi denote the degree of vertex vi and the average of the degrees of the vertices adjacent to vertex vi respectively. Equality holds if and only if T is a tree T(di,dj), where T(di,dj) is formed by joining the centres of di copies of K1,dj−1 to a new vertex vi, that is, T(di,dj)−vi=diK1,dj−1.

Let v1 be the highest degree vertex of degree d1 and v2 be the second highest degree vertex of degree d2. We also show that if T is a tree of order n>2, thenλ2(T)&ges;d2ifv1v2∈E,(d2+1)+(d2+1)2−4/2: vi∈V,wheredi and mi denote the degree of vertex vi and the average of the degrees of the vertices adjacent to vertex vi respectively. Equality holds if and only if T is a tree T(di,dj), where T(di,dj) is formed by joining the centres of di copies of K1,dj−1 to a new vertex vi, that is, T(di,dj)−vi=diK1,dj−1.Let v1 be the highest degree vertex of degree d1 and v2 be the second highest degree vertex of degree d2. We also show that if T is a tree of order n>2, thenλ2(T)&ges;d2if v1v2∈E,(d2+1)+(d2+1)2−4/2if v1v2∉E,whereE is the set of edges. Equality holds if T=T1(d1) or T=T2(d1), where T1(d1) is formed by joining the centres of two copies of K1,d1−1 and T2(d1) is formed by joining the centres of two copies of K1,d1−1 to a new vertex.Moreover, we obtain the lower bounds for the sum of two largest Laplacian eigenvalues. [Copyright &y& Elsevier]

Let G=(V,E) be a simple connected graph and λ1(G) be the largest Laplacian eigenvalue of G. In this paper, we prove that: [Copyright &y& Elsevier]

Let G=(V,E) be a simple graph on vertex set V={v1,v2,…,vn}. Further let di be the degree of vi and Ni be the set of neighbors of vi. It is shown thatmaxdi+dj−|Ni∩Nj|:1&les;iis an upper bound for the largest eigenvalue of the Laplacian matrix of G, where |Ni∩Nj| denotes the number of common neighbors between vi and vj. For any G, this bound does not exceed the order of G.Further using the concept of common neighbors another upper bound for the largest eigenvalue of the Laplacian matrix of a graph has been obtained asmax√ of 2d2i+dim′i:1&les;i&les;n,wherem′i=∑jdj−|Ni∩Nj|:vivj∈E/di. [Copyright &y& Elsevier]

Abstract: A graph G is L–DS (respectively, Q–DS) if there is no other non-isomorphic graph with the same (respectively, signless) Laplacian spectrum as G. Let be the join graph of graphs and , and the graph obtained by attaching pendent vertices to a vertex of (the cycle of order r). In this paper, we prove that if G is L–DS and the algebraic connectivity of G is less than three, then is L–DS under certain condition, which extends the main result of Zhou and Bu (2012) [24]. Also, is proved to be Q–DS for . [Copyright &y& Elsevier]

Let a ( k ) = ( a 1 , a 2 , … , a k ) be a sequence of positive integers. A butterfly-like graph W p ( s ) ; a ( k ) is a graph consisting of s ( ≥ 1 ) cycle of lengths p + 1 , and k ( ≥ 1 ) paths P a 1 + 1 , P a 2 + 1 , …, P a k + 1 intersecting in a single vertex. The girth of a graph G is the length of a shortest cycle in G . Two graphs are said to be A - cospectral if they have the same adjacency spectrum. For a graph G , if there does not exist another non-isomorphic graph H such that G and H share the same Laplacian (respectively, signless Laplacian) spectrum, then we say that G is L − D S (respectively, Q − D S ). In this paper, we firstly prove that no two non-isomorphic butterfly-like graphs with the same girth are A -cospectral, and then present a new upper and lower bounds for the i -th largest eigenvalue of L ( G ) and Q ( G ) , respectively. By applying these new results, we give a positive answer to an open problem in Wen et al. (2015) [17] by proving that all the butterfly-like graphs W 2 ( s ) ; a ( k ) are both Q − D S and L − D S . [ABSTRACT FROM AUTHOR]

There is an error in the proof of Theorem 2.2 in our paper Liu et al. (2017) [1] , and we give a correct proof. [ABSTRACT FROM AUTHOR]