# On the spread of outerplanar graphs

Daniel Gotshall Department of Mathematics & Statistics, Villanova University,
email addresses {dgotshall, mobrie71<EMAIL_ADDRESS>The third
author is partially supported by National Science Foundation grant
DMS-2011553. Megan O’Brien11footnotemark: 1 Michael Tait11footnotemark: 1

###### Abstract

The spread of a graph is the difference between the largest and most negative
eigenvalue of its adjacency matrix. We show that for sufficiently large $n$,
the $n$-vertex outerplanar graph with maximum spread is a vertex joined to a
linear forest with $\Omega(n)$ edges. We conjecture that the extremal graph is
a vertex joined to a path on $n-1$ vertices.

##  1 Introduction

The spread of a square matrix $M$ is defined to be

$S(M):=\max_{i,j}|\lambda_{i}-\lambda_{j}|,$

where the maximum is taken over all pairs of eigenvalues of $M$. That is,
$S(M)$ is the diameter of the spectrum of $M$. The spread of general matrices
has been studied in several papers (e.g. [4, 9, 18, 24, 25, 34, 37]). In this
paper, given a graph $G$ we will study the spread of the adjacency matrix of
$G$, and we will call this quantity the spread of $G$ and denote it by $S(G)$.
Since the adjacency matrix of an $n$-vertex graph is real and symmetric, it
has a full set of real eigenvalues which we may order as
$\lambda_{1}\geq\cdots\geq\lambda_{n}$. In this case, the spread of $G$ is
given simply by $\lambda_{1}-\lambda_{n}$.

The study of the spread of graphs was introduced in a systematic way by
Gregory, Hershkowitz, and Kirkland in [15]. Since then, the spread of graphs
has been studied extensively. A problem in this area with an extremal flavor
is to maximize or minimize the spread over a fixed family of graphs. This
problem has been considered for trees [1], graphs with few cycles [13, 27,
38], the family of all $n$-vertex graphs [3, 6, 29, 31, 32, 35], bipartite
graphs [6], graphs with a given matching number [19] or girth [36] or size
[22].

We also note that spreads of other matrices associated with a graph have been
considered extensively (e.g. [2, 12, 14, 16, 21, 23, 26, 39, 40, 41]), but in
this paper we will focus on the adjacency matrix. This paper examines the
question of maximizing the spread of an $n$-vertex outerplanar graph. A graph
is outerplanar if it can be drawn in the plane with no crossings and such that
all vertices are incident with the unbounded face. Similarly to Wagner’s
theorem characterizing planar graphs, a graph is outerplanar if and only if it
does not contain either $K_{2,3}$ or $K_{4}$ as a minor. Maximizing the spread
of this family of graphs is motivated by the extensive history on maximizing
eigenvalues of planar or outerplanar graphs, for example [5, 7, 8, 10, 11, 17,
20, 28, 30, 42, 43].

Our main theorem comes close to determining the outerplanar graph of maximum
spread. Let $P_{k}$ denote the path on $k$ vertices and $G\vee H$ the join of
$G$ and $H$. A linear forest is a disjoint union of paths.

######  Theorem 1.1.

For $n$ sufficiently large, any graph which maximizes spread over the family
of outerplanar graphs on $n$ vertices is of the form $K_{1}\vee F$ where $F$
is a linear forest with $\Omega(n)$ edges.

We leave it as an open problem to determine whether or not $F$ should be a
path on $n-1$ vertices, and we conjecture that this is the case.

######  Conjecture 1.2.

For $n$ sufficiently large, the unique $n$-vertex outerplanar graph of maximum
spread is $K_{1}\vee P_{n-1}$.

##  2 Preliminaries

Let $G$ be an outerplanar graph of maximum spread and let $A$ be its
adjacency. We will frequently assume that $n$ is sufficiently large. We will
use the characterization that a graph is outerplanar if and only it does not
contain $K_{2,3}$ or $K_{4}$ as a minor. In particular, $G$ does not contain
$K_{2,3}$ as a subgraph. Given a vertex $v\in V(G)$, the neighborhood of $v$
will be denoted by $N(v)$ and its degree by $d_{v}$. If
$f,g:\mathbb{N}\to\mathbb{R}$ we will use $f=\mathcal{O}(g)$ to mean that
there exists a constant $c$ such that $f(n)\leq cg(n)$ for $n$ sufficiently
large. $f=\Omega(g)$ means that $g=\mathcal{O}(f)$ and $f=\Theta(g)$ means
that $f=\mathcal{O}(g)$ and $g=\mathcal{O}(f)$. We will occasionally have
sequences of inequalities where we will abuse notation and mix inequality
symbols with $\mathcal{O}(\cdot)$ and $\Theta(\cdot)$.

Let the eigenvalues of $A$ be represented as
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$. For any disconnected
graph, adding an edge between the connected components will not decrease
$\lambda_{1}$ and will also not decrease $-\lambda_{n}$. Therefore, without
loss of generality, we may assume that $G$ is connected. By the Perron-
Frobenius theorem we may assume that the eigenvector $\mathbf{x}$
corresponding to $\lambda_{1}$ has $\mathbf{x}_{u}>0$ for all $u$.

Furthermore, we will normalize $\mathbf{x}$ so that it has maximum entry equal
to $1$, and let $\mathbf{x}_{w}=1$ where $w$ is a vertex attaining the maximum
entry in $\mathbf{x}$. Note there may be more than one such vertex, in which
case we can arbitrarily choose and fix $w$ among all such vertices. The other
eigenvector of interest to us corresponds to $\lambda_{n}$, call it
$\mathbf{z}$. We will also normalize $\mathbf{z}$ so that its largest entry in
absolute value has absolute value $1$ and let $w^{\prime}$ correspond to a
vertex with maxumum absolute value in $\mathbf{z}$ (so
$\mathbf{x}_{w^{\prime}}$ equals $1$ or $-1$).

We will implement the following known equalities for the largest and smallest
eigenvalues:

$\displaystyle\lambda_{1}=\max\limits_{\mathbf{x}^{\prime}\neq 0}$
$\displaystyle\frac{(\mathbf{x}^{\prime})^{t}A\mathbf{x}^{\prime}}{(\mathbf{x}^{\prime})^{t}\mathbf{x}^{\prime}}=\frac{\mathbf{x}^{t}A\mathbf{x}}{\mathbf{x}^{t}\mathbf{x}}$
(2.1) $\displaystyle\lambda_{n}=\min\limits_{\mathbf{z}^{\prime}\neq 0}$
$\displaystyle\frac{(\mathbf{z}^{\prime})^{t}A\mathbf{z}^{\prime}}{(\mathbf{z}^{\prime})^{t}\mathbf{z}^{\prime}}=\frac{\mathbf{z}^{t}A\mathbf{z}}{\mathbf{z}^{t}\mathbf{z}}$
(2.2)

An important result from equations 2.1 and 2.2 and the Perron-Frobenius
Theorem is that for any strict subgraph $H$ of $G$, we have
$\lambda_{1}(A(G))>\lambda_{1}(A(H))$. Finally, we will use the following
theorem from [33]

######  Theorem 2.3.

For $n$ large enough, $K_{1}\vee P_{n-1}$ has maximum spectral radius over all
$n$-vertex outerplanar graphs.

##  3 Vertex of Maximum Degree

The main goal of this section is to prove that $G$ has a vertex of degree
$n-1$. This is stated in the following theorem.

######  Theorem 3.1.

For $n$ large enough, we have $d_{w}=n-1$.

As a first step, we will get preliminary upper and lower bounds on the largest
and smallest eigenvalues of $G$. First we obtain an upper bound on the
spectral radius.

######  Lemma 3.2.

$\lambda_{1}\leq\sqrt{n}+1$.

###### Proof.

We define the graph $G_{1}$ to be the graph $K_{1}\vee P_{n-1}$. By Theorem
2.3, we know that any outerplanar graph on sufficiently many vertices cannot
have a spectral radius larger than that of $G_{1}$. Now define $G_{2}$ as
$G_{1}$ with another edge joining the endpoints of the path, so
$G_{2}=K_{1}\vee C_{n-1}$. Clearly $G_{1}$ is a subgraph of $G_{2}$. Putting
all this together gives us

$\displaystyle\lambda_{1}(G)\leq\lambda_{1}(G_{1})<\lambda_{1}(G_{2})=\sqrt{n}+1,$

where the last equality can be calculated using an equitable partition with
two parts (the dominating vertex and the cycle). ∎

Next we bound $|\lambda_{n}|$.

######  Lemma 3.3.

For $n$ sufficiently large, $\sqrt{n-1}-2\leq|\lambda_{n}|\leq\sqrt{n-1}+2$.

###### Proof.

The upper bound on $|\lambda_{n}|$ follows immediately from Lemma 3.2 and the
well-known fact $\lambda_{1}\geq|\lambda_{n}|$ for any graph. Now to get the
lower bound, since $G$ is the outerplanar graph on $n$ vertices that maximizes
spread, we have

$\displaystyle S(G)$ $\displaystyle\geq S(K_{1,n-1})$
$\displaystyle=\lambda_{1}(K_{1,n-1})-\lambda_{n}(K_{1,n-1})$
$\displaystyle=\sqrt{n-1}-(-\sqrt{n-1})$ $\displaystyle=2\sqrt{n-1}.$

So

$2\sqrt{n-1}\leq\lambda_{1}(G)-\lambda_{n}(G)\leq\sqrt{n}+1-\lambda_{n}(G)<\sqrt{n-1}+2-\lambda_{n}(G).$

Hence we have

$-\lambda_{n}\geq\sqrt{n-1}-2.$

∎

Essentially the same proof also gives a lower bound for $\lambda_{1}$.

######  Corollary 3.4.

For $n$ large enough we have $\lambda_{1}\geq\sqrt{n-1}-2$.

We shall use Lemma 3.3 to obtain a lower bound on the degree of each vertex.

######  Lemma 3.5.

Let $u$ be an arbitrary vertex in $G$. Then
$d_{u}>|\mathbf{z}_{u}|n-\mathcal{O}(\sqrt{n})$ and
$d_{u}>\mathbf{x}_{u}n-\mathcal{O}(\sqrt{n})$.

###### Proof.

We will show the first part explicitly. When $\lambda_{n}$ is the smallest
eigenvalue for our graph, we have

$\displaystyle|\lambda_{n}^{2}\mathbf{z}_{u}|$
$\displaystyle=\left|\sum\limits_{y\sim u}\sum\limits_{v\sim
y}\mathbf{z}_{v}\right|$ $\displaystyle\leq d_{u}+\sum\limits_{y\sim
u}\sum_{\begin{subarray}{c}v\sim y\\\ v\not=u\end{subarray}}|\mathbf{z}_{v}|.$

Recall that an outerplanar graph cannot have a $K_{2,3}$. This implies every
vertex in $G$ has at most two neighbors in $N(u)$, meaning the eigenvector
entry for each vertex contained in the neighborhood of $N(u)$ can be counted
at most twice. Hence $\sum\limits_{y\sim u}\sum\limits_{v\sim
y}|\mathbf{z}_{v}|\leq 2\sum\limits_{v\not=w}|\mathbf{z}_{v}|$. Note

$|\lambda_{n}||\mathbf{z}_{v}|\leq\sum\limits_{v^{\prime}\sim
v}|\mathbf{z}_{v^{\prime}}|\leq\sum\limits_{v^{\prime}\sim v}1=d_{v}.$

So we have

$\sum_{y\sim u}\sum_{v\sim y}|\mathbf{z}_{v}|\leq
2\sum_{v\not=w}|\mathbf{z}_{v}|\leq\frac{2}{|\lambda_{n}|}\sum\limits_{v\not=w}d_{v}\leq\frac{4e(G)}{|\lambda_{n}|}\leq\frac{4(2n-3)}{|\lambda_{n}|},$

as $e(G)\leq 2n-3$ by outerplanarity. Combining and using Lemma 3.3, we have

$(\sqrt{n-1}-2)^{2}|\mathbf{z}_{u}|\leq|\lambda_{n}^{2}\mathbf{z}_{u}|\leq
d_{u}+\frac{4(2n-3)}{|\lambda_{n}|}\leq d_{u}+\frac{8n}{\sqrt{n-1}-2},$

for $n$ sufficiently large. Isolating $d_{u}$ gives the result. A similar
proof can be written to justify the lower bound with respect to $\mathbf{x}$
and we omit these details.

∎

######  Lemma 3.6.

We have $d_{w}>n-\mathcal{O}(\sqrt{n})$ and
$d_{w^{\prime}}>n-\mathcal{O}(\sqrt{n})$. For every other vertex $u$ we get
$|\mathbf{z}_{u}|,\mathbf{x}_{u}=\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$,
for n sufficiently large.

###### Proof.

The bound on $d_{w}$ and $d_{w^{\prime}}$ follows immediately from the
previous lemma and the normalization that
$|\mathbf{z}_{w^{\prime}}|=\mathbf{x}_{w}=1$. Now consider any other vertex
$u$. We know that $G$ contains no $K_{2,3}$ and hence can have at most $2$
common neighbors with $w$. Thus $d_{u}=\mathcal{O}(\sqrt{n})$. By Lemma 3.5,
we have that there are constants $c_{1}$ and $c_{2}$ such that

$c_{1}\sqrt{n}>d_{u}\mathbf{x}_{u}-c_{2}\sqrt{n},$

and

$c_{1}\sqrt{n}>d_{u}|\mathbf{z}_{u}|-c_{2}\sqrt{n},$

for sufficiently large $n$. This implies the result. ∎

If $w$ and $w^{\prime}$ were distinct vertices, then for sufficiently large
$n$ they would share many neighbors, contradicting outerplanarity. Hence we
immediately have the following important fact.

######  Corollary 3.7.

For $n$ sufficiently large we have $w=w^{\prime}$.

Hence from now on, we will denote the vertex in Corollary 3.7 by $w$, and
furthermore for the remainder of the paper we will also assume that
$\mathbf{z}_{w}=1$ without loss of generality. Before deriving our next result
quantifying the other entries of $\mathbf{z}$, we first need to define an
important vertex set.

######  Definition 3.8.

Recall that $w$ is the fixed vertex of maximum degree in $G$. Let
$B=V(G)\backslash(N(w)\cup\\{w\\})$.

Now we consider the $\mathbf{z}_{u}$ eigenvector entries of vertices in $B$.
At the moment we know that each eigenvector entry for a vertex in $B$ has
order at most $\frac{1}{\sqrt{n}}$. The next lemma shows that in fact the sum
of all of the eigenvector entries of $B$ has this order.

######  Lemma 3.9.

For $n$ large enough, we have that $\sum\limits_{u\in B}|\mathbf{z}_{u}|$ and
$\sum\limits_{u\in B}\mathbf{x}_{u}$ are each
$\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$.

###### Proof.

Let $u\in B$. Since $u$ is not adjacent to $w$, all of the neighbors of $u$
have eigenvector entry of order at most $1/\sqrt{n}$ and the size of $B$ is
also of order at most $1/\sqrt{n}$ by Lemma 3.6. Hence there is a constant $C$
such that

$|\lambda_{n}||\mathbf{z}_{u}|\leq\sum_{v\sim
u}|\mathbf{z}_{v}|\leq\frac{Cd_{u}}{\sqrt{n}},$

and $|B|\leq C\sqrt{n}$. Now

$\sum_{u\in B}|\mathbf{z}_{u}|\leq\frac{1}{|\lambda_{n}|}\sum_{u\in
B}\left(\frac{Cd_{u}}{\sqrt{n}}\right)\leq\frac{C}{|\lambda_{n}|\sqrt{n}}(e(B,V(G)\setminus
B)+2e(B)).$

Each vertex in $B$ is connected to at most two vertices in $N(u)$, so
$e(B,V(G)\setminus B)\leq 2|B|\leq 2C\sqrt{n}$. The graph induced on $B$ is
outerplanar, so $e(B)\leq 2|B|-3<2C\sqrt{n}$. Finally, using Lemma 3.3, we get
the required result. A slightly modified version of this argument proves the
bound on $\sum\limits_{u\in B}\mathbf{x}_{u}$. ∎

We will use Lemma 3.9 to show that $B$ is empty, and this will complete the
proof of Theorem 3.1. First we define the following alteration of $G$. Let $t$
be an arbitrary vertex in $B$ (if it exists).

######  Definition 3.10.

Let $G^{*}$ be the graph defined such that its adjacency matrix $A^{*}$
satisfies

$A^{*}_{ij}=\begin{cases}1&$if $i=w,j=t\\\ 0&$if $i=t,j\not=w\\\
A_{ij}&$otherwise$\end{cases}$

That is, to get $G^{*}$ from $G$ we add an edge from $t$ to $w$ and remove all
other edges incident with $t$. In particular, the only neighbor of the $t$
vertex in $G^{*}$ is $w$.

######  Lemma 3.11.

For large enough $n$, $B$ is empty.

###### Proof.

Assume for contradiction that $B$ is nonempty. Then there is a vertex $t$ such
that $t\not\sim w$. Define $G^{*}$ as in Definition 3.10. Furthermore, we
define the vector $\mathbf{z}^{*}$ which slightly modifies $\mathbf{z}$ as
follows.

$\mathbf{z}^{*}_{u}=\begin{cases}\mathbf{z}_{u}&\mbox{if $u\not=t$}\\\
-|\mathbf{z}_{u}|&\mbox{if $u=t$}\end{cases}$

That is, if $\mathbf{z}_{t}<0$ then $\mathbf{z}^{*}$ is the same vector as
$\mathbf{z}$ and otherwise we flip the sign of $\mathbf{z}_{t}$. Note that
$(\mathbf{z}^{*})^{T}\mathbf{z}^{*}=\mathbf{z}^{T}\mathbf{z}$. Now

$\displaystyle S(G^{*})-S(G)$
$\displaystyle\geq\left(\frac{\mathbf{x}^{T}A^{*}\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}-\frac{(\mathbf{z^{*}})^{T}A^{*}\mathbf{z^{*}}}{\mathbf{z}^{T}\mathbf{z}}\right)-\left(\frac{\mathbf{x}^{T}A\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}-\frac{\mathbf{z}^{T}A\mathbf{z}}{\mathbf{z}^{T}\mathbf{z}}\right)$
$\displaystyle=\frac{2\mathbf{x}_{t}}{\mathbf{x}^{T}\mathbf{x}}\left(1-\sum\limits_{v\sim
t}x_{v}\right)+\frac{2\mathbf{z}_{t}}{\mathbf{z}^{T}\mathbf{z}}\left(\mathrm{sgn}(\mathbf{z}_{t})+\sum\limits_{v\sim
t}\mathbf{z}_{v}\right)$
$\displaystyle\geq\frac{2\mathbf{x}_{t}}{\mathbf{x}^{T}\mathbf{x}}\left(1-\sum\limits_{v\sim
t}x_{v}\right)+\frac{2|\mathbf{z}_{t}|}{\mathbf{z}^{T}\mathbf{z}}\left(1-\left|\sum\limits_{v\sim
t}\mathbf{z}_{v}\right|\right),$

where $\mathrm{sgn}(\mathbf{z}_{t})$ equals $1$ if $\mathbf{z}_{t}>0$ and $-1$
otherwise.

$\left|\sum\limits_{v\sim t}\mathbf{z}_{v}\right|\leq\sum_{v\sim
t}|\mathbf{z}_{v}|\leq\sum_{\begin{subarray}{c}v\sim t\\\ v\not\in
B\end{subarray}}|\mathbf{z}_{v}|+\sum_{v\in B}|\mathbf{z}_{v}|.$

There are at most $2$ terms in the first sum, and so by Lemmas 3.6 and 3.9, we
have

$\left|\sum\limits_{v\sim
t}\mathbf{z}_{v}\right|=\mathcal{O}\left(\frac{1}{\sqrt{n}}\right).$

Similarly, we have

$\sum\limits_{v\sim
t}\mathbf{x}_{v}=\mathcal{O}\left(\frac{1}{\sqrt{n}}\right).$

This implies $1-\sum\limits_{v\sim t}\mathbf{x}_{v}>0$ and
$1-\left|\sum\limits_{v\sim t}\mathbf{z}_{v}\right|>0$ for $n$ large enough,
which implies that

$\frac{2\mathbf{x}_{t}}{\mathbf{x}^{T}\mathbf{x}}\left(1-\sum\limits_{v\sim
t}x_{v}\right)+\frac{2|\mathbf{z}_{t}|}{\mathbf{z}^{T}\mathbf{z}}\left(1-\left|\sum\limits_{v\sim
t}\mathbf{z}_{v}\right|\right)>0$

for $n$ large enough. Hence $S(G^{*})>S(G)$, contradicting the assumption that
$G$ is spread-extremal. ∎

We have finally achieved our goal for this section. Theorem 3.1 follows
immediately from the definition of $B$ and the fact that it is empty, as
implied by Lemma 3.11.

##  4 Determining Graph Structure

By Theorem 3.1, the vertex $w$ has degree $n-1$, or equivalently, $K_{1,n-1}$
is a subgraph of $G$. Since $G$ is $K_{2,3}$-free, the graph induced by the
neighborhood of $w$ has maximum degree at most $2$. Furthermore, this subgraph
cannot contain a cycle, otherwise $G$ would contain a wheel-graph and this is
a $K_{4}$-minor. Any graph of maximum degree at most $2$ that does not contain
a cycle is a disjoint union of paths. Therefore, we know that $G$ is given by
a $K_{1}\vee F$ where $F$ is a disjoint union of paths. Our next task is to
study $F$. To this end, we denote the number of edges in $F$ by $m$. Our main
theorem, Theorem 1.1 is proved if we can show that $m=\Omega(n)$. Before doing
this, we need a more accurate estimate for the eigenvector entries.

######  Lemma 4.1.

For any $u\not=w$, we have
$\mathbf{z}_{u}=\frac{1}{\lambda_{n}}+\frac{d_{u}-1}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)$.

###### Proof.

As we are only considering outerplanar graphs, we have $d_{u}\in\\{1,2,3\\}$
for all $u\neq w$. Hence

$\displaystyle\lambda_{n}\mathbf{z}_{u}$ $\displaystyle=\sum\limits_{y\sim
u}\mathbf{z}_{y}$ $\displaystyle=\mathbf{z}_{w}+\sum_{\begin{subarray}{c}y\sim
u\\\ y\not=w\end{subarray}}\mathbf{z}_{y}$
$\displaystyle=1-\Theta\left(\frac{1}{\sqrt{n}}\right)$

by Lemma 3.6 and our normalization.

Note that as
$\lambda_{n}\mathbf{z}_{u}=1+\mathbf{z}_{u_{1}}+\mathbf{z}_{u_{2}}>0$ and
$\lambda_{n}<0$, we must have $\mathbf{z}_{u}<0$. Next we repeat the argument
to improve our estimate,

$\displaystyle\lambda_{n}\mathbf{z}_{u}$
$\displaystyle=\mathbf{z}_{w}+\sum_{\begin{subarray}{c}y\sim u\\\
y\not=w\end{subarray}}\mathbf{z}_{y}$
$\displaystyle=1+(d_{u}-1)\left(\frac{1}{\lambda_{n}}+\Theta\left(\frac{1}{n}\right)\right).$
Now we apply our bounds on $\lambda_{n}$ in Lemma 3.3 to get
$\displaystyle\mathbf{z}_{u}$
$\displaystyle=\frac{1}{\lambda_{n}}+\frac{d_{u}-1}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right).$

∎

We can use equivalent reasoning to obtain a very similar approximation for the
$\mathbf{x}_{u}$ entries,

######  Lemma 4.2.

For any $u\not=w$, we have
$\mathbf{x}_{u}=\frac{1}{\lambda_{1}}+\frac{d_{u}-1}{\lambda_{1}^{2}}+\Theta(\frac{1}{n^{3/2}})$

###### Proof.

By the same logic as in the proof of Lemma 4.1, we have

$\displaystyle\lambda_{1}\mathbf{x}_{u}$ $\displaystyle=\sum\limits_{w\sim
u}\mathbf{x}_{w}$ $\displaystyle=\mathbf{x}_{w}+\sum_{\begin{subarray}{c}y\sim
u\\\ y\not=w\end{subarray}}\mathbf{x}_{y}$
$\displaystyle=1+\Theta\left(\frac{1}{\sqrt{n}}\right)\text{by Corollary
\ref{lmac3}}.$

So $\mathbf{x}_{u}=\frac{1}{\lambda_{1}}+\Theta\left(\frac{1}{n}\right)$. Next
we repeat the argument to improve our estimate,

$\displaystyle\lambda_{1}\mathbf{x}_{u}$
$\displaystyle=\mathbf{x}_{w}+\sum_{\begin{subarray}{c}y\sim u\\\
y\not=w\end{subarray}}\mathbf{x}_{y}$
$\displaystyle=1+(d_{u}-1)\left(\frac{1}{\lambda_{1}}+\Theta\left(\frac{1}{n}\right)\right).$

So
$\mathbf{x}_{u}=\frac{1}{\lambda_{1}}+\frac{d_{u}-1}{\lambda_{1}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)$
according to our bounds on $\lambda_{1}$ in Lemma 3.2. ∎

Using Lemma 4.1, we can now get tighter estimates on $\lambda_{n}$.

######  Lemma 4.3.

We have that
$\lambda_{n}=-\sqrt{n-1}+\frac{m}{n-1}+\Theta\left(\frac{m}{n^{3/2}}\right)$.

###### Proof.

We first define the vector

$\mathbf{y_{2}}=\begin{bmatrix}1\\\ -\frac{1}{\sqrt{n-1}}\\\
-\frac{1}{\sqrt{n-1}}\\\ \vdots\\\ -\frac{1}{\sqrt{n-1}}\end{bmatrix}$

where $\mathbf{y_{2}}$ has $n$ entries and $w$ corresponds to the 1 entry. As
$\lambda_{n}$ is the minimum Rayleigh quotient we have

$\displaystyle\lambda_{n}$
$\displaystyle\leq\frac{\mathbf{y_{2}}^{T}A\mathbf{y_{2}}}{\mathbf{y_{2}}^{T}\mathbf{y_{2}}}$
$\displaystyle=\frac{2\sum\limits_{i\sim
j}(\mathbf{y}_{2})_{i}(\mathbf{y}_{2})_{j}}{2}$
$\displaystyle=(n-1)\left(-\frac{1}{\sqrt{n-1}}\right)+m\left(\frac{1}{n-1}\right)$
$\displaystyle=-\sqrt{n-1}+\frac{m}{n-1}.$

In order to show the lower bound on $\lambda_{n}$, we need to realize that
$\lambda_{n}$ is the minimum possible Rayleigh quotient. So

$\lambda_{n}=\frac{\mathbf{z}^{T}A\mathbf{z}}{\mathbf{z}^{T}\mathbf{z}}=\frac{2\sum\limits_{i\sim
j}\mathbf{z}_{i}\mathbf{z}_{j}}{\mathbf{z}^{T}\mathbf{z}}=\frac{2\sum\limits_{w\sim
k}\mathbf{z}_{w}\mathbf{z}_{k}}{\mathbf{z}^{T}\mathbf{z}}+\frac{2\sum\limits_{{i\sim
j\,,\,i,j\neq w}}\mathbf{z}_{i}\mathbf{z}_{j}}{\mathbf{z}^{T}\mathbf{z}}.$

Note the first term is the Rayleigh quotient for the star subgraph centered at
the vertex $w$ of maximum degree. Hence it is bounded from below by
$-\sqrt{n-1}$. More specifically, we have

$\frac{2\sum\limits_{w\sim
k}\mathbf{z}_{w}\mathbf{z}_{k}}{\mathbf{z}^{T}\mathbf{z}}=\frac{\mathbf{z}^{T}A(K_{1,n-1})\mathbf{z}}{\mathbf{z}^{T}\mathbf{z}}\geq\lambda_{n}(A(K_{1,n-1}))=-\sqrt{n-1}.$

Applying Lemma 4.1 we have

$\displaystyle\lambda_{n}$
$\displaystyle\geq-\sqrt{n-1}+\frac{2\sum\limits_{\begin{subarray}{c}i\sim
j\\\
i,j\not=w\end{subarray}}\left(\frac{1}{\lambda_{n}}+\frac{d_{i}-1}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)\left(\frac{1}{\lambda_{n}}+\frac{d_{j}-1}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}{1+\left(\sum_{\ell\not=w}\frac{1}{\lambda_{n}}+\frac{d_{\ell}-1}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)^{2}}$

For $\ell\not=w$ we have $0\leq d_{\ell}-1\leq 2$. Note that for $n$ large
enough we have that
$\frac{1}{\lambda_{n}}+\frac{d_{u}-1}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)<0$,
and so we have a lower bound if we replace all $d_{\ell}-1$ terms in the
numerator by $2$ and in the denominator by $0$, and so we have

$\displaystyle\lambda_{n}$
$\displaystyle\geq-\sqrt{n-1}+\frac{2\sum\limits_{\begin{subarray}{c}i\sim
j\\\
i,j\not=w\end{subarray}}\left(\frac{1}{\lambda_{n}}+\frac{2}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)\left(\frac{1}{\lambda_{n}}+\frac{2}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}{1+\sum\limits_{\ell\not=w}\left(\frac{1}{\lambda_{n}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)^{2}}$
$\displaystyle=-\sqrt{n-1}+\frac{2m\left(\frac{1}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}{1+(n-1)\left(\frac{1}{\lambda_{n}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}.$

Since $-\sqrt{n-1}-2\leq\lambda_{n}\leq\sqrt{n-1}+2$, we have that
$\frac{1}{\lambda_{n}^{2}}=\frac{1}{n-1}+\Theta\left(\frac{1}{n^{3/2}}\right)$.
Hence we have

$\displaystyle\lambda_{n}$
$\displaystyle\geq-\sqrt{n-1}+\frac{2m\left(\frac{1}{n-1}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}{1+(n-1)\left(\frac{1}{n-1}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}$
$\displaystyle=-\sqrt{n-1}+\frac{\frac{2m}{n-1}+\Theta\left(\frac{m}{n^{3/2}}\right)}{2+\Theta\left(\frac{1}{n^{1/2}}\right)}$
$\displaystyle=-\sqrt{n-1}+\left(\frac{m}{n-1}+\Theta\left(\frac{m}{n^{3/2}}\right)\right)\left(1+\Theta\left(\frac{1}{\sqrt{n}}\right)\right),$

completing the proof.

∎

We claim a very similar result for $\lambda_{1}$.

######  Lemma 4.4.

$\lambda_{1}=\sqrt{n-1}+\frac{m}{n-1}+\Theta\left(\frac{m}{n^{3/2}}\right)$.

###### Proof.

First we prove the lower bound. Define the vector

$\mathbf{y_{3}}=\begin{bmatrix}1\\\ \frac{1}{\sqrt{n-1}}\\\
\frac{1}{\sqrt{n-1}}\\\ \vdots\\\ \frac{1}{\sqrt{n-1}}\end{bmatrix},$

where $w$ corresponds to the entry 1. As $\lambda_{1}$ is the maximum possible
Rayleigh quotient we have

$\displaystyle\lambda_{1}$
$\displaystyle\geq\frac{\mathbf{y}^{T}A\mathbf{y_{3}}}{\mathbf{y_{3}}^{T}\mathbf{y_{3}}}$
$\displaystyle=\frac{2\sum\limits_{i\sim
j}(\mathbf{y}_{3})_{i}(\mathbf{y}_{3})_{j}}{2}$
$\displaystyle=(n-1)\left(\frac{1}{\sqrt{n-1}}\right)+m\left(\frac{1}{n-1}\right)$
$\displaystyle=\sqrt{n-1}+\frac{m}{n-1}.$

For the upper bound, we use the fact that $\lambda_{1}$ is the maximum
possible Rayleigh quotient similarly to the previous lemma. So

$\displaystyle\lambda_{1}$
$\displaystyle=\frac{\mathbf{x}^{T}A\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}$
$\displaystyle=\frac{2\sum\limits_{i\sim
j}\mathbf{x}_{i}\mathbf{x}_{j}}{\mathbf{x}^{T}\mathbf{x}}$
$\displaystyle=\frac{2\sum\limits_{w\sim
k}\mathbf{x}_{w}\mathbf{x}_{k}}{\mathbf{x}^{T}\mathbf{x}}+\frac{2\sum{\begin{subarray}{c}i\sim
j\\\ i,j\neq
w\end{subarray}}\mathbf{x}_{i}\mathbf{x}_{j}}{\mathbf{x}^{T}\mathbf{x}}.$

As before, the first term is

$\frac{\mathbf{x}^{T}A(K_{1,n-1})\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}\leq\lambda_{1}(A(K_{1,n-1}))=\sqrt{n-1}.$

Applying Lemma 4.2 and using $0\leq d_{u}-1\leq 2$ for all $u\not=w$ we have

$\displaystyle\lambda_{1}$
$\displaystyle\leq\sqrt{n-1}+\frac{2\sum_{\begin{subarray}{c}i\sim j\\\
i,j\not=w\end{subarray}}\left(\frac{1}{\lambda_{1}}+\frac{d_{i}-1}{\lambda_{1}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)\left(\frac{1}{\lambda_{1}}+\frac{d_{j}-1}{\lambda_{1}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}{1+\left(\sum_{\ell\not=w}\frac{1}{\lambda_{1}}+\frac{d_{\ell}-1}{\lambda_{1}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)^{2}}$
$\displaystyle\leq\sqrt{n-1}+\frac{2\sum_{\begin{subarray}{c}i\sim j\\\
i,j\not=w\end{subarray}}\left(\frac{1}{\lambda_{1}}+\frac{2}{\lambda_{1}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)\left(\frac{1}{\lambda_{1}}+\frac{2}{\lambda_{1}^{2}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}{1+\sum_{\ell\not=w}\left(\frac{1}{\lambda_{1}}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)^{2}}$

Using $\sqrt{n-1}-2\leq\lambda_{1}\leq\sqrt{n-1}+2$, we have

$\displaystyle\lambda_{1}$
$\displaystyle\leq\sqrt{n-1}+\frac{2m\left(\frac{1}{n-1}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}{1+(n-1)\left(\frac{1}{n-1}+\Theta\left(\frac{1}{n^{3/2}}\right)\right)}$
$\displaystyle=\sqrt{n-1}+\frac{\frac{2m}{n-1}+\Theta\left(\frac{m}{n^{3/2}}\right)}{2+\Theta\left(\frac{1}{n^{1/2}}\right)}$
$\displaystyle=\sqrt{n-1}+\left(\frac{m}{n-1}+\Theta\left(\frac{m}{n^{3/2}}\right)\right)\left(1+\Theta\left(\frac{1}{\sqrt{n}}\right)\right),$

completing the proof.

∎

We are now in a position to prove our main theorem.

###### Proof of Theorem 1.1.

As before, let $G_{1}$ be the graph $K_{1}\vee P_{n-1}$ and let $A_{1}$ be its
adjacency matrix with the dominating vertex corresponding to the first row and
column. Since $G$ is spread-extremal we must have $S(G)\geq S(G_{1})$. We
lower bound $S(G_{1})$ using the vectors

$\mathbf{v}_{1}=\begin{bmatrix}-1+\sqrt{n}\\\ 1\\\ 1\\\ \vdots\\\
1\end{bmatrix}\quad\mbox{and}\quad\mathbf{v}_{2}=\begin{bmatrix}-1-\sqrt{n}\\\
1\\\ 1\\\ \vdots\\\ 1\end{bmatrix}.$

Using these vectors and the Rayleigh principle, we have that

$\displaystyle S(G_{1})$
$\displaystyle\geq\frac{\mathbf{v}_{1}^{T}A_{1}\mathbf{v}_{1}}{\mathbf{v}_{1}^{T}\mathbf{v}_{1}}-\frac{\mathbf{v}_{2}^{T}A_{1}\mathbf{v}_{2}}{\mathbf{v}_{2}^{T}\mathbf{v}_{2}}$
$\displaystyle=\frac{2(n-1)(\sqrt{n}-1)+(n-2)(1)}{2n-2\sqrt{n}}-\frac{2(n-1)(-\sqrt{n}-1)+(n-2)(1)}{2n+2\sqrt{n}}$
$\displaystyle=\frac{2(n-1)(\sqrt{n}-1)+(n-1)(1)}{2n-2\sqrt{n}}-\frac{1}{2n-2\sqrt{n}}$
$\displaystyle-\frac{2(n-1)(-\sqrt{n}-1)+(n-1)(1)}{2n+2\sqrt{n}}+\frac{1}{2n+2\sqrt{n}}$
$\displaystyle=\frac{n-1}{\sqrt{n}-1}+\frac{n-1}{\sqrt{n}+1}-\frac{\sqrt{n}}{n^{2}-n}\geq
2\sqrt{n}-\frac{1}{n}.$

Combining this with Lemmas 4.3 and 4.4, we have

$2\sqrt{n}-\frac{1}{n}\leq\lambda_{1}(G)-\lambda_{n}(G)=\left(\sqrt{n-1}+\frac{m}{n-1}+\Theta\left(\frac{m}{n^{3/2}}\right)\right)-\left(-\sqrt{n-1}+\frac{m}{n-1}+\Theta\left(\frac{m}{n^{3/2}}\right)\right).$

Therefore there exists a constant $C$ such that for $n$ large enough we have

$2\sqrt{n}-\frac{1}{n}\leq 2\sqrt{n-1}+\frac{C\cdot m}{n^{3/2}}.$

Since $\sqrt{n}-\sqrt{n-1}=\Omega(n^{-1/2})$, rearranging gives the final
result.

∎

## Acknowledgements

The authors would like to thank the Community of Mathematicians and
Statisticians Exploring Research (Co-MaStER) program at Villanova, through
which this research was started.

## References

  * [1] Tatjana M Aleksić and Miroslav Petrović.  Cacti whose spread is maximal.  Graphs and Combinatorics, 31(1):23–34, 2015.
  * [2] Enide Andrade, Geir Dahl, Laura Leal, and María Robbiano.  New bounds for the signless Laplacian spread.  Linear Algebra and its Applications, 566:98–120, 2019.
  * [3] Mustapha Aouchiche, Francis K Bell, Dragiša Cvetković, Pierre Hansen, Peter Rowlinson, Slobodan K Simić, and Dragan Stevanović.  Variable neighborhood search for extremal graphs. 16. some conjectures related to the largest eigenvalue of a graph.  European Journal of Operational Research, 191(3):661–676, 2008\.
  * [4] Iwo Biborski.  Note on the spread of real symmetric matrices with entries in fixed interval.  Linear Algebra and its Applications, 632:246–257, 2022.
  * [5] Barry N Boots and Gordon F Royle.  A conjecture on the maximum value of the principal eigenvalue of a planar graph.  Geographical analysis, 23(3):276–282, 1991.
  * [6] Jane Breen, Alex WN Riasanovsky, Michael Tait, and John Urschel.  Maximum spread of graphs and bipartite graphs.  arXiv preprint arXiv:2109.03129, 2021.
  * [7] Dasong Cao and Andrew Vince.  The spectral radius of a planar graph.  Linear algebra and its applications, 187:251–257, 1993.
  * [8] Dragiša Cvetković and Peter Rowlinson.  The largest eigenvalue of a graph: A survey.  Linear and multilinear algebra, 28(1-2):3–33, 1990.
  * [9] Emeric Deutsch.  On the spread of matrices and polynomials.  Linear Algebra and Its Applications, 22:49–55, 1978.
  * [10] Zdeněk Dvořák and Bojan Mohar.  Spectral radius of finite and infinite planar graphs and of graphs of bounded genus.  Journal of Combinatorial Theory, Series B, 100(6):729–739, 2010\.
  * [11] Mark N Ellingham and Xiaoya Zha.  The spectral radius of graphs on surfaces.  Journal of Combinatorial Theory, Series B, 78(1):45–56, 2000.
  * [12] Yi-Zheng Fan and Shaun Fallat.  Edge bipartiteness and signless Laplacian spread of graphs.  Applicable Analysis and Discrete Mathematics, pages 31–45, 2012\.
  * [13] Yi-Zheng Fan, Yi Wang, and Yu-Bin Gao.  Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread.  Linear Algebra and Its Applications, 429(2-3):577–588, 2008.
  * [14] Yi-Zheng Fan, Jing Xu, Yi Wang, and Dong Liang.  The Laplacian spread of a tree.  Discrete Mathematics and Theoretical Computer Science, 10(1):79–86, 2008.
  * [15] David A Gregory, Daniel Hershkowitz, and Stephen J Kirkland.  The spread of the spectrum of a graph.  Linear Algebra and its Applications, 332:23–35, 2001.
  * [16] Haiyan Guo and Bo Zhou.  On adjacency-distance spectral radius and spread of graphs.  Applied Mathematics and Computation, 369:124819, 2020.
  * [17] Yuan Hong and Jin-Long Shu.  Sharp lower bounds of the least eigenvalue of planar graphs.  Linear Algebra and Its Applications, 296(1-3):227–232, 1999.
  * [18] Charles R Johnson, Ravinder Kumar, and Henry Wolkowicz.  Lower bounds for the spread of a matrix.  Linear Algebra and Its Applications, 71:161–173, 1985.
  * [19] Xueliang Li, Jianbin Zhang, and Bo Zhou.  The spread of unicyclic graphs with given size of maximum matchings.  Journal of Mathematical Chemistry, 42(4):775–788, 2007.
  * [20] Huiqiu Lin and Bo Ning.  A complete solution to the Cvetković–Rowlinson conjecture.  Journal of Graph Theory, 97(3):441–450, 2021.
  * [21] Zhen Lin, Lianying Miao, and Shu-Guang Guo.  The ${A}_{\alpha}$-spread of a graph.  Linear Algebra and its Applications, 606:1–22, 2020.
  * [22] Bolian Liu and Liu Mu-Huo.  On the spread of the spectrum of a graph.  Discrete mathematics, 309(9):2727–2732, 2009.
  * [23] Muhuo Liu and Bolian Liu.  The signless Laplacian spread.  Linear algebra and its applications, 432(2-3):505–514, 2010.
  * [24] Leon Mirsky.  The spread of a matrix.  Mathematika, 3(2):127–130, 1956.
  * [25] Peter Nylen and Tin-Yau Tam.  On the spread of a Hermitian matrix and a conjecture of Thompson.  Linear and Multilinear Algebra, 37(1-3):3–11, 1994.
  * [26] Carla Silva Oliveira, Leonardo Silva De Lima, Nair Maria Maia de Abreu, and Steve Kirkland.  Bounds on the ${Q}$-spread of a graph.  Linear algebra and its applications, 432(9):2342–2351, 2010.
  * [27] Miroslav Petrović, Bojana Borovićanin, and Tatjana Aleksić.  Bicyclic graphs for which the least eigenvalue is minimum.  Linear algebra and its applications, 430(4):1328–1335, 2009.
  * [28] AJ RF and RJ Schwenk.  On the eigenvalues of a graph.  Selected Topics in Graph Theory, Academic Press, San Diego, pages 307–336, 1978.
  * [29] Alex W Neal Riasanovsky.  Two Problems in Extremal Combinatorics.  PhD thesis, Iowa State University, 2021.
  * [30] Peter Rowlinson.  On the index of certain outerplanar graphs.  Ars Combinatoria, 29:221–225, 1990.
  * [31] Zoran Stanić.  Inequalities for graph eigenvalues, volume 423.  Cambridge University Press, 2015.
  * [32] Dragan Stevanovic.  Spectral radius of graphs.  Academic Press, 2014.
  * [33] Michael Tait and Josh Tobin.  Three conjectures in extremal spectral graph theory.  Journal of Combinatorial Theory, Series B, 126:137–161, 2017.
  * [34] Robert C Thompson.  The eigenvalue spreads of a Hermitian matrix and its principal submatrices.  Linear and Multilinear Algebra, 32(3-4):327–333, 1992.
  * [35] John C Urschel.  Graphs, Principal Minors, and Eigenvalue Problems.  PhD thesis, MASSACHUSETTS INSTITUTE OF TECHNOLOGY, 2021.
  * [36] Bing Wang, Ming-qing Zhai, and Jin-long Shu.  On the spectral spread of bicyclic graphs with given girth.  Acta Mathematicae Applicatae Sinica, English Series, 29(3):517–528, 2013.
  * [37] Junliang Wu, Pingping Zhang, and Wenshi Liao.  Upper bounds for the spread of a matrix.  Linear algebra and its applications, 437(11):2813–2822, 2012.
  * [38] Yarong Wu and Jinlong Shu.  The spread of the unicyclic graphs.  European Journal of Combinatorics, 31(1):411–418, 2010.
  * [39] Lihua You, Liyong Ren, and Guanglong Yu.  Distance and distance signless Laplacian spread of connected graphs.  Discrete Applied Mathematics, 223:140–147, 2017.
  * [40] Zhifu You and Bolian Liu.  The Laplacian spread of graphs.  Czechoslovak mathematical journal, 62(1):155–168, 2012.
  * [41] Guanglong Yu, Hailiang Zhang, Huiqiu Lin, Yarong Wu, and Jinlong Shu.  Distance spectral spread of a graph.  Discrete Applied Mathematics, 160(16-17):2474–2478, 2012.
  * [42] Hong Yuan.  On the spectral radius and the genus of graphs.  Journal of Combinatorial Theory, Series B, 65(2):262–268, 1995\.
  * [43] Hong Yuan.  Upper bounds of the spectral radius of graphs in terms of genus.  Journal of Combinatorial Theory, Series B, 74(2):153–159, 1998\.