ICAR Research Data Repository for Knowledge Management
Average distance in graphs and eigenvalues
DSpace at IIT Bombay
View Archive Info| Field | Value | |
| Title |
Average distance in graphs and eigenvalues
|
|
| Creator |
SIVASUBRAMANIAN, S
|
|
| Subject |
average distance
eigenvalues laplacian |
|
| Description |
Brendan McKay gave the following formula relating the average distance between pairs of vertices in a tree T and the eigenvalues of its Laplacian: (d) over bar (T) = 2/n-1 Sigma(n)(i=2) 1/lambda(i). By modifying Mohar's proof of this result, we prove that for any graph G, its average distance, (d) over bar (G), between pairs of vertices satisfies the following inequality: (d) over bar (G) >= 2/n-1 Sigma(n)(i=2) 1/lambda(i). This solves a conjecture of Graffiti. We also present a generalization of this result to the average of suitably defined distances for k subsets of a graph. (C) 2008
|
|
| Publisher |
ELSEVIER SCIENCE BV
|
|
| Date |
2011-07-24T11:04:31Z
2011-12-26T12:52:33Z 2011-12-27T05:38:38Z 2011-07-24T11:04:31Z 2011-12-26T12:52:33Z 2011-12-27T05:38:38Z 2009 |
|
| Type |
Article
|
|
| Identifier |
DISCRETE MATHEMATICS, 309(10), 3458-3462
0012-365X http://dx.doi.org/10.1016/j.disc.2008.09.044 http://dspace.library.iitb.ac.in/xmlui/handle/10054/6404 http://hdl.handle.net/10054/6404 |
|
| Language |
en
|
|