Search

The cyclomatic number of a graph G (is denoted by ν) is the minimum number of edges of G whose removal makes G as acyclic. Denote by Gn,ν the collection of all n-vertex connected graphs with cyclomatic number ν. The elements of Gn,ν with maximum second Zagreb (M2) index (for ν ≤ 4 and ν = k(k-3) 2+1, where 4 ≤ k ≤ n-2) and with minimum M2 index (for ν ≤ 2) have already been reported in the literature. The main contribution of the present article is the characterization of graphs in the collection Gn,ν with minimum M2 index for ν ≥ 3 and n ≥ 2(ν - 1). The obtained extremal graphs, are molecular graphs and thereby, also minimize M2 index among all the connected molecular n-vertex graphs with cyclomatic number ν ≥ 3, where n ≥ 2(ν-1). For n ≥ 6, the graph having maximum M2 value in the collection Gn,5 has also been characterized and thereby a conjecture posed by Xu et al. [MATCH Commun. Math. Comput. Chem. 72 (2014) 641-654] is confirmed for ν = 5. [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 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]

The classical first and second Zagreb indices of a graph G are defined as M 1 ( G ) = ∑ v ∈ V d G ( v ) 2 and M 2 ( G ) = ∑ u v ∈ E ( G ) d G ( u ) d G ( v ) , where d G ( v ) is the degree of the vertex v of graph G . Recently, Furtula et al. (2014) studied the difference between the Zagreb indices and mentioned a problem to characterize the graphs for which M 1 ( G ) > M 2 ( G ) or M 1 ( G ) < M 2 ( G ) or M 1 ( G ) = M 2 ( G ) . In this paper we completely solve this problem. [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]

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 S z ( G ) and ξ c ( G ) be the Szeged index and the eccentric connectivity index of a graph G , respectively. In this paper we obtain a lower bound on S z ( T ) − ξ c ( T ) by double counting on some matrix and characterize the extremal graphs. From this result we compare the Szeged index and the eccentricity connectivity index of trees. For bipartite graphs we also compare the Szeged index and the eccentricity connectivity index. Moreover, we show that S z ( G ) − ξ c ( G ) ≥ − 4 for bipartite graphs and this result is not true in the general case. Finally, we classify the bipartite graphs G in which S z ( G ) − ξ c ( G ) ∈ { − 4 , − 3 , − 2 , − 1 , 0 , 1 , 2 } . [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: Molecular descriptors play an important role in mathematical chemistry, especially in the QSPR and QSAR modeling. Among them, a special place is reserved for the so called topological indices. Nowadays, there exists a legion of topological indices that found applications in various areas of chemistry Todeschini and Consonni (2000, 2009). Recently, we carried out comparison between several topological indices for various classes of graphs and trees (Das et al., 2012; Das and Trinajsti, 2010, 2011, 2012; Horoldagva and Das, 2012; Hua and Das, 2013). In this report, we compare the Wiener index and the Zagreb indices and the eccentric connectivity index for trees. [Copyright &y& Elsevier]

Abstract: Let be a graph with vertices and edges. Also let be the eigenvalues of the Laplacian matrix of graph . The Laplacian energy of the graph is defined as In this paper, we present some lower and upper bounds for of graph in terms of , the number of edges and the maximum degree . Also we give a Nordhaus–Gaddum-type result for Laplacian energy of graphs. Moreover, we obtain a relation between Laplacian energy and Laplacian-energy-like invariant of graphs. [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 connected graph with vertex set and edge set . The first Zagreb index and the second Zagreb index are defined as follows: and where is the degree of vertex in . The eccentric connectivity index of a graph , denoted by , is defined as where is the eccentricity of in . Recently, Das and Trinajstić (2011) [11] compared the eccentric connectivity index and Zagreb indices for chemical trees and molecular graphs. However, the comparison between the eccentric connectivity index and Zagreb indices, in the case of general trees and general graphs, is very hard and remains unsolved till now. In this paper, we compare the eccentric connectivity index and Zagreb indices for some graph families. We first give some sufficient conditions for a graph satisfying , . Then we introduce two classes of composite graphs, each of which has larger eccentric connectivity index than the first Zagreb index, if the original graph has larger eccentric connectivity index than the first Zagreb index. As a consequence, we can construct infinite classes of graphs having larger eccentric connectivity index than the first Zagreb index. [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: The power of a graph , denoted by , is the graph with the same vertex set as , such that two vertices are adjacent in if and only if their distance is at most in . In this paper, we give bounds on the first two largest Laplacian eigenvalues of the second power of a general graph, and on the second power of a tree. We also give a Nordhaus–Gaddum-type inequality for the Laplacian spectral radius of . [Copyright &y& Elsevier]

Abstract: Let be a simple connected graph. Denote by the diagonal matrix of its vertex degrees and by its adjacency matrix. Then the signless Laplacian matrix of G is . In this paper, we obtain some new and improved sharp upper bounds on the spectral radius of the signless Laplacian matrix of a graph G. [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 signless Laplacian matrix of is . In , Cvetković et al. (2007) have given conjectures on signless Laplacian eigenvalues of (see also Aouchiche and Hansen (2010) , Oliveira et al. (2010) ). Here we prove two conjectures. [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: The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph and two nonadjacent vertices and in of , recall that is the supergraph formed from by adding an edge between vertices and . Denote the Harary index of and by and , respectively. We obtain lower and upper bounds on , and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained. [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]

In this article, we present lower bounds for the largest eigen value, the second largest eigenvalue and the sum of the two largest eigenvalues of the Laplacian matrix of a graph. [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a simple graph with n vertices, e edges, and vertex degrees d1,d2,…,dn. Also, let d1, dn be, respectively, the highest degree and the lowest degree of G and mi be the average of the degrees of the vertices adjacent to vertex vi∈V. It is proved thatwith equality if and only if G is an Sn graph (K1,n-1⊆Sn⊆Kn) or a complete graph of order n-1 with one isolated vertex. Using the above result we establish the following upper bound for the sum of the squares of the degrees of a graph G:with equality if and only if G is a star graph or a regular graph or a complete graph Kd1+1 with n-d1-1 isolated vertices. A comparison is made to another upper bound on ∑i=1n di2, due to de Caen (Discrete Math. 185 (1998) 245). We also present several upper bounds for ∑i=1n di2 and determine the extremal graphs which achieve the bounds. [Copyright &y& Elsevier]

The eigenvalues of a graph are the eigenvalues of its adjacency matrix. This paper presents some upper and lower bounds on the greatest eigenvalue and a lower bound on the smallest eigenvalue. [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]