Groupe d’études et de recherche en analyse des décisions

G-2014-68

Proximity, remoteness and distance eigenvalues of a graph

et

La proximité \(\pi\) et l'éloignement \(\rho\) sont respectivement le minimum et le maximum, pour les sommets d'un graphe connexe, de la distance moyenne d'un sommet vers les autres. Le rayon spectral des distances \(\partial_1\) d'un graphe connexe est la plus grande valeur propre de sa matrice des distances. Dans le présent article, nous nous intéressons à une comparaison entre la proximité et l'éloignement d'un graphe connexe d'une part et ses valeurs propres des distances d'autre part. Nous prouvons, entre autres résultats, des bornes inférieure et supérieure sur le rayon spectral des distances, en fonction de la proximité et de l'éloignement, et des bornes inférieures sur \(\partial_1 - \pi\) et sur \(\partial_1 - \rho\). De plus, nous proposons plusieurs conjectures obtenues avec l'aide d'AutoGraphiX.

, 14 pages