The Distance Spectrum Does Not Determine Bipartiteness
Abstract
Over a decade ago, Koolen, Hayat, and Iqbal posed the problem of whether the distance spectrum determines bipartiteness within the class of connected graphs. In this paper, we resolve this problem in the negative: we explicitly construct an infinite family of counterexamples, where each pair comprises a connected bipartite graph and a connected non-bipartite graph with equal distance spectra.
Disclosure
“Acknowledgements The Python codes provided in Appendix A was generated with assistance from GPT-5.6-sol. All computational outputs have been independently verified by the authors. The authors bear full responsibility for the accuracy of the manuscript. References [1] A. Abiad, B. Brimkov, A. Erey, L. Leshock, X. Martínez-Rivera, S. O,”
PDF page 8
- Classification
- Code generation, completion, or debugging
- Multiplier
- 2
- Verified
Structural counts
Pages 9 pdf
Theorems 1 source
Lemmas 2 source
Propositions 0 source
Corollaries 2 source
Definitions 0 source
Displayed equations 38 source
Bibliography entries 6 source
Appendix pages 1 estimated
Count notes
- Source counts use the expanded primary TeX file distance_bipartite_counterexample.tex.
- Appendix pages include the first PDF page with an explicit Appendix heading through the final page.