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

DOI10.1016/J.DISC.2013.10.010MaRDI QIDQ393167zbMATH OpenOpenAlexFDO

Authors Jernej Azarija

Publication date 16 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.4517

zbMATH Keywords

distance matrixdistance spectrumPaley graphstrongly regular graph

Mathematics Subject Classification ID

Trees (05C05) Eigenvalues, singular values, and eigenvectors (15A18)

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.

Recommendations

• Distance spectra of graphs: a survey
• Graphs whose distance matrix has at most three negative eigenvalues
• On graphs with at least three distance eigenvalues less than \(-1\)
• On the distance spectra of graphs
• Graphs with at most three distance eigenvalues different from \(-1\) and \(-2\)

Cites work

• A course in combinatorics.
• Distance matrix polynomials of trees
• Handbook of product graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• On the Addressing Problem for Loop Switching

Cited in

(8)

• Distance spectra of graphs: a survey
• On a conjecture of Graham and Lovász about distance matrices
• On the distance spectra of graphs
• The generalized distance spectrum of a graph and applications
• Distance Signatures of Extended and Co-extended Incidence Graphs of Affine Designs
• Spectra of variants of distance matrices of graphs and digraphs: a survey
• On a symmetric representation of Hermitian matrices and its applications to graph theory
• The distance signatures of the incidence graphs of affine resolvable designs

This page was built for publication: A short note on a short remark of Graham and Lovász

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393167)