Article ID Journal Published Year Pages File Type
420348 Discrete Applied Mathematics 2010 6 Pages PDF
Abstract

Let G=(V,E)G=(V,E) be a simple, undirected graph of order nn and size mm with vertex set VV, edge set EE, adjacency matrix AA and vertex degrees Δ=d1≥d2≥⋯≥dn=δΔ=d1≥d2≥⋯≥dn=δ. The average degree of the neighbor of vertex vivi is mi=1di∑j=1naijdj. Let DD be the diagonal matrix of degrees of GG. Then L(G)=D(G)−A(G)L(G)=D(G)−A(G) is the Laplacian matrix of GG and Q(G)=D(G)+A(G)Q(G)=D(G)+A(G) the signless Laplacian matrix of GG. Let μ1(G)μ1(G) denote the index of L(G)L(G) and q1(G)q1(G) the index of Q(G)Q(G). We survey upper bounds on μ1(G)μ1(G) and q1(G)q1(G) given in terms of the didi and mimi, as well as the numbers of common neighbors of pairs of vertices. It is well known that μ1(G)≤q1(G)μ1(G)≤q1(G). We show that many but not all upper bounds on μ1(G)μ1(G) are still valid for q1(G)q1(G).

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,