Resolutions of two conjectures on the spectral diameter

Abstract

Let ${\lambda }_1(G)\ge \cdots \ge {\lambda }_n(G)$ be the adjacency spectrum of a graph $G$ on $n$ vertices. The spectral distance $\sigma (G,H)$ between $n$-vertex graphs $G$ and $H$ is the Manhattan distance between their spectra, i.e. $\sigma (G,H)={\sum }_{i=1}^n|{\lambda }_i(G)-{\lambda }_i(H)|$. Given a set $\mathcal{G}$ of pairwise non-isomorphic graphs of order $n$, the spectral diameter of $\mathcal{G}$ is defined as $\mathrm{sdiam}(\mathcal{G})=\max \{{\mathrm{secc}}_{\mathcal{G}}(G):G\in \mathcal{G}\}$, where ${\mathrm{secc}}_{\mathcal{G}}(G)=\max \{\sigma (G,H):H\in \mathcal{G}\}$ is the spectral eccentricity of $G\in \mathcal{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 ${\mathcal{B}}_n$ of all connected bipartite graphs of order $n$, while the other, of the set ${\mathcal{T}}_n$ of all trees of order $n$. More precisely, Stanić conjectured that $\mathrm{sdiam}({\mathcal{T}}_n)=\sigma (P_n,K_{1,n-1})$, where $P_n$ is the path graph, while $K_{1,n-1}$ is the star, and that $\mathrm{sdiam}({\mathcal{B}}_n)={\mathrm{secc}}_{{\mathcal{B}}_n}(K_{\lceil n/2\rceil ,\lfloor n/2\rfloor })$, where $K_{\lceil n/2\rceil ,\lfloor n/2\rfloor }$ is the complete bipartite graph. In this paper, both of these conjectures are disproved.

arXiv comment15 pages, 2 figures