We have previously determined the maximum-spread $K_{s, t}$-minor-free graph(s) on $n$ vertices when $n$ is sufficiently large, $2\le s\le t$, and $s=2$ or $t\ge \frac{3}{2}(s-3) + \frac{4}{s-1}$. In this sequel paper, we completely determine the maximum-spread $K_{s, t}$-minor-free graphs on $n$ vertices for $n$ sufficiently large and $2\le s\le t$. In all of the remaining cases, the extremal graph is unique and is of the form $(K_r \vee (s-1-r)K_1) \vee (\ell_r K_t \cup (n-s+1-t\ell_r)K_1)$, where $r$ is an integer determined by $s$ and $t$ and $\ell_r$ is an integer determined by $n, s, t,$ and $r$.
For a graph $G$, let $ \lambda_1(G)\ge \lambda_2(G)\ge \cdots \ge \lambda_n(G)$ denote the adjacency eigenvalues of $G$. We investigate the asymptotic maximum of \[ \lambda_i(G)+\lambda_j(\overline G) \] for fixed $i$ and $j$. We prove general bounds on $\lambda_i(G) + \lambda_{j}(\overline{G})$ for all pairs $(i, j)$ and also give general bounds on the related problem of minimizing $\lambda_{n-i+1}(G) + \lambda_{n-j+1}(\overline{G})$ for fixed $i$ and $j$. We prove that for all looped graphs $G$ on $n$ vertices, \[\lambda_1(G) + \lambda_2(\overline{G}) \le \frac87 n. \] Our method also gives a new short proof of the Nordhaus-Gaddum result for the spectral radius proved by Terpai that $\lambda_1(G) + \lambda_1(\overline{G}) \le \frac43n - 1$. We also show the close relation of these Nordhaus-Gaddum type problems to recent work on the maximum spectral gaps of graphs by Brooks, Linz and Lu.
Sahil Agarwal, Carter Antley, Joseph Aulenbacher et al.· 1 citation· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
