Graphs with three distinct distance eigenvalues, one of which is zero

Abstract

Koolen, Hayat and Iqbal asked for the connected graphs whose distance matrix has exactly three distinct eigenvalues, the middle one being $0$. The examples they gave, namely the Johnson graphs, the Hamming graphs and the halved cubes, are distance-regular. In this note, we show that the distance spectrum of such a graph is {ρ,0,−c} with integers c≥2 and c|ρ. For c=2 the graphs are exactly the cocktail party graphs, and for c=3 they are exactly the Cartesian product K₃ □ K₃ of two triangles, the Petersen graph and its complement. We also show that such a graph need not be transmission-regular: Seidel switching the lattice graph K₆ □ K₆ with respect to a line and the triangular graph T(11) with respect to a maximal clique of size $10$ gives graphs on $36$ and $55$ vertices with distance spectra {54,0⁽²⁶⁾,(−6)⁽⁹⁾} and {81,0⁽⁴⁵⁾,(−9)⁽⁹⁾}. Among the graphs of diameter $2$ obtained by switching a strongly regular graph with smallest eigenvalue −2 with respect to one part of an equitable partition, these two are the only ones that have exactly three distance eigenvalues and are not transmission-regular. We also observe that the transmission-regular graphs with exactly three distinct distance eigenvalues, the smallest one being −3, are exactly the complements of the strongly regular graphs with smallest eigenvalue −2 other than the cocktail party graphs.

Threshold Graphs Allow Few Distinct Eigenvalues: A New Approach
Jane Breen, Shaun Fallat, Johnna Parenteau
arXiv8 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Graphs with three eigenvalues from group divisible designs
Gary Greaves, Jose Yip
arXiv15 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
On Hamming Eigenvalues and Hamming Energy of Graphs
Harishchandra S. Ramane, Mallappa P. Mellikeri, Daneshwari D. Patil +1
Discrete Mathematics Letters25 Oct 2026Peer-reviewedCC BYFull textGeometry & topologyDOAJ
On the Brouwer-type Conjecture for Signless Laplacian Eigenvalues of Graphs
Ruisong Yuan, Xiao-Dong Zhang
arXiv25 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Convergence of cyclic steepest descent for quadratics with two distinct eigenvalues
Yu Li, Qihang Wang
arXiv15 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{suil2026graphs,
  title = {{Graphs with three distinct distance eigenvalues, one of which is zero}},
  author = {Suil O},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.00126},
  eprint = {2611.00126},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.00126},
}

RIS

TY  - UNPB
TI  - Graphs with three distinct distance eigenvalues, one of which is zero
AU  - Suil O
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.00126
UR  - https://arxiv.org/abs/2611.00126
AB  - Koolen, Hayat and Iqbal asked for the connected graphs whose distance matrix has exactly three distinct eigenvalues, the middle one being $0$. The examples they gave, namely the Johnson graphs, the Hamming graphs and the halved cubes, are distance-regular. In this note, we show that the distance spectrum of such a graph is {ρ,0,−c} with integers c≥2 and c|ρ. For c=2 the graphs are exactly the cocktail party graphs, and for c=3 they are exactly the Cartesian product K_3 □ K_3 of two triangles, the Petersen graph and its complement. We also show that such a graph need not be transmission-regular: Seidel switching the lattice graph K_6 □ K_6 with respect to a line and the triangular graph T(11) with respect to a maximal clique of size $10$ gives graphs on $36$ and $55$ vertices with distance spectra {54,0^(26),(−6)^(9)} and {81,0^(45),(−9)^(9)}. Among the graphs of diameter $2$ obtained by switching a strongly regular graph with smallest eigenvalue −2 with respect to one part of an equitable partition, these two are the only ones that have exactly three distance eigenvalues and are not transmission-regular. We also observe that the transmission-regular graphs with exactly three distinct distance eigenvalues, the smallest one being −3, are exactly the complements of the strongly regular graphs with smallest eigenvalue −2 other than the cocktail party graphs.
ER  -

Abstract

Related

Cite