\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems
\usepackage[sort,noadjust]{cite}
\def\G{\overline{G}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
%%%1
\author{\firstname{Xiaofeng} \lastname{Gu}}
\address{Department of Computing and Mathematics\\
University of West Georgia\\
Carrollton, GA 30118, USA}
\email{xgu@westga.edu}
%%%2
\author{\firstname{Willem} \middlename{H.} \lastname{Haemers}}
\address{Department of Econometrics and Operations Research\\
Tilburg University\\
Tilburg, The Netherlands}
\email{haemers@uvt.nl}
%% Acknowledgements are not a footnote in
\thanks{The first author is partially supported by a grant from the Simons Foundation (522728, XG)}
%%%%% Sujet
\keywords{Toughness, Laplacian eigenvalue, perfect matching, factor, Hamilton cycle}
%% Mathematical classification (2010)
\subjclass{05C42, 05C50, 05C70, 05C45}
%%%%% Gestion
\DOI{10.5802/alco.197}
\datereceived{2021-04-08}
\daterevised{2021-08-24}
\dateaccepted{2021-08-25}
%%%%% Titre et résumé
\title
[Graph toughness from Laplacian eigenvalues]
{Graph toughness from Laplacian eigenvalues}
\begin{abstract}
The toughness $t(G)$ of a graph $G=(V,E)$ is defined as $t(G)=\min\left\{\frac{|S|}{c(G-S)}\right\}$,
in which the minimum is taken over all $S\subset V$ such that $G-S$ is disconnected,
where $c(G-S)$ denotes the number of components of $G-S$.
We present two tight lower bounds for $t(G)$ in terms of the Laplacian eigenvalues
and provide strong support for a conjecture for a better bound which, if true,
implies both bounds, and improves and generalizes known bounds by Alon, Brouwer, and the first author.
As applications, several new results on perfect matchings, factors and walks from Laplacian eigenvalues are obtained,
which leads to a conjecture about Hamiltonicity and Laplacian eigenvalues.
\end{abstract}
\datepublished{2022-02-28}
\begin{document}
\maketitle
\section{Introduction}
Throughout this paper, $G=(V,E)$ is a simple graph of order $n$ with nonempty vertex set $V$ and nonempty edge set $E$.
The minimum degree of $G$ is denoted by $\delta$.
For a subset $S\subset V$, the subgraph of $G$ induced by $V\backslash S$ is denoted by $G-S$, and
$c(G-S)$ is the number of components of $G-S$.
The \emph{toughness} $t(G)$ of a graph $G$ is defined as $t(G)=\min\{\frac{|S|}{c(G-S)}\}$,
where the minimum is taken over all proper subsets $S\subset V$ such that $c(G-S)>1$.
By convention, a complete graph has infinite toughness.
For any real number $r\ge 0$, $G$ is \emph{$r$-tough} if $t(G)\ge r$.
The graph toughness was introduced by Chv\'atal~\cite{Chva73} in 1973 and has been shown closely related to
many graph properties, including connectivity, Hamiltonicity, pancyclicity, factors, spanning trees, and others (see~\cite{BaBS06}).
Toughness of regular graphs from eigenvalues of adjacency matrices has been well studied by, among others,
\cite{Alon95, Brou95, CiWo14, CiGu16, Gu21, Gu21b}.
We use $\lambda_i :=\lambda_i(G)$ to denote the $i$-th largest eigenvalue of the adjacency matrix of $G$, and let
$\lambda =\max\{|\lambda_2|, |\lambda_n|\}$, that is, $\lambda$ is the second largest absolute eigenvalue.
It was Alon~\cite{Alon95} who first showed that for any connected $d$-regular graph $G$, $t(G)>\frac{1}{3}(\frac{d^2}{d\lambda+\lambda^2}-1)$,
through which, Alon was able to show that for every $t$ and $g$ there are $t$-tough graphs of girth strictly greater than $g$.
This strengthened a result of Bauer, Van den Heuvel and Schmeichel~\cite{BaVS95} who showed the same for $g=3$, and
thus disproved in a strong sense a conjecture of Chv\'atal~\cite{Chva73} that there exists a constant $t_0$ such that
every $t_0$-tough graph is pancyclic. Almost at the same time, Brouwer~\cite{Brou95} independently showed that
$t(G)>\frac{d}{\lambda}-2$ for any connected $d$-regular graph $G$. He also conjectured that $t(G) \ge\frac{d}{\lambda}-1$
in~\cite{Brou95, Brou96}. Recently Brouwer's conjecture has been confirmed by the first author~\cite{Gu21b}.
In this paper, we consider arbitrary graphs and look for lower bounds on $t(G)$ in terms of the eigenvalues of the Laplacian matrix.
%\medskip
The \emph{Laplacian matrix} $L$ (also called \emph{combinatorial Laplacian} or \emph{discrete Laplacian}) of a graph $G$,
is defined by $L=D-A$, where $D$ is the diagonal degree matrix and $A$ is the adjacency matrix of $G$.
Let $\mu_i:=\mu_i(G)$ denote the $i$-th smallest eigenvalue of the Laplacian matrix of $G$.
Then $L$ is positive semi-definite and $\mu_1(G)=0$.
The second smallest Laplacian eigenvalue $\mu_2(G)$, is known as the \emph{algebraic connectivity} of $G$.
We have $\mu_2(G)=0$ if and only if $G$ is disconnected.
Moreover, if $\kappa$ is the vertex connectivity, then
\begin{equation}
\label{algcon}
\mu_2\leq\kappa\leq\delta.
\end{equation}
The complement $\G$ of $G$ has eigenvalues $\mu_1(\G)=0$ and $\mu_i(\G) = n-\mu_{n+2-i}(G)$ for $i=2,\ldots,n$.
Therefore $\mu_n(G)\leq n$ and $\mu_n(G)=n$ if and only if $\G$ is disconnected.
If $G$ is regular of degree $d$, then $L=dI-A$ and therefore $\mu_i=d-\lambda_i$ for $i=1,\ldots,n$.
For these and other properties of the Laplacian matrix and its eigenvalues, we refer to~\cite{BrHa12}.
%\bigskip
The paper is organized as follows. Our main results will be in the next section.
The tools and the proofs will be presented in Sections~\ref{tools} and~\ref{proofs}.
In Section~\ref{appls}, we will show applications on perfect matchings, factors and walks.
Since toughness is closely related to cycle structures, we include a conjecture on Hamilton cycles
from Laplacian eigenvalues.
\section{Results}
Recently, the second author made the following conjecture~\cite{Haem20}.
\begin{conjecture}[Haemers]
\label{Haemconj}
\begin{equation}
\label{bd0}
t(G)\ge \frac{\mu_2}{\mu_n -\delta}.
\end{equation}
\end{conjecture}
For $d$-regular graphs, this conjecture implies that $t(G)\ge \frac{d-\lambda_2}{ -\lambda_n}$, which is stronger than Brouwer's conjecture.
The conjecture is supported by the following theorem and proposition.
The proofs will be given in Section~\ref{proofs}.
\begin{theorem}\label{mutou}
\begin{equation}
\label{bd1}
t(G)\ge \frac{\mu_n\mu_2}{n(\mu_n-\delta)},
\end{equation}
and
\begin{equation}
\label{bd2}
t(G)\ge \frac{\mu_2}{\mu_n - \mu_2}.
\end{equation}
\end{theorem}
\begin{prop}\label{conjprop}
Let $S\subset V$ be such that $t(G)=|S|/c(G-S)$.
Then Conjecture~\ref{Haemconj} is true in each of the following cases.
\begin{enumerate}[label=(\roman*)]
\item\label{prop2.3_i}
The complement of $G$ is disconnected,
\item\label{prop2.3_ii}
All connected components of $G-S$ are singletons \textup{(}\ie $n-|S|=c(G-S)$\textup{)},
\item\label{prop2.3_iii}
The union of some components of $G-S$ has order $\frac{1}{2}(n-|S|)$,
\item\label{prop2.3_iv}
$c(G-S)=2$.
\end{enumerate}
\end{prop}
Since $\mu_n\leq n$ and $\delta\geq\mu_2$, the conjectured bound~\eqref{bd0} implies~\eqref{bd1} and~\eqref{bd2}.
Note that~\eqref{bd0} and~\eqref{bd1} coincide if $\mu_n=n$, that is, if the complement of $G$ is disconnected.
Therefore~\ref{prop2.3_i} of Proposition~\ref{conjprop} follows from~\eqref{bd1}.
The three bounds coincide and are tight in case $G$ is the complete multipartite graph $K_{n_1,\ldots,n_m}$ ($1 \frac{c}{2}$
and $|Y| = \sum_{i > (c+1)/2} |H_i| \ge 2\cdot \frac{c-1}{2}=c-1\ge c/2$. Switch $X$ and $Y$ whenever needed to get $|Y|\ge |X|$.
It follows that $c\le 2|X|$.
Thus, by~\eqref{ssiz},
\begin{equation*}
t(G) = \frac{|S|}{c}\ge
\frac{2\mu_2}{\mu_n -\mu_2}\cdot \frac{|X|}{c} \ge \frac{\mu_2}{\mu_n -\mu_2}.\qedhere
\end{equation*}
\end{proof}
The last two proofs of this section deal with~\ref{prop2.3_iii} and~\ref{prop2.3_iv} of Proposition~\ref{conjprop}.
\begin{proof}~\ref{prop2.3_iii}:
In this case $V\backslash S$ can be partitioned into two sets $X$ and $Y$ both having cardinality $\frac{1}{2}(n-|S|)$,
such that there are no edges between $X$ and $Y$.
We apply~\eqref{ssiz} and find $|S|\geq \frac{\mu_2}{\mu_n-\mu_2}(n-|S|)$, which implies
$|S|\geq n\mu_2/\mu_n$.
As before, Theorem~\ref{indupp} gives $c\leq n(\mu_n-\delta)/\mu_n$ and hence
\[
t(G)= \frac{|S|}{c} \geq n\frac{\mu_2}{\mu_n} \cdot \frac{\mu_n}{n(\mu_n-\delta)}=\frac{\mu_2}{\mu_n-\delta}.\qedhere
\]
\end{proof}
\begin{proof}~\ref{prop2.3_iv}:
It is known (see~\cite[Section 3.9]{BrHa12}) that $\mu_n\geq d_{\max}+1$, when $d_{\max}$ is the maximum degree of $G$.
If $G$ is not regular, then $d_{\max}-\delta\geq 1$, and hence $\mu_n-\delta\geq 2$.
If $G$ is regular of degree $d=\delta$, then the adjacency matrix has smallest eigenvalue $\lambda_n=d-\mu_n$.
If $G$ is regular with $\lambda_n > -2$ then $G$ is the complete graph $K_n$ or an odd cycle $C_n$; see~\cite[Theorem 2.5]{DoCv}.
We have $t(K_n)=\infty$ and $t(C_n)=2$ if $n\geq 4$.
If $n$ is odd, $\mu_2(C_n) = 2 - 2\cos(\pi/n)$ and $\mu_n(C_n) = 2 + 2\cos(2\pi/n)$, so~\eqref{bd0}
gives $2\geq (1-\cos(\pi/n))/\cos(2\pi/n)$ which is clearly true for all odd $n\geq 5$.
Thus we can assume that $\lambda_n\leq -2$ and hence $\mu_n-d=\mu_n-\delta \geq 2$.
By~\eqref{ssize}, it implies that
\[
t(G)=\frac{|S|}{c} = \frac{|S|}{2} \geq \frac{\mu_2}{2} \geq \frac{\mu_2}{\mu_n-\delta}.\qedhere
\]
\end{proof}
\section{Applications}\label{appls}
It was shown in~\cite{LiCh10} that if $\frac{\mu_2}{\mu_n} \ge \frac{2}{3}$, then $G$ is $2$-tough.
Now we can generalize it by rewriting~\eqref{bd2} of Theorem~\ref{mutou} as below.
\begin{theorem}
\label{toucor}
If $\displaystyle \frac{\mu_2}{\mu_n} \ge \frac{r}{r+1}$, then $G$ is $r$-tough.
\end{theorem}
Since many graph parameters and properties are related to toughness,
we have various applications, including but not limited to the results in this section.
We refer readers to the survey paper~\cite{BaBS06} for more toughness related results.
Spectral conditions for matchings and $k$-factors of regular graphs have been attracting many researchers
\cite{BrHa05, Cioa05, KrSu06, CiGr07, CiGH09, OCi10, Lu10, Lu12, Gu14}, among others.
However, not as much has been discovered for general graphs that are not necessarily regular.
Brouwer and the second author~\cite{BrHa05} showed that if $n$ is even and $2\mu_2 \ge \mu_n$, then $G$ has a perfect matching.
This result has been recently generalized to matching numbers in~\cite{GuLiu20}.
We will have other generalizations by using graph toughness.
A graph $G$ is called \emph{elementary} if it contains a perfect matching and if the edges which occur in at least one perfect matching in $G$
induce a connected subgraph. A substantial study of elementary graphs has been given in~\cite{LoPl86}.
It is proved in~\cite{BBKMSS07} that every 1-tough graph with an even number of vertices is elementary.
Thus Theorem~\ref{toucor} implies the following result.
\begin{theorem}
If $n$ is even and $2\mu_2 \ge \mu_n$, then $G$ is elementary.
\end{theorem}
Let $G$ be an $n$-vertex graph with a perfect matching, and $m$ be a positive integer with $m m$, then $G$ is $m$-extendable.
\begin{theorem}
Suppose $n$ is even, and let $m$ be a positive integer such that $m \frac{m}{m+1},
\]
then $G$ is $m$-extendable.
\end{theorem}
In~\cite{EJKS85}, it is proved that every $k$-tough graph has a $k$-factor if $k|V(G)|$ is even and $|V(G)|\ge k+1$, confirming a conjecture
of Chv\'atal~\cite{Chva73}. The result was extended to non-regular factors by Katerinis~\cite{Kate90}.
Let $a\le b$ be positive integers. An \emph{$[a,b]$-factor} of a graph $G$ is a spanning subgraph $H$ such that $a\le d_H(v)\le b$ for each vertex.
Katerinis~\cite{Kate90} showed that for a graph $G$ on $n$ vertices such that $a** s/2$,
then $G$ is $(1,s)$-factor-critical.
By Theorem~\ref{toucor}, we have the following result.
\begin{theorem}
Suppose $2\le s \frac{s}{s+2},
\]
then $G$ is $(1,s)$-factor-critical.
\end{theorem}
For $k=2, 3$ or even a general $k$, similar results on $(k,s)$-factor-critical graphs from toughness can be found in the survey~\cite{BaBS06}.
Thus Theorem~\ref{toucor} implies Laplacian eigenvalue conditions for $(k,s)$-factor-critical graphs with various values of $k$ and $s$,
which will be omitted here.
%\medskip
Spectral conditions for the existence of a spanning tree with degree bounded above by a fixed number $k$ in a regular graph
have been obtained in~\cite{CiWo14, CiGu16}.
When $k=2$, such a spanning tree is exactly a Hamilton path, and a sufficient condition has been given by, among others,
Butler and Chung~\cite{BuCh10}, who borrowed the idea from~\cite{KrSu03} (both~\cite{KrSu03, BuCh10} studied a stronger
structure, \ie Hamilton cycle). The case of $k\ge 3$ for general graphs was asked in~\cite{CiGu16} and has been solved in~\cite{GuLiu20}.
A theorem of Win~\cite{Win89} implies that if $t(G)\ge \frac{1}{k-2}$ for $k\ge 3$, then $G$ has a spanning tree with maximum degree
at most $k$. Thus, Theorem~\ref{toucor} implies the following result of~\cite{GuLiu20}.
\begin{theorem}[\cite{GuLiu20}]
\label{k-tre}
Let $k\ge 3$ be an integer.
If
\[
\frac{\mu_2}{\mu_n} \ge \frac{1}{k-1},
\]
then $G$ has a spanning tree with maximum degree at most $k$.
\end{theorem}
Generalizing the idea of a Hamilton cycle, a \emph{$k$-walk} in a graph $G$ is a closed spanning walk of $G$ that visits every vertex of $G$
at most $k$ times. In particular, a Hamilton cycle is a 1-walk. Jackson and Wormald~\cite{JaWo90} observed that the existence of a spanning tree
with maximum degree at most $k$ actually implies the existence of a $k$-walk. Thus Theorem~\ref{k-tre} implies the existence of a
$k$-walk for $k\ge 3$. For $k=2$, Ellingham and Zha~\cite{ElZh00} showed that every 4-tough graph has a 2-walk.
By Theorem~\ref{toucor}, we have the following Laplacian eigenvalue condition for the existence of a $2$-walk.
\begin{theorem}
\label{2-wal}
If $\frac{\mu_2}{\mu_n} \ge \frac{4}{5}$, then $G$ has a $2$-walk.
\end{theorem}
%\smallskip
\begin{rema}
In this section we presented applications of~\eqref{bd2} on perfect matchings, factors and walks.
The bound~\eqref{bd1} has similar applications and if Conjecture~\ref{Haemconj} is true,
then all results in this section can be improved in a similar manner.
\end{rema}
Similar to Theorems~\ref{k-tre} and~\ref{2-wal}, the first author made the following conjecture for Hamilton cycles, but never
published elsewhere before.
\begin{conjecture}[Gu]
\label{conjham}
There exists a positive constant $C<1$ such that if $\mu_2/ \mu_n \ge C$ and $n\ge 3$,
then $G$ contains a Hamilton cycle.
\end{conjecture}
\begin{rema}
Notice that $K_{s, s+1}$ contains no Hamilton cycle, but $\mu_2 =s$ and $\mu_n = 2s+1$, which implies that
$\mu_2/ \mu_n$ can be arbitrarily close to $1/2$ if $s$ is sufficiently large. Thus the smallest possible $C$ is at least $1/2$.
\end{rema}
Chv\'atal~\cite{Chva73} conjectured that there exists a constant $t_0$ such that every $t_0$-tough graph contains a Hamilton cycle.
By~\eqref{bd2} of Theorem~\ref{mutou}, clearly Chv\'atal's conjecture implies Conjecture~\ref{conjham}.
Krivelevich and Sudakov~\cite{KrSu03} conjectured that for a $d$-regular graph $G$, there exists a constant $K$ such that
$d/\lambda > K$ and $n$ is large enough, then $G$ contains a Hamilton cycle.
It is not hard to see that Conjecture~\ref{conjham} implies the conjecture of Krivelevich and Sudakov.
All three conjectures remain open.
The results in this section as well as~\cite{Haem95, BrHa05, YoLi12, GuLiu20} indicate that many graph properties are related to
the \emph{Laplacian eigenratio $\mu_2/\mu_n$}.
This eigenratio also has application aspects, and is highly related to the synchronization in small-world systems~\cite{BaPe02}.
It plays a similar role as %the
spectral gap, but may give a bit more information about the structure of the graph.
It is clear that $\mu_2/\mu_n=1$ if and only if the graph is complete.
For a non-complete graph we have that $\mu_n\geq 1+d_{\max}$ (see Section~\ref{proofs}), and since $\mu_2\leq\kappa$
the Laplacian eigenratio of a non-complete graph is bounded above by $\kappa/(1+d_{\max})$ (see~\cite{G} for more about this inequality).
But for many $d$-regular graphs with vertex connectivity $d$ (i.e. $d_{\max}=\kappa$) the ratio is close to $1$.
For example the Paley graph of order $n$ satisfies $\mu_2/\mu_n=(\sqrt{n}-1)/(\sqrt{n}+1)$ (see~\cite{BrHa12}).
We feel that the Laplacian eigenratio is interesting for future research.
\longthanks{The authors would like to thank the referees for carefully reading our manuscript and for their comments.}
\nocite{*}
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Gu_582}
\end{document}
**