Koolen–Hayat–Iqbal distance-spectrum problem

For all connected graphs $G$ and $H$ , if their distance matrices $D(G)$ and $D(H)$ are cospectral, meaning that $\operatorname{Spec}(D(G))=\operatorname{Spec}(D(H))$ , then $G$ is bipartite if and only if $H$ is bipartite.

Progress summary

Solved

A new preprint answers the question negatively: distance information alone does not determine whether a graph is bipartite.

The problem asks whether a graph’s distance spectrum determines bipartiteness. It is named for Koolen, Hayat, and Iqbal; no posing date was supplied.

August 2026 negative answer

A. Abiad and A. E. Brouwer report in a new arXiv preprint that the distance spectrum does not determine bipartiteness, resolving the question negatively.

Current status (as of August 2026): The question is resolved negatively; distance spectrum does not determine bipartiteness.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

arXiv

Additional references

The Distance Spectrum Does Not Determine Bipartiteness — arXiv — A. Abiad, A. E. Brouwer

spectral-graph-theory

2 days ago

No solutions have been posted yet.