Search

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 , and be, respectively, the distance matrix, the distance Laplacian matrix and the distance signless Laplacian matrix of graph G, where denotes the diagonal matrix of the vertex transmissions in G. The eigenvalues of and will be denoted by and , respectively. In this paper, we study the properties of the distance Laplacian eigenvalues and the distance signless Laplacian eigenvalues of graph G. [ABSTRACT FROM AUTHOR]

The degree distance DD(G) of a connected graph G was invented by Dobrynin and Kochetova in 1994. Recently, one of the present authors introduced the concept of k-center Steiner degree distance defined as... where dG(S) is the Steiner k-distance of S and degG(v) is the degree of the vertex v in G. In this paper, we investigate the Steiner degree distance of complete and Cartesian product graphs. [ABSTRACT FROM AUTHOR]

A graph is almost self-centered (ASC) if all but two of its vertices are central. An almost self-centered graph with radius r is called an r-ASC graph. The r-ASC index θr(G) of a graph G is the minimum number of vertices needed to be added to G such that an r-ASC graph is obtained that contains G as an induced subgraph. It is proved that θr(G)≤2r holds for any graph G and any r≥2 which improves the earlier known bound θr(G)≤2r+1. It is further proved that θr(G)≤2r-1 holds if r≥3 and G is of order at least 2. The 3-ASC index of complete graphs is determined. It is proved that θ3(G)∈{3,4} if G has diameter 2 and for several classes of graphs of diameter 2 the exact value of the 3-ASC index is obtained. For instance, if a graph G of diameter 2 does not contain a diametrical triple, then θ3(G)=4. The 3-ASC index of paths of order n≥1, cycles of order n≥3, and trees of order n≥10 and diameter n-2 are also determined, respectively, and several open problems proposed. [ABSTRACT FROM AUTHOR]

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 Laplacian matrix and the signless Laplacian matrix of G are L(G)=D(G)-A(G) and Q(G)=D(G)+A(G), respectively. Also denote by λ1(G), a(G), q1(G) and δ(G) the largest eigenvalue of A(G), the second smallest eigenvalue of L(G), the largest eigenvalue of Q(G) and the minimum degree of G, respectively. In this paper, we give partial proofs to the following two conjectures: (i)Aouchiche (Comparaison Automatisée d’Invariants en Théorie des Graphes, 2006) if G is a connected graph, then a(G)/δ(G) is minimum for graph composed of 2 triangles linked with a path. (ii)Aouchiche et al. (Linear Algebra Appl 432:2293-2322, 2010) and Cvetković et al. (Publ Inst Math Beogr 81(95):11-27, 2007) if G is a connected graph with n≥4 vertices, then q1(G)-2λ1(G)≤n-2n-1 with equality holding if and only if G≅K1,n-1. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a connected graph with vertex set V(G) = {v1, v2,..., vn} and edge set E(G). Let D(G) be the distance matrix of G and λ1(D) ≥···≥ λn(D) be its distance spectrum. The distance between distance spectra of G and G' is defined by σ(G,G') = i=1∑n|λi(D(G)) - λi(D(G'))|. Define the cospectrality of G by cs(G) = min {i=1∑n|λi(D(G)) - λi(D(G'))|: G' not isomorphic to G}. Let csn = max{cs(G) : G a connected graph on n vertices}. In the paper, we obtain lower bounds on σ(G, Kn) and σ(G, Ka,b) for a+b = n. Furthermore, we give an upper bound on csn. [ABSTRACT FROM AUTHOR]

The aim of this note is to establish new spectral bounds for the harmonic matrix. [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]

Copyright of Canadian Journal of Chemistry is the property of Canadian Science Publishing and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

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 article offers information on the molecular graph G with vertex set V (G) and edge set E(G). It mentions that the Zagreb index of G is related to the degree of vertex in G. It offers information on the multiplicative Zagreb coindex and second multiplicative Zagreb coindex.. It offers information on the Narumi-Katayama index of a graph G, denoted by NK(G).

The first Zagreb index M1 is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M2 is equal to the sum of the products of the degrees of pairs of adjacent vertices of the respective graph. In this paper we present the lower bound on M1 and M2 among all unicyclic graphs of given order, maximum degree, and cycle length, and characterize graphs for which the bound is attained. Moreover, we obtain some relations between the Zagreb indices for unicyclic graphs. [ABSTRACT FROM AUTHOR]

Resistance distance was introduced by Klein and Randić as a generalisation of the classical distance. The Kirchhoff index Kf(G) of a graph G is the sum of resistance distances between all unordered pairs of vertices. In this article we characterise the extremal graphs with the maximal Kirchhoff index among all non-trivial quasi-tree graphs of order n. Moreover, we obtain a lower bound on the Kirchhoff index for all non-trivial quasi-tree graphs of order n. [ABSTRACT FROM AUTHOR]

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. In this paper, we determined the extremal (maximal and minimal) unicyclic and bicyclic graphs with respect to Harary index. [ABSTRACT FROM AUTHOR]

In this paper, we obtain the lower and upper bounds on the Harary index of a connected graph (molecular graph), and, in particular, of a triangle- and quadrangle-free graphs in terms of the number of vertices, the number of edges and the diameter. We give the Nordhaus–Gaddum-type result for Harary index using the diameters of the graph and its complement. Moreover, we compare Harary index and reciprocal complementary Wiener number for graphs. [ABSTRACT FROM AUTHOR]

The first Zagreb index M1( G) is equal to the sum of squares of the degrees of the vertices, and the second Zagreb index M2( G) is equal to the sum of the products of the degrees of pairs of adjacent vertices of the underlying molecular graph G. In this paper we obtain an upper bound on the first Zagreb index M1( G) of G in terms of the number of vertices ( n), number of edges ( m), maximum vertex degree (Δ1), second maximum vertex degree (Δ2) and minimum vertex degree ( δ). Using this result we find an upper bound on M2( G). Moreover, we present upper bounds on $${M_1(G)+M_1(\overline{G})}$$ and $${M_2(G)+M_2(\overline{G})}$$ in terms of n, m, Δ1, Δ2, δ, where $${\overline{G}}$$ denotes the complement of G. [ABSTRACT FROM AUTHOR]

Let G = ( V, E) be a simple graph with n vertices, e edges and d 1 be the highest degree. Further let λ i , i = 1,2,..., n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ2 = λ3 = ... = λ n-1 if and only if G is a complete graph or a star graph or a ( d 1, d 1) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d 1 only: The equality holds if and only if G is a star graph or a complete graph. Earlier bounds by Grimmett [5], Grone and Merris [6], Nosal [11], and Kelmans [2] were sharp for complete graphs only. Also our bound depends on n, e and d 1 only. [ABSTRACT FROM AUTHOR]

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]

Given a simple connected graph G, let D (G) be the distance matrix, D L (G) be the distance Laplacian matrix, D Q (G) be the distance signless Laplacian matrix, and T r (G) be the vertex transmission diagonal matrix of G. We introduce the generalized distance matrix D α (G) = α T r (G) + (1 − α) D (G) , where α ∈ [ 0 , 1 ] . Noting that D 0 (G) = D (G) , 2 D 1 2 (G) = D Q (G) , D 1 (G) = T r (G) and D α (G) − D β (G) = (α − β) D L (G) , we reveal that a generalized distance matrix ideally bridges the spectral theories of the three constituent matrices. In this paper, we obtain some sharp upper and lower bounds for the generalized distance energy of a graph G involving different graph invariants. As an application of our results, we will be able to improve some of the recently given bounds in the literature for distance energy and distance signless Laplacian energy of graphs. The extremal graphs of the corresponding bounds are also characterized. [ABSTRACT FROM AUTHOR]