\documentstyle[a4,12pt]{article}
\title{Spectrum and connectivity of graphs}
\author{A.E. Brouwer}
\date{(talk at SMC50, 960206)}
\begin{document}
\maketitle

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\Remark}{ \noindent{\bf Remark:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}

\medskip
{\bf Problem}
Let $\Gamma$ be a nice graph. Show that $\Gamma$ is very connected.

\medskip
In this talk I would like to give three examples of results about the
connectivity of a graph that follow by considering its spectrum.
There are lots of open problems.

\medskip
Three measures of connectivity play a r\^{o}le here:\\
(i) is $\Gamma$ connected or not?\\
(ii) $\kappa(\Gamma)$, the vertex connectivity of $\Gamma$,
that is, the minimum number of vertices that one has to remove
in order to disconnect $\Gamma$.\\
(iii) $t(\Gamma)$, the toughness of $\Gamma$, is defined as
$$\min_S ~ {|S| \over c(\Gamma \setminus S)}$$
where $S$ runs over all sets of vertices such that $\Gamma \setminus S$
is disconnected, and $c(\Gamma \setminus S)$ is its number of connected
components.

\medskip
The graph $K_0$ without vertices is not connected (we have
$c(K_0) = 0$, while $c(\Gamma) = 1$ for connected graphs $\Gamma$)
but I shall leave undefined whether it is disconnected, and hence
do not define $\kappa(\Gamma)$ and $t(\Gamma)$ when $\Gamma$ is complete.

\medskip
For example, for the Petersen graph we find $\kappa(\Gamma) = 3$ and
$t(\Gamma) = {4 \over 3}$. More generally, we clearly have
$\kappa(\Gamma) \le k(\Gamma)$ if $k(\Gamma)$ is the (minimal) valency
of $\Gamma$. One may also ask about the size of `nonlocal' cut sets.
For example,

(1) (`unimodality') Is it true that if $S$ is a cut set of $\Gamma$,
with separation $\Gamma\setminus S = A + B$, then
$\min(|\Gamma(S) \cap A|,~|\Gamma(S) \cap B|) \le |S|$?
(Here $\Gamma(S)$ denotes the set of all vertices adjacent to
some vertex of $S$.)

[Jack Koolen remarks that some condition is necessary:
for each $i$, $0 \le i \le 17$,
the Biggs-Smith graph has a cut set $S$ of size 17 such that
$|\Gamma(S) \cap A| = 17+i$, $|\Gamma(S) \cap B| = 34-i$.]

(2) Show that $|S|$ is substantially larger than $k$ when $S$ is nonlocal
(say, given a lower bound on the size or the minimum valency of each
component of $\Gamma\setminus S$).

\section{The connectivity of strongly regular graphs}
\begin{Theorem}
{\rm (Brouwer \& Mesner \cite{BM})}
Let $\Gamma$ be strongly regular of valency $k$. Then $\kappa(\Gamma) = k$,
and the only cut sets of size $k$ are the point neighbourhoods.
\end{Theorem}

\medskip

The weaker result that for strongly regular graphs
the edge-connectivity is at least the valency, was shown ten years
earlier by Ples\'nik \cite{Pl}.

\medskip

Open problems are for example:

(3) Prove the above result for distance-regular graphs.

(4) Let $\Gamma$ be strongly regular with parameters $(v,k,\lambda,\mu)$,
and let $S$ be a disconnecting set not containing any point neighbourhood
$\Gamma(x)$. Show that $|S| \ge 2k-2-\lambda$.

(5) Let $S$ be a disconnecting set such that $|S \cap \Gamma(x)| \le \alpha k$
for some fixed $\alpha$, $0 < \alpha < 1$, and all vertices $x$ of $\Gamma$.
Prove a superlinear (in $k$) lower bound for $|S|$.

Godsil \cite{G} conjectures that for any graph that is a colour class
in an association scheme, the edge-connectivity equals the degree,
and I conjecture the same for the vertex-connectivity.

Partial results:
Fiedler \cite{F} shows that the vertex-connectivity of a graph is at least
$k - \theta_2$, where $k$ is the degree and $\theta_2$
the second largest eigenvalue.
Lov\'asz \cite{L}, Problem 12.14, proves that the edge-connectivity
of a vertex-transitive graph is at least its degree.
An old result says that the vertex-connectivity of a vertex-transitive
graph is at least $2(k+1)/3$, where the extreme case is the clique
extension of a circuit.

\medskip
Brouwer \& Mulder \cite{BMu} showed
$\kappa(\Gamma) = k$ for graphs with the property that any two distinct
vertices have either 0 or 2 common neighbours. This settles (3) in the
case $\lambda \in \{0,2\}$, $\mu = 2$.

\section{The connectedness of generic pieces of generalized polygons}
\begin{Theorem}
{\rm (Brouwer \cite{B})}
Let $\Gamma$ be the point graph or the flag graph of a finite generalized
polygon. Then the subgraph $\Delta$ of $\Gamma$ induced on the set
of all vertices far away from (`in general position w.r.t.') a point
or flag is connected, except in the cases $G_2(2)$, ${}^2F_4(2)$ and
(for the flag graph) $B_2(2)$, $G_2(3)$.
A similar result holds more generally for the complement of a geometric
hyperplane.
\end{Theorem}

\medskip
Open problems:

(6) Generalize this to near polygons.

(7) Generalize this to distance-regular graphs.

\medskip
It is very easy to see that in a strongly regular graph
the subgraph on the vertices far away from a point is connected
(except when the graph is complete multipartite).

\section{The toughness of a regular graph}
\begin{Theorem}
{\rm (Alon-Brouwer, cf. \cite{A,Bt})}
Let $\Gamma$ be a graph on $v$ vertices, regular of valency $k$,
and with eigenvalues $k = \theta_1 \ge \theta_2 \ge ... \ge \theta_v$.
Put $$\lambda := \max_{2 \le j \le v} | \theta_j | .$$
Then $$t(\Gamma) > {k \over \lambda} - 2 .$$
\end{Theorem}

\medskip
Open problems:

(8) Prove $t(\Gamma) \ge {k \over \lambda} - 1$. (I conjecture that this
is the right bound.)

(9) Prove $t(\Gamma) = {k \over \lambda}$ in many cases.

\medskip
\noindent
{\bf Examples}
We have bipartite graphs of small toughness, so the `$-1$' would be
best possible. The Delsarte-Hoffman bound for cocliques $C$ in strongly
regular graphs states
$$|C| \le {v \over {1 + k/(-\theta_v)}} .$$
If equality holds, and $\lambda = - \theta_v$ (as is often the case),
then we find with $S = \Gamma\setminus C$: $t(\Gamma) \le
(v - |C|)/|C| = {k \over \lambda}$.

\section{Tools}
How are these results proved? Essentially, only interlacing (cf. Haemers
\cite{H}) is used.
Interlacing comes in two main forms:

(i) If $\Delta$ is an induced subgraph of a graph $\Gamma$, then the
eigenvalues $\eta_j$ $(1 \le j \le u)$ of $\Delta$ interlace the
eigenvalues $\theta_i$ $(1 \le i \le v)$ of $\Gamma$:
we have $\theta_i \ge \eta_i$ $(1 \le i \le u)$ and
$\eta_{u-j} \ge \theta_{v-j}$ $(0 \le j \le u-1)$.

(ii) Given a partition $\Pi$ of the index set of a symmetric matrix $A$,
let $B = (B_{R,S})_{R,S \in \Pi}$ be the matrix of average row sums
of the corresponding submatrices of $A$. Then the eigenvalues of $B$
interlace those of $A$.

\medskip
\noindent
{\bf Examples}

\begin{Lemma}
The average valency of a graph is not more than its largest eigenvalue.
\end{Lemma}
\Proof
Use a partition with 1 part. \qed

\begin{Lemma}
Let $\Gamma$ be regular of valency $k$ on $v$ vertices, and let the graph
induced on the $r$-set $R$ have average valency $k_R$. Then
$$\theta_2 \ge (v k_R - r k)/(v-r) \ge \theta_v ,$$ (and hence
$$r \le v(k_R - \theta_v)/(k - \theta_v).$$
For $k_R = 0$ we find the Delsarte-Hoffman bound).
\end{Lemma}
\Proof
Use a partition with 2 parts. \qed

\begin{Lemma}
Let $\Gamma$ and $R$ be as before. Put
$\lambda =  \max (|\theta_2|, |\theta_v|)$. Then
$$\sum_x (|\Gamma(x) \cap R| - {r k \over v})^2 \le \lambda^2 r(v-r)/v .$$
\end{Lemma}
\Proof
Use a partition with 2 parts, and apply to $A^2$, the square of
the adjacency matrix of $\Gamma$. \qed

\section{Proofs of the results in sections 1,2,3}
Let $\Gamma$ have eigenvalues $k = \theta_1 \gg \theta_2 \ge ...$.
If $\Delta$ is a disconnected subgraph, then its spectrum is the union
of the spectra of its components. Each component has a largest
eigenvalue at least as large as its average degree, and by interlacing
it follows that all components except perhaps one have average degree
at most $\theta_2$, but this is much too small
(except when $\Gamma$ is very small).

This proves the results of Sections 1 and 2.
For those of Section 3, use the above three Lemmata and compute.

\begin{thebibliography}{}

\bibitem[1]{A} Noga Alon,
{\it Tough Ramsey graphs without short cycles\/},
preprint, 1993.

\bibitem[2]{B} A.E. Brouwer,
{\it The complement of a geometric hyperplane in a generalized polygon
is usually connected\/},
pp. 53-57 in: Finite geometry and combinatorics - Proc. Deinze 1992,
F. De Clerck et al. (eds), London Math. Soc. Lect. Note Ser. 191,
Cambridge Univ. Press, 1993.

\bibitem[3]{Bt} A.E. Brouwer,
{\it Toughness and spectrum of a graph\/},
preprint, 1993.

\bibitem[4]{BM} A.E. Brouwer \& D.M. Mesner,
{\it The connectivity of strongly regular graphs\/},
Europ. J. Combin. {\bf 6} (1985) 215-216.

\bibitem[5]{BMu} A.E. Brouwer \& H.M. Mulder,
{\it The vertex connectivity of a $\{0,2\}$-graph equals its valency\/},
preprint, 1994.

\bibitem[6]{F} M. Fiedler,
{\it Algebraic connectivity of graphs\/},
Czech. Math. J. {\bf 23} (1973) 298-305.

\bibitem[7]{G} C.D. Godsil,
{\it Equiarboreal graphs\/},
Combinatorica {\bf 1} (1981) 163-167.

\bibitem[8]{H} W.H. Haemers,
{\it Eigenvalue techniques in design and graph theory\/},
Reidel, Dordrecht, 1980.

\bibitem[9]{L} L. Lov\'asz,
{\it Combinatorial problems and exercises\/},
North Holland, Amsterdam, 1979.

\bibitem[10]{Pl} J. Ples\'nik,
{\it Critical graphs of given diameter\/},
Acta Fac. Rerum Natur. Univ. Comenianae, Math. {\bf 30} (1975) 71-93.

\end{thebibliography}

\end{document}
