Spectral bipartiteness in generalized odd graphs of diameter three
Abstract
For a graph G of order n, put σ(G)=(λ1(G)+λn(G))/n. We determine the first three largest values of this invariant among nonbipartite distance-regular graphs of diameter three and odd girth at least seven. The unique maximizer is the folded $7$-cube, with value 1/32; the unique second maximizer is the Odd graph O4, with value 1/35; and the unique third maximizer is C7, with value 2(1−cos(π/7))/7. More precisely, every other graph in the class satisfies σ(G)<1/36. This answers Problem~11 of Abiad, Taranchuk and van Veluw in \emph{Electronic Journal of Combinatorics} 33(2) (2026), P2.31. The proof combines established local multiplicity and odd-moment bounds: the condition σ(G)≥1/36 forces the valency to be at most $182$. An exhaustive certificate using only integer and rational arithmetic then leaves three intersection arrays. The complete certificate is publicly available, and neither a classification of generalized odd graphs nor the Q-polynomial property is assumed. The odd-girth theorem gives the same extremal conclusions for connected {C3,C5}-free graphs with at most four distinct adjacency eigenvalues, without assuming regularity.
Related
- Generalized Spectral Closedness and the Nonexistence of Walk-Realizable Supporters for Split Graphs
- The spectral relation between irreducible cyclic codes and generalized Paley graphs
- On the Laplacian spectral gap of generalized pancake graphs
- Counterexamples to the Mao-Wu-Xu spectral conjecture and a three-scale boundary for spherical random graphs
- A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs
BibTeX
@misc{zhou2026spectral,
title = {{Spectral bipartiteness in generalized odd graphs of diameter three}},
author = {Qi Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11729},
eprint = {2609.11729},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11729},
}
RIS
TY - UNPB
TI - Spectral bipartiteness in generalized odd graphs of diameter three
AU - Qi Zhou
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11729
UR - https://arxiv.org/abs/2609.11729
AB - For a graph G of order n, put σ(G)=(λ_1(G)+λ_n(G))/n. We determine the first three largest values of this invariant among nonbipartite distance-regular graphs of diameter three and odd girth at least seven. The unique maximizer is the folded $7$-cube, with value 1/32; the unique second maximizer is the Odd graph O_4, with value 1/35; and the unique third maximizer is C_7, with value 2(1−cos(π/7))/7. More precisely, every other graph in the class satisfies σ(G)<1/36. This answers Problem~11 of Abiad, Taranchuk and van Veluw in \emph{Electronic Journal of Combinatorics} 33(2) (2026), P2.31. The proof combines established local multiplicity and odd-moment bounds: the condition σ(G)≥1/36 forces the valency to be at most $182$. An exhaustive certificate using only integer and rational arithmetic then leaves three intersection arrays. The complete certificate is publicly available, and neither a classification of generalized odd graphs nor the Q-polynomial property is assumed. The odd-girth theorem gives the same extremal conclusions for connected {C_3,C_5}-free graphs with at most four distinct adjacency eigenvalues, without assuming regularity.
ER -