Group for Research in Decision Analysis

# Proximity, remoteness and distance eigenvalues of a graph

## Mustapha Aouchiche and Pierre Hansen

Proximity $$\pi$$ and remoteness $$\rho$$ are respectively the minimum and the maximum, over the vertices of a connected graph, of the average distance from a vertex to others. The distance spectral radius $$\partial_1$$ of a connected graph is the largest eigenvalue of its distance matrix. In the present paper, we are interested in a comparison between the proximity and the remoteness of a simple connected graph on the one hand and its distance eigenvalues on the other hand. We prove, among other results, lower and upper bound on the distance spectral radius using proximity and remotemess, and lower bounds on $$\partial_1 - \pi$$ and on $$\partial_1 - \rho$$. In addition, several conjectures, obtained with the help of the system AutoGraphiX, are formulated.

, 14 pages