Distance spectra of graphs: A survey

Mustapha Aouchiche; Pierre Hansen

doi:10.1016/j.laa.2014.06.010

Distance spectra of graphs: A survey

Mustapha Aouchiche, Pierre Hansen

Research output: Contribution to journal › Article › peer-review

205 Citations (Scopus)

Abstract

In 1971, Graham and Pollack established a relationship between the number of negative eigenvalues of the distance matrix and the addressing problem in data communication systems. They also proved that the determinant of the distance matrix of a tree is a function of the number of vertices only. Since then several mathematicians were interested in studying the spectral properties of the distance matrix of a connected graph. Computing the distance characteristic polynomial and its coefficients was the first research subject of interest. Thereafter, the eigenvalues attracted much more attention. In the present paper, we report on the results related to the distance matrix of a graph and its spectral properties.

Original language	English
Pages (from-to)	301-386
Number of pages	86
Journal	Linear Algebra and Its Applications
Volume	458
DOIs	https://doi.org/10.1016/j.laa.2014.06.010
Publication status	Published - Oct 1 2014
Externally published	Yes

Keywords

Characteristic polynomial
Distance matrix
Eigenvalues
Graph
Largest eigenvalue

ASJC Scopus subject areas

Algebra and Number Theory
Numerical Analysis
Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.laa.2014.06.010

Cite this

@article{1d1b8ef468414c7687c7f443cbcc1c2c,

title = "Distance spectra of graphs: A survey",

abstract = "In 1971, Graham and Pollack established a relationship between the number of negative eigenvalues of the distance matrix and the addressing problem in data communication systems. They also proved that the determinant of the distance matrix of a tree is a function of the number of vertices only. Since then several mathematicians were interested in studying the spectral properties of the distance matrix of a connected graph. Computing the distance characteristic polynomial and its coefficients was the first research subject of interest. Thereafter, the eigenvalues attracted much more attention. In the present paper, we report on the results related to the distance matrix of a graph and its spectral properties.",

keywords = "Characteristic polynomial, Distance matrix, Eigenvalues, Graph, Largest eigenvalue",

author = "Mustapha Aouchiche and Pierre Hansen",

year = "2014",

month = oct,

day = "1",

doi = "10.1016/j.laa.2014.06.010",

language = "English",

volume = "458",

pages = "301--386",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Distance spectra of graphs

T2 - A survey

AU - Aouchiche, Mustapha

AU - Hansen, Pierre

PY - 2014/10/1

Y1 - 2014/10/1

N2 - In 1971, Graham and Pollack established a relationship between the number of negative eigenvalues of the distance matrix and the addressing problem in data communication systems. They also proved that the determinant of the distance matrix of a tree is a function of the number of vertices only. Since then several mathematicians were interested in studying the spectral properties of the distance matrix of a connected graph. Computing the distance characteristic polynomial and its coefficients was the first research subject of interest. Thereafter, the eigenvalues attracted much more attention. In the present paper, we report on the results related to the distance matrix of a graph and its spectral properties.

AB - In 1971, Graham and Pollack established a relationship between the number of negative eigenvalues of the distance matrix and the addressing problem in data communication systems. They also proved that the determinant of the distance matrix of a tree is a function of the number of vertices only. Since then several mathematicians were interested in studying the spectral properties of the distance matrix of a connected graph. Computing the distance characteristic polynomial and its coefficients was the first research subject of interest. Thereafter, the eigenvalues attracted much more attention. In the present paper, we report on the results related to the distance matrix of a graph and its spectral properties.

KW - Characteristic polynomial

KW - Distance matrix

KW - Eigenvalues

KW - Graph

KW - Largest eigenvalue

UR - http://www.scopus.com/inward/record.url?scp=84903587605&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84903587605&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2014.06.010

DO - 10.1016/j.laa.2014.06.010

M3 - Article

AN - SCOPUS:84903587605

SN - 0024-3795

VL - 458

SP - 301

EP - 386

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Distance spectra of graphs: A survey

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this