Search

The aim of this note is to establish new spectral bounds for the harmonic matrix.

Let ρ 1 ≥ ρ 2 ≥ ⋯ ≥ ρ n − 1 ≥ ρ n = 0 be the normalized Laplacian eigenvalues of a graph G with n vertices. Also, let χ and α be the chromatic number and the independence number of a graph G, respectively. In this paper, we discuss some properties of graphs with ρ 1 = χ / (χ − 1). In particular, we characterize all the graphs with ρ 1 = χ / (χ − 1) when the maximum degree is n−1. Moreover, we obtain an upper bound on the multiplicity of normalized Laplacian eigenvalues m G (ρ) in terms of n and α, and also characterize graphs for which the bound is attained. [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]

Letdenote the class ofc-cyclic graphs withnvertices, girthandpendant vertices. In this paper, we determine the unique extremal graph with largest signless Laplacian spectral radius and Laplacian spectral radius in the class of connectedc-cyclic graphs withvertices, girthgand at mostpendant vertices, respectively, and the unique extremal graph with largest signless Laplacian spectral radius ofwhenand, and we also identify the unique extremal graph with largest Laplacian spectral radius inin the caseand eitherandgis even orandgis odd. Our results extends the corresponding results of [Sci. Sin. Math. 2010;40:1017–1024, Electron. J. Combin. 2011; 18:p.183, Comput. Math. Appl. 2010;59:376–381, Electron. J. Linear Algebra. 2011;22:378–388 and J. Math. Res. Appl. 2014;34:379–391]. [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 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]

The Kirchhoff indexof a graphGis the sum of resistance distances between all unordered pairs of vertices, which was introduced by Klein and Randić. In this paper, we characterize all extremal graphs with respect to Kirchhoff index among all graphs obtained by deletingpedges from a complete graphwithand obtain a sharp upper bound on the Kirchhoff index of these graphs. In addition, all the graphs with the first to ninth maximal Kirchhoff indices are completely determined among all connected graphs of order. [ABSTRACT FROM PUBLISHER]

The k-th power of a graph G, denoted by [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 number of spanning trees of a graphGis the total number of distinct spanning subgraphs ofGthat are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number. [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]

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]

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]

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]