Resolutions of two conjectures on the spectral diameter
Abstract
Let λ1(G) ≥ … ≥ λn(G) be the adjacency spectrum of a graph G on n vertices. The spectral distance σ(G,H) between n-vertex graphs G and H is the Manhattan distance between their spectra, i.e. σ(G,H) = ∑i=1n |λi(G) − λi(H)|. Given a set 𝒢 of pairwise non-isomorphic graphs of order n, the spectral diameter of 𝒢 is defined as sdiam(𝒢) = max{secc𝒢(G) : G ∈ 𝒢}, where secc𝒢(G) = max{σ(G,H) : H ∈ 𝒢} is the spectral eccentricity of G ∈ 𝒢. Among six conjectures on spectral distances posed by Z. Stanić in 2012, two conjectures related to the spectral diameter of certain graph classes remained open. One of them concerns the spectral diameter of the set ℬn of all connected bipartite graphs of order n, while the other, of the set 𝒯n of all trees of order n. More precisely, Stanić conjectured that sdiam(𝒯n) = σ(Pn, K1,n−1), where Pn is the path graph, while K1,n−1 is the star, and that sdiam(ℬn) = seccℬn(K⌈ n/2 ⌉, ⌊ n/2 ⌋), where K⌈ n/2 ⌉, ⌊ n/2 ⌋ is the complete bipartite graph. In this paper, both of these conjectures are disproved.
Related
- Counterexamples to two conjectures on the diameter of clique-free graphs
- Lemmas and Conjectures in Spectral Graph Theory
- Proofs of Li, Wang and Guo's conjectures on (signless) Laplacian spectral radius
- Spectral bipartiteness in generalized odd graphs of diameter three
- Characterizing multigraded regularity and virtual resolutions on products of projective spaces
BibTeX
@misc{jovanovic2026resolutions,
title = {{Resolutions of two conjectures on the spectral diameter}},
author = {Irena M. Jovanović and Jelena Sedlar and Riste Škrekovski},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.29632},
eprint = {2609.29632},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29632},
}
RIS
TY - UNPB
TI - Resolutions of two conjectures on the spectral diameter
AU - Irena M. Jovanović
AU - Jelena Sedlar
AU - Riste Škrekovski
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.29632
UR - https://arxiv.org/abs/2609.29632
AB - Let λ_1(G) ≥ … ≥ λ_n(G) be the adjacency spectrum of a graph G on n vertices. The spectral distance σ(G,H) between n-vertex graphs G and H is the Manhattan distance between their spectra, i.e. σ(G,H) = ∑_i=1^n |λ_i(G) − λ_i(H)|. Given a set 𝒢 of pairwise non-isomorphic graphs of order n, the spectral diameter of 𝒢 is defined as sdiam(𝒢) = max{secc_𝒢(G) : G ∈ 𝒢}, where secc_𝒢(G) = max{σ(G,H) : H ∈ 𝒢} is the spectral eccentricity of G ∈ 𝒢. Among six conjectures on spectral distances posed by Z. Stanić in 2012, two conjectures related to the spectral diameter of certain graph classes remained open. One of them concerns the spectral diameter of the set ℬ_n of all connected bipartite graphs of order n, while the other, of the set 𝒯_n of all trees of order n. More precisely, Stanić conjectured that sdiam(𝒯_n) = σ(P_n, K_1,n−1), where P_n is the path graph, while K_1,n−1 is the star, and that sdiam(ℬ_n) = secc_ℬ_n(K_⌈ n/2 ⌉, ⌊ n/2 ⌋), where K_⌈ n/2 ⌉, ⌊ n/2 ⌋ is the complete bipartite graph. In this paper, both of these conjectures are disproved.
ER -