A short note on a short remark of Graham and Lovász

2013/03/19 by Jernej Azarija, Azarija, Jernej
Computer Science · Mathematics · #05C12 #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #Matrix Theory and Algorithms #math.CO #msc:05C12 #msc:05C50

paper · pdf · doi:10.48550/arxiv.1303.4517

5 pages, 3 figures

openalex publication_date 2013/03/19 · arxiv created 2013/09/30 · arxiv updated 2013/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let D be the distance matrix of a connected graph G and let nn(G), np(G) be the number of strictly negative and positive eigenvalues of D respectively. It was remarked in [1] that it is not known whether there is a graph for which np(G) > nn (G). In this note we show that there exists an infinite number of graphs satisfying the stated inequality, namely the conference graphs of order> 9. A large representative of this class being the Paley graphs.The result is obtained by derving the eigenvalues of the distance matrix of a strongly-regular graph.

Related

• Graphs with at most three distance eigenvalues different from -1 and -2
• The distance-regular graphs such that all of its second largest local eigenvalues are at most one
• Remoteness and distance eigenvalues of a graph
• On the distance spectra of graphs
• Minimum number of distinct eigenvalues of distance-regular and signed Johnson graphs