$H_{n,k,\delta}$, this implies
$\lambda(H_{n,k,\delta})>\lambda(L_{n,k,\delta})$; see, e.g., [111, Theorem
2.12]. With this observation in mind, Theorem 2.35 implies the following
corollary, which is an extension on Theorem 2.12.

######  Corollary 2.36.

Let $k\geq 0$, $\delta\geq k+2$ and $n$ be sufficiently large. If $G$ is an
$n$-vertex graph with minimum degree $\delta(G)\geq\delta$ and

$\lambda(G)\geq\lambda(H_{n,k,\delta}),$

then $G$ is $k$-edge-Hamiltonian unless $G=H_{n,k,\delta}$.

Moreover, Li and Peng [116] also presented the following sufficient conditions
on the signless Laplacian spectral radius for $k$-Hamiltonian graphs with
large minimum degree.

######  Theorem 2.37 (Li–Peng [116]).

Let $k\geq 0,\delta\geq k+2$ and $n$ be sufficiently large. If $G$ is an
$n$-vertex graph with minimum degree $\delta(G)\geq\delta$ and

$q(G)\geq 2(n-\delta+k-1),$

then $G$ is $k$-edge-Hamiltonian unless $G\in\mathcal{H}_{n,k,\delta}^{(1)}$
or $G\in\mathcal{L}_{n,k,\delta}^{(1)}$.

As a consequence, we get the following corollary.

######  Corollary 2.38.

Let $k\geq 0$, $\delta\geq k+2$ and $n$ be sufficiently large. If $G$ is an
$n$-vertex graph with minimum degree $\delta(G)\geq\delta$ and

$q(G)\geq q(H_{n,k,\delta}),$

then $G$ is $k$-edge-Hamiltonian unless $G=H_{n,k,\delta}$.

##  3 Spectral problem for path coverability

###  3.1 Problem for Hamilton path

Let $G$ be a simple graph. A path is called a Hamilton path if it contains all
vertices of $G$. When $G$ contains a Hamiltonian path, we usually say that $G$
is traceable. It is well-known that $G$ contains a Hamilton path if and only
if $G\vee K_{1}$ contains a Hamilton cycle. With the help of this relation,
almost all results involving Hamilton cycle can imply the corresponding
results for Hamilton path. Thus, almost all problems involving Hamilton path
can be reduced to the problem of Hamilton cycle in this way. For any non-
negative integer $q$, a graph $G$ with $n\geq 3$ vertices is called
$q$-traceable if any removal of at most $q$ vertices of $G$ results in a
traceable graph.

######  Theorem 3.1 (Dirac [53], Ore [155]).

If $G$ is a graph on $n\geq 3$ vertices with minimum degree
$\delta(G)\geq\frac{n-1}{2}$, then $G$ has a Hamilton path.

######  Theorem 3.2 (Bondy–Chvátal [23]).

A graph $G$ is traceable if and only if the closure graph
$\mathrm{cl}_{n-1}(G)$ is traceable. In particular, if $d(u)+d(v)\geq n-1$ for
all non-edges $\\{u,v\\}$, then $\mathrm{cl}_{n-1}(G)=K_{n}$ and $G$ is
traceable.

######  Lemma 3.3 (Chvátal [40]).

Let $G$ be an $n$-vertex graph with degree sequence $d_{1}\leq
d_{2}\leq\cdots\leq d_{n}$. If $G$ has no Hamilton path, then there exists
$i<\frac{n+1}{2}$ such that $d_{i}\leq i-1$ and $d_{n-i+1}\leq n-i-1$.

######  Theorem 3.4 (Ore [155], Bondy [22]).

Let $G$ be a graph on $n\geq 3$ vertices. If

$e(G)\geq{n-1\choose 2},$

then $G$ has a Hamilton path unless $G=K_{1}\cup K_{n-1}$ or $n=4$ and
$G=K_{1,3}$.

######  Theorem 3.5 (Fiedler–Nikiforov [73]).

Let $G$ be a graph on $n$ vertices and

$\lambda(G)\geq n-2,$

then either $G$ has a Hamilton path or $G=K_{n-1}\cup K_{1}$.

The proof is short and similar with that in Theorem 2.6.

###### Proof.

The well-known Stanley inequality asserts that
$\lambda(G)\leq-1/2+\sqrt{2e(G)+1/4}$, which together with $\lambda(G)\geq
n-2$, implies that $e(G)\geq{n-1\choose 2}$. Hence, for $n\neq 4$, the desired
result follows from Theorem 3.4. For $n=4$, if $G$ is the another possible
exception $K_{1,3}$, we can calculate that $\lambda(K_{1,3})=\sqrt{3}$, which
contradicts the condition $\lambda(G)\geq n-2$. This completes the proof. ∎

In 2013, Yu and Fan [177] provided the condition for the existence of
Hamiltonian paths in terms of the signless Laplacian spectral radius of the
graph.

######  Theorem 3.6 (Yu–Fan [177]).

Let $G$ be a graph on $n$ vertices and

$q(G)\geq 2(n-2),$

then $G$ has a Hamilton path or $G=K_{n-1}\cup K_{1}$, or $n=4$ and
$G=K_{1,3}$.

###### Proof.

An important inequality in [68] states that $q(G)\leq\frac{2e(G)}{n-1}+n-2$,
which together with $q(G)\geq 2(n-2)$ yields that $e(G)\geq{n-1\choose 2}$.
Hence, for $n\neq 4$, the desired result follows from Theorem 3.4. For $n=4$,
when $G$ is the another possible exception $K_{1,3}$, we can calculate that
$q(K_{1,3})=4$. This completes the proof. ∎

Note that the extremal graph in Fielder–Nikiforov’s result is $K_{n-1}\cup
K_{1}$, which is not connected. Moreover, if a graph contains a Hamilton path,
then it must be connected. In 2012, Lu, Liu and Tian [130] generalized this
spectral condition to connected graphs.

######  Theorem 3.7 (Lu–Liu–Tian [130]).

Let $G$ be a graph on $n\geq 7$ vertices. If $G$ is connected and

$\lambda(G)\geq\sqrt{(n-3)^{2}+2},$

then $G$ contains a Hamilton path.

We remark here that the original statement of Theorem 3.7 (see [130, Theorem
3.4]) requires the restriction $n\geq 5$, this is a typo because for $n=6$, we
can verify that $\lambda(K_{2}\vee I_{4})=\frac{1+\sqrt{33}}{2}\approx
3.372>\sqrt{3^{2}+2}\approx 3.316$ and $K_{2}\vee I_{4}$ does not contain
Hamilton path. By a careful examination, the restriction should be modified to
$n\geq 7$.

######  Theorem 3.8 (Ning–Ge [150]).

Let $G$ be a graph on $n\geq 4$ vertices with $\delta(G)\geq 1$. If

$\lambda(G)>n-3,$

then $G$ has a Hamilton path or $G\in\\{K_{1}\vee(K_{n-3}\cup I_{2}),K_{2}\vee
I_{4},K_{1}\vee(K_{1,3}\cup K_{1})\\}$.

When the minimum degree is involved in contrast with the results in [73],
using the adjacency spectral radius, Li and Ning [111] obtained the following
result.

######  Theorem 3.9 (Li–Ning [111]).

Let $\delta\geq 0$ and $n\geq\max\\{6\delta+10,(\delta^{2}+7\delta+8)/2\\}$.
If $G$ is a graph of order $n$ with minimum degree $\delta(G)\geq\delta$ and

$\lambda(G)\geq\lambda(K_{\delta}\vee(K_{n-2\delta-1}\cup I_{\delta+1})),$

then $G$ has a Hamilton path, unless $G=K_{\delta}\vee(K_{n-2\delta-1}\cup
I_{\delta+1})$.

######  Theorem 3.10 (Li–Ning [111]).

Let $\delta\geq 0$ and $n\geq\max\\{6\delta+10,(3\delta^{2}+9\delta+8)/2\\}$.
If $G$ is a graph of order $n$ with minimum degree $\delta(G)\geq\delta$ and

$q(G)\geq q(K_{\delta}\vee(K_{n-2\delta-1}\cup I_{\delta+1})),$

then $G$ has a Hamilton path, unless $G=K_{\delta}\vee(K_{n-2\delta-1}\cup
I_{\delta+1})$.

Theorem 3.9 was generalized by Nikiforov [149, Theorem 1.5] as below.

######  Theorem 3.11 (Nikiforov [149]).

Let $\delta\geq 1$ and $n\geq\delta^{3}+\delta^{2}+2\delta+5$. If $G$ is a
graph on $n$ vertices with minimum degree $\delta(G)\geq\delta$ and

$\lambda(G)\geq n-\delta-2,$

then $G$ has a Hamilton path unless $G=K_{\delta}\vee(K_{n-2\delta-1}\cup
I_{\delta+1})$ or $G=K_{\delta+1}\cup K_{n-\delta-1}$.

The following version of the signless Laplacian spectral radius is a special
case of Theorem 3.19, which will be introduced in next subsection.

######  Theorem 3.12 (Cheng et al. [39]).

Let $\delta\geq 1$ and $n\geq\delta^{4}+9\delta^{3}+24\delta^{2}+23\delta+15$.
If $G$ is a connected graph on $n$ vertices with minimum degree
$\delta(G)\geq\delta$ and

$q(G)\geq 2(n-\delta-2),$

then either $G$ has a Hamilton path or $G$ is a subgraph of
$K_{\delta}\vee(K_{n-2\delta-1}\cup I_{\delta+1})$ by removing at most
$\lfloor{\delta(\delta+1)}/{4}\rfloor$ edges.

Moreover, comparing the Moon–Moser theorem with the Erdős theorem, we can
similarly consider the existence of Hamilton path in bipartite graphs. Note
that if a bipartite graph has a Hamilton path, then it must be balanced and
nearly balanced, i.e., the sizes of two vertex parts differs at most one.

In 2017, Li and Ning [112] established several spectral analogues of Moon and
Moser’s theorem on Hamilton paths in balanced bipartite graphs and nearly
balanced bipartite graphs. We remark that one main ingredient of their proofs
is a structural stability result involving Hamilton paths in balanced
bipartite graphs with given minimum degree and number of edges. To some
extent, the line of proof is similar with that in [111].

In 2020, Wei and You [170, Theorem 1.5] further extended Nikiforov’s result
(Theorem 3.11) by improving the bound of order $n$ by almost a half. In
addition, the authors [170, Theorem 1.8] also obtained spectral sufficient
conditions for a graph to be traceable among graphs or balanced bipartite
graphs with large minimum degree, which extended a result of Li and Ning for
balanced bipartite graph being traceable. Futhermore, Liu, Wu and Lai [128]
unified these several former spectral Hamiltonian results on balanced
bipartite graphs and complementary graphs.

###  3.2 Problem for path coverability

In this section, we consider the $k$-path-coverable problem. A graph $G$ is
$k$-path-coverable if $V(G)$ can be covered by $k$ or fewer vertex-disjoint
paths. In particular, 1-path-coverable is the same as traceable. So the
concept of $k$-path coverability is a natural extension of the Hamilton path.
The disjoint path cover problem is strongly related to the well-known
hamiltonian problem (one may refer to [117] for a survey), which is among the
most fundamental ones in graph theory, and attracts much attention in
theoretical computer science. However, this problem is NP-complete [161],
therefore, finding their guaranteed sufficient conditions becomes an
interesting work. In [119], such Ore-type condition is obtained.

######  Theorem 3.13 (Bondy–Chvátal [23]).

A graph $G$ is $k$-path coverable if and only if the closure graph
$\mathrm{cl}_{n-k}(G)$ is $k$-path coverable. In particular, if $d(u)+d(v)\geq
n-k$ for all non-edges $\\{u,v\\}$, then $\mathrm{cl}_{n-k}(G)=K_{n}$ and $G$
is $k$-path coverable.

######  Theorem 3.14.

[23, 110] Let $G$ be an $n$-vertex graph with degree sequence $d_{1}\leq
d_{2}\leq\cdots\leq d_{n}$. Suppose $k\geq 1$. If $G$ is not $k$-path-
coverable, then there exists $1\leq i<\frac{n-k}{2}$ such that $d_{i+k}\leq i$
and $d_{n-i}\leq n-i-k-1$.

######  Theorem 3.15 (Feng et al. [70]).

Let $k\geq 2$, and let $G$ be a graph of order $n\geq 5k+6$. If

$e(G)\geq{n-k-1\choose 2}+k+1,$

then either $G$ is $k$-path-coverable or $G=K_{1}\vee(K_{n-k-2}\cup I_{k+1})$.

For every integers $k\geq 1$ and $\delta\geq 1$, we denote

$\boxed{{B}_{n,k,\delta}:=K_{\delta}\vee(K_{n-2\delta-k}\cup{I_{\delta+k}}).}$

Clearly, ${B}_{n,k,\delta}$ is not $k$-path-coverable and
$e({B}_{n,k,\delta})={n-\delta-k\choose 2}+(\delta+k)\delta$. We next extend
Theorem 3.15 by introducing the minimum degree. Clearly, when we set
$\delta=1$, the following theorem reduces to Theorem 3.15.

######  Theorem 3.16.

Let $k\geq 1$ and $G$ be a graph on $n\geq 5k+6\delta$ vertices. If the
minimum degree $\delta(G)\geq\delta$ and

$e(G)\geq e({B}_{n,k,\delta}),$

then $G$ is $k$-path-coverable or $G={B}_{n,k,\delta}$.

###### Proof.

Assume that $G$ is not $k$-path-coverable. By Theorem 3.13, we know that the
closure graph $H:=\mathrm{cl}_{n-k}(G)$ is also not $k$-path-coverable. We
denote by $d_{1}\leq d_{2}\leq\cdots\leq d_{n}$ the degree sequence of $H$. By
Theorem 3.14, there exists an integer $1\leq m\leq\frac{n-k-1}{2}$ such that
$d_{m+k}\leq m$ and $d_{n-m}\leq n-m-k-1$. Thus we get

$\displaystyle 2e(H)=\sum\limits_{i=1}^{n}d_{i}$
$\displaystyle\leq(m+k)m+(n-2m-k)(n-m-k-1)+m(n-1)$
$\displaystyle=3m^{2}-(2n-4k-1)m+(n-k)(n-k-1).$ (8)

We denote by $f(m):=3m^{2}-(2n-4k-1)m$. Since
$\delta\leq\delta(G)\leq\delta(H)\leq m\leq\frac{n-k-1}{2}$. The function
$f(m)$ is minimized at $m_{0}=\frac{2n-4k-1}{6}$. By the condition $n\geq
6\delta+5k$, we have $m_{0}-\delta>\frac{n-k-1}{2}-m_{0}$. Hence, the function
$f(m)$ is maximized at $m=\delta$, which yields

$2e(G)\leq 2e(H)\leq
f(\delta)+(n-k)(n-k-1)=2e(K_{\delta}\vee(K_{n-2\delta-k}\cup I_{\delta+k})).$

Combing the condition, we get $e(G)=e(K_{\delta}\vee(K_{n-2\delta-k}\cup
I_{\delta+k}))$, and all the above inequalities in (8) become equalities.
Hence, we have $m=\delta$ and $G=\mathrm{cl}_{n-k}(G)$, the degrees of $G$ are
$d_{1}=\cdots=d_{\delta+k}=\delta,d_{\delta+k+1}=\cdots=d_{n-\delta}=n-\delta-k-1$
and $d_{n-\delta+1}=\cdots=d_{n}=n-1$. Next, we shall prove that
$G=K_{\delta}\vee(K_{n-2\delta-k}\cup I_{\delta+k})$.

Let $v_{1},v_{2},\ldots,v_{n}$ be the vertices of $G$ corresponding to the
degrees $d_{1}$, $d_{2}$, $\ldots$, $d_{n}$. We denote by
$X:=\\{v_{1},v_{2},\ldots,v_{\delta+k}\\}$ and
$Y:=\\{v_{\delta+k+1},\ldots,v_{n}\\}$. First of all, we show that the induced
subgraph $G[Y]$ forms a clique. Otherwise, let $u$ and $v$ be two non-adjacent
vertices in $Y$. From the definition of the $(n-k)$-closure graph, we know
that $d_{G}(u)+d_{G}(v)<n-k$. On the other hand, we have
$d_{G}(u)+d_{G}(v)\geq 2(n-\delta-k-1)>n-k$, a contradiction. So we get
$G[Y]=K_{n-\delta-k}$. Let $F$ be the set of vertices in $Y$ with degree
$n-1$, that is, $F=\\{v_{n-\delta+1},\cdots,v_{n}\\}$. We denote by $G[X,F]$
the induced bipartite subgraph of $G$ between vertex sets $X$ and $F$.
Finally, we shall prove $G[X,F]=K_{\delta+k,\delta}$. Since each vertex of $F$
has degree $n-1$, so it adjacent to every vertex of $X$. Note that the vertex
of $X$ has degree $\delta=|F|$, so $X$ is an independent set of $G$. Then
$G[X,F]=K_{\delta+k,\delta}$. Hence, we get
$G=K_{\delta}\vee(K_{n-2\delta-k}\cup I_{\delta+k})$. ∎

In 2020, by generalizing the results in Theorem 3.9 and Theorem 3.11, Liu et
al. [125] obtained the following sufficient conditions by using the adjacency
spectral radius.

######  Theorem 3.17 (Liu et al. [125]).

Let $k\geq 1,\delta\geq 2$ and $n\geq n_{0}(\delta,k)$ where

$n_{0}(\delta,k)=\max\\{\delta^{2}(\delta+k)+\delta+k+5,5k+6\delta+6\\}.$

If $G$ is a connected graph on $n$ vertices with minimum degree
$\delta(G)\geq\delta$ and

$\lambda(G)\geq n-\delta-k-1,$

then $G$ is $k$-path-coverable unless $G={B}_{n,k,\delta}$.

Since $K_{n-\delta-k}$ is a proper subgraph of ${B}_{n,k,\delta}$, we have

$\lambda({B}_{n,k,\delta})>\lambda(K_{n-\delta-k})=n-\delta-k-1.$

Hence, we get immediately the following corollary.

######  Corollary 3.18 (Liu et al. [125]).

Let $k\geq 1$, $\delta\geq 2$ and $n\geq n_{0}(\delta,k)$. If $G$ is a
connected graph of order $n$ with minimum degree $\delta(G)\geq\delta$ and

$\lambda(G)\geq\lambda({B}_{n,k,\delta}),$

then $G$ is $k$-path-coverable unless $G={B}_{n,k,\delta}$.

In the sequel, we will consider the $Q$-index version of Theorem 3.17. Recall
that ${B}_{n,k,\delta}=K_{\delta}\vee(K_{n-2\delta-k}\cup{I_{\delta+k}})$. For
the graph ${B}_{n,k,\delta}$, let $X=\\{v\in
V({B}_{n,k,\delta}):d(v)=k\\},Y=\\{v\in V({B}_{n,k,\delta}):d(v)=n-1\\}$, and
$Z=\\{v\in V({B}_{n,k,\delta}):d(v)=n-k-\delta-1\\}$. We denote by
$E_{1}({B}_{n,k,\delta})$ the edge set of ${B}_{n,k,\delta}$ whose endpoints
are both from $Y\cup Z.$ Moreover, we define

$\displaystyle\mathcal{B}^{(1)}_{n,k,\delta}=\left\\{{B}_{n,k,\delta}\setminus
E^{\prime}:\mbox{$E^{\prime}\subseteq E_{1}({B}_{n,k,\delta})$ with
$|E^{\prime}|\leq\left\lfloor{(\delta+k)\delta}/{4}\right\rfloor$}\right\\}.$

Here, the symbol ${B}_{n,k,\delta}\setminus E^{\prime}$ stands for the
subgraph of ${B}_{n,k,\delta}$ by deleting all edges from the edge set
$E^{\prime}$. Recently, Cheng, Feng, Li and Liu [39] proved the following
extension on the sufficient conditions of the existence of a Hamilton path.

######  Theorem 3.19 (Cheng et al. [39]).

Let $k\geq 1,\delta\geq 2$ and $n\geq n_{1}(\delta,k)$ where

$n_{1}(\delta,k)=(\delta^{2}+k\delta+7\delta+6k+9)(\delta^{2}+k\delta+1)$

If $G$ is a connected graph on $n$ vertices and minimum degree
$\delta(G)\geq\delta$ such that

$q(G)\geq 2(n-\delta-k-1),$

then either $G$ is $k$-path-coverable or $G\in\mathcal{B}^{(1)}_{n,k,\delta}$.

######  Corollary 3.20.

Let $k\geq 1$, $\delta\geq 2$ and $n\geq n_{1}(\delta,k)$. If $G$ is a
connected graph of order $n$ with minimum degree $\delta(G)\geq\delta$ and

$q(G)\geq q({B}_{n,k,\delta}),$

then $G$ is $k$-path-coverable unless $G={B}_{n,k,\delta}$.

##  4 Spectral problem for connectivity

###  4.1 Problem for $k$-connectivity

A connected graph $G$ is said to be _$k$ -connected_ (or _$k$ -vertex-
connected_) if it has more than $k$ vertices and remains connected whenever
fewer than $k$ vertices are deleted. In particular, $1$-connected graphs are
the general connected graphs. The connectivity of $G$, written as $\kappa(G)$,
is defined as the maximum integer $k$ such that $G$ is $k$-connected. In other
words, the connectivity of a graph $G$ is the minimum number of vertices that
we need to delete to make $G$ disconnected. From the definition, we can see
that $\kappa(G)\geq k$ is equivalent to say that $G$ is $k$-connected.

When we talk about the connectivity and the eigenvalues, perhaps the most
famous one is due to Fiedler [72] which states that the second smallest
Laplacian eigenvalue is at most the connectivity for any non-complete graph.
For adjacency eigenvalues, the relation between the connectivity, edge-
connectivity and the eigenvalues was reported in [46, 84, 197, 200].

Let $G$ be a simple graph of order $n\geq k+1$. It is known [15, Page 4] that
if $\delta(G)\geq\frac{1}{2}(n+k-2),$ then $G$ is $k$-connected. In 1969,
Bondy [20] provided a sufficient condition on the degree sequence.

######  Theorem 4.1 (Bondy–Chvátal [23]).

A graph $G$ is $k$-connected if and only if the closure graph
$\mathrm{cl}_{n+k-2}(G)$ is $k$-connected. In particular, if $d(u)+d(v)\geq
n+k-2$ for all non-edges $\\{u,v\\}$, then $\mathrm{cl}_{n+k-2}(G)=K_{n}$ and
$G$ is $k$-connected.

######  Lemma 4.2 (Bondy [20]).

Suppose that $n\geq k+1$ and $G$ is an $n$-vertex graph with degree sequence
$d_{1}\leq d_{2}\leq\cdots\leq d_{n}$. If $G$ is not $k$-connected, then there
exists $1\leq i\leq\frac{n-k+1}{2}$ such that $d_{i}\leq i+k-2$ and
$d_{n-k+1}\leq n-i-1$.

Sometimes we can characterize the vertex-connectivity using the information
about co-degrees of vertices in our graph. Such result was used in [61] to
determine the vertex-connectivity of dense random $d$-regular graphs.

######  Theorem 4.3 (Krivelevich et al. [103]).

Let $G=(V,E)$ be a $d$-regular graph on $n$ vertices such that $\sqrt{n}\log
n<d\leq 3n/4$ and the number of common neighbors for every two distinct
vertices in $G$ is $(1+o(1))d^{2}/n$. Then the graph $G$ is $d$-vertex-
connected.

######  Theorem 4.4 (Wu–Zhang–Feng [173]).

Let $G$ be a connected graph on $n\geq 5$ vertices. If the minimum degree
$\delta(G)\geq 2$ and

$e(G)\geq{n-2\choose 2}+3,$

then $G$ is $2$-connected unless $G=K_{1}\vee(K_{n-3}\cup K_{2})$.

######  Theorem 4.5 (Feng et al. [70]).

Let $G$ be a graph of order $n\geq k+1\geq 2$. If

$e(G)\geq{n-1\choose 2}+k-1,$

then either $G$ is $k$-connected or $G=K_{k-1}\vee(K_{1}\cup K_{n-k})$.

The above result was extended by Feng et al. [71, Theorem 3.2]. Clearly, when
we set $\delta=k-1$, then Theorem 4.6 reduces to Theorem 4.5. For convenience,
we denote

$\boxed{A_{n,k,\delta}:=K_{k-1}\vee(K_{\delta-k+2}\cup K_{n-\delta-1}).}$

It is easy to see that $A_{n,k,\delta}$ is not $k$-connected and
$e(A_{n,k,\delta})=\frac{1}{2}n^{2}-(\delta-k+\tfrac{5}{2})n+(\delta+1)(\delta-k+2)$.
In 2017, Feng et al. [71, Theorem 3.2] proved that $A_{n,k,\delta}$ is the
unique graph that is not $k$-connected and has the maximum number of edges.

######  Theorem 4.6 (Feng et al. [71]).

Let $G$ be a connected graph on $n$ vertices with minimum degree
$\delta(G)\geq\delta$. If

$e(G)\geq e(A_{n,k,\delta}),$

then either $G$ is $k$-connected or $G=A_{n,k,\delta}$.

From the spectral point of view, we naturally ask the following question: can
one find a sufficient spectral condition for a connected graph to be
$k$-connected? For pseudo-random graphs, Krivelevich and Sudakov [105, Theorem
4.1] provided a sufficient condition on the second largest eigenvalue in
absolute value for regular graphs.

######  Theorem 4.7.

[105] Let $G$ be a $d$-regular graph on $n$ vertices with $d\leq n/2$. We
denote $\mu=\max\\{|\lambda_{i}|:i\in[n],\lambda_{i}\neq d\\}$. Then the
connectivity of $G$ satisfies $\kappa(G)\geq d-{36\mu^{2}}/{d}$.

In 2019, Wu, Zhang and Feng [173] presented the sufficient spectral condition
of a connected graph to be $2$-connected with small minimum degree.

######  Theorem 4.8 (Wu–Zhang–Feng [173]).

Let $G$ be a connected graph on $n\geq 5$ vertices. If the minimum degree
$\delta(G)\geq 2$ and

$\lambda(G)\geq\sqrt{(n-3)^{2}+4},$

then $G$ is $2$-connected.

######  Theorem 4.9 (Feng et al. [71]).

Let $\delta\geq k\geq 3$ and $n\geq n_{0}(k,\delta)$ where

$n_{0}(k,\delta)=(\delta-k+2)(k^{2}-2k+4)+3.$

If $G$ is a connected graph of order $n$ with minimum degree
$\delta(G)\geq\delta$ and

$\lambda(G)\geq n-\delta+k-3,$

then $G$ is $k$-connected unless $G=A_{n,k,\delta}$.

Since $\lambda(A_{n,k,\delta})\geq n-\delta+k-3,$ we immediately have

######  Corollary 4.10 (Feng et al. [71]).

Let $\delta\geq k\geq 3$ and $n\geq n_{0}(k,\delta)$. Let $G$ be a connected
graph of order $n$ and minimum degree $\delta(G)\geq\delta$. If

$\lambda(G)\geq\lambda(A_{n,k,\delta}),$

then $G$ is $k$-connected unless $G=A_{n,k,\delta}$.

Recall that
${A}_{n,k,\delta}=K_{k-1}\vee(K_{\delta-k+2}\cup{K_{n-\delta-1}})$. For the
graph ${A}_{n,k,\delta}$, let $X=\\{v\in V({A}_{n,k,\delta}):d(v)=\delta\\}$,
$Y=\\{v\in V({A}_{n,k,\delta}):d(v)=n-1\\}$ and $Z=\\{v\in
V({A}_{n,k,\delta}):d(v)=n-\delta+k-3\\}$. Let $E_{1}({A}_{n,k,\delta})$
denote the edge set of ${A}_{n,k,\delta}$ whose endpoints are both from $Y\cup
Z.$ We define

$\mathcal{A}^{(1)}_{n,k,\delta}=\left\\{{A}_{n,k,\delta}\setminus
E^{\prime}:\mbox{$E^{\prime}\subseteq E_{1}({A}_{n,k,\delta})$ with
$|E^{\prime}|\leq\left\lfloor{(\delta-k+2)(k-1)}/{4}\right\rfloor$}\right\\}.$

Here, we denote by $A_{n,k,\delta}\setminus E^{\prime}$ the graph obtained
from $A_{n,k,\delta}$ by deleting all edges of the edge set $E^{\prime}$.
Recently, it was proved in [191] that

######  Theorem 4.11 (Zhang et al. [191]).

Let $\delta\geq k\geq 3$ and $n\geq n_{1}(k,\delta)$ where

$n_{1}(k,\delta)=(k^{2}+2k-3)\delta^{2}-(2k^{3}-k^{2}-17k+8)\delta+(k^{4}-3k^{3}-8k^{2}+23k+4).$

If $G$ is a connected graph of order $n$ with minimum degree
$\delta(G)\geq\delta$ and

$q(G)\geq 2(n-\delta+k-3),$

then $G$ is $k$-connected unless $G\in\mathcal{A}^{(1)}_{n,k,\delta}$.

######  Corollary 4.12.

Let $\delta\geq k\geq 3$ and $n\geq n_{1}(k,\delta)$. Let $G$ be a connected
graph of order $n$ and minimum degree $\delta(G)\geq\delta$. If

$q(G)\geq q(A_{n,k,\delta}),$

then $G$ is $k$-connected unless $G=A_{n,k,\delta}$.

###  4.2 Problem for $k$-edge-connectivity

Similarly to vertex-connectivity, we now define the edge-connectivity of a
graph. A simple graph $G$ is _$k$ -edge-connected_ if it has at least two
vertices and remains connected whenever fewer than $k$ edges are deleted. The
edge-connectivity of $G$, written as $\kappa^{\prime}(G)$, is defined as the
maximum $k$ such that $G$ is $k$-edge-connected. In particular, $1$-edge-
connected graphs are the general connected graphs. Clearly, it is well-known
that $\kappa(G)\leq\kappa^{\prime}(G)$. Moreover, the edge-connectivity is
always at most the minimum degree of a graph.

######  Theorem 4.13 (Bondy–Chvátal [23]).

A graph $G$ is $k$-edge-connected if and only if the closure graph
$\mathrm{cl}_{n+k-2}(G)$ is $k$-edge-connected. In particular, if
$d(u)+d(v)\geq n+k-2$ for all non-edges $\\{u,v\\}$, then
$\mathrm{cl}_{n+k-2}(G)=K_{n}$ and $G$ is $k$-edge-connected.

######  Lemma 4.14 (Bauer et al. [9]).

Let $G$ be an $n$-vertex graph with degree sequence $d_{1}\leq
d_{2}\leq\cdots\leq d_{n}$. Suppose $n\geq k+1$, and $d_{1}\geq k\geq 1$. If
$G$ is not $k$-edge-connected, then there exists $k+1\leq
i\leq\lfloor{n}/{2}\rfloor$ such that $d_{i-k+1}\leq i-1$, $d_{i}\leq i+k-2$
and $d_{n}\leq n-i+k-2$. In particular, if $k\geq\lfloor{n}/{2}\rfloor$, then
$G$ is $k$-edge-connected.

For adjacency eigenvalues, the relation between the connectivity, edge-
connectivity and the eigenvalues was reported in [41, 46, 84, 126, 153].

First of all, we introduce some results that only deal with regular graphs.

######  Theorem 4.15 (Krivelevich–Sudakov [105]).

Let $G$ be a $d$-regular graph on $n$ vertices. If $\lambda_{2}(G)\leq d-2$,
then $\kappa^{\prime}(G)=d$.

Extending and improving the the previous results, Cioabă [41] obtained that

######  Theorem 4.16 (Cioabă [41]).

Let $d\geq k\geq 2$. If the second largest eigenvalue $\lambda_{2}$ of a
$d$-regular graph satisfies

$\lambda_{2}<d-\frac{(k-1)n}{(d+1)(n-d-1)},$

then the edge-connectivity of $G$ is at least $k$.

Now, we consider the $k$-edge-connected property. Since every $k$-connected
graph is also $k$-edge-connected. So Theorem 4.5 also provided a sufficient
condition for a graph to be $k$-edge-connected. Next, we shall present a
sufficient condition with a smaller lower bound, which is slightly different
from Theorem 4.5.

######  Theorem 4.17 (Feng et al. [70]).

Let $G$ be a graph of order $n\geq k+1$. If $k\geq 2$ and
$e(G)\geq\frac{1}{2}(n^{2}-(k+4)n+2k^{2}+2k+4)$, then $G$ is $k$-edge-
connected.

###### Proof.

Suppose that $G$ is not $k$-edge-connected. Then from Lemma 4.14, there exists
an integer $k+1\leq i\leq\frac{n}{2}$ such that $d_{i-k+1}\leq i-1$,
$d_{i}\leq i+k-2$ and $d_{n}\leq n-i+k-2$. In particular, note that $n\geq
2k+2$. We have

$\displaystyle 2e(G)$
$\displaystyle\leq(i-k+1)(i-1)+(k-1)(i+k-2)+(n-i)(n-i+k-2)$
$\displaystyle=n(n-1)+(k-1)(n+k-1)+2i^{2}-(2n+k-1)i.$

Suppose $f(x)=2x^{2}-(2n+k-1)x$ with $k+1\leq x\leq\frac{n}{2}$. Then it is
easy to check that $f(k+1)-f(\frac{n}{2})=\frac{(n-k-3)(n-2k-2)}{2}\geq 0$,
with equality if and only if $n=2k+2$. It follows that
$f_{\max}(x)=f(k+1)=-(k+1)(2n-k-3)$, and we have

$\displaystyle 2e(G)$ $\displaystyle\leq n(n-1)+(k-1)(n+k-1)-(k+1)(2n-k-3)$
$\displaystyle=n^{2}-(k+4)n+2k^{2}+2k+4.$

Thus $e(G)=\frac{1}{2}(n^{2}-(k+4)n+2k^{2}+2k+4)$, and we have $i=k+1$, and
the degree sequence is given as $d_{1}=d_{2}=k$, $d_{3}=\cdots=d_{k+1}=2k-1$
and $d_{k+2}=\cdots=d_{n}=n-3$.

Next, we show that if $G$ has this degree sequence, then it must be $k$-edge-
connected, which will be a contradiction. It suffices to show that for any
partition $V(G)=A\cup B$, where $|A|+|B|=n$ and $1\leq|A|\leq|B|$, we have
$e(A,B)\geq k$.

Since $G$ has minimum degree $\delta(G)=k$, if $|A|=1$, then $e(A,B)\geq k$,
and if $|A|=2$, then $e(A,B)\geq 2(k-1)\geq k$.

Now, let $|A|\geq 3$. Note that $n\geq 2k+2$ and $|A|\leq|B|$ imply $|B|\geq
k+1$. Firstly, if $|B|=k+1$, then we also have $|A|=k+1$. Thus by the symmetry
of $A$ and $B$, we may assume that $A$ has $k$ vertices with degree at least
$2k-1$ in $G$. Then, each such vertex in $A$ has at least $(2k-1)-k\geq 1$
neighbour in $B$, and hence $e(A,B)\geq k$.

Secondly, suppose that $|B|\geq k+2$. If $A$ contains a vertex $v$ with
$d_{G}(v)=n-3$, then $v$ has at least $|B|-2\geq k$ neighbours in $B$, and
$e(A,B)\geq k$. Otherwise, all vertices with degree $n-3$ in $G$ lie in $B$.
Since $|A|\geq 3$, each such vertex in $B$ has at least $|A|-2\geq 1$
neighbour in $A$. Since there are $n-(k+1)\geq(2k+2)-(k+1)>k$ such vertices,
it follows again that $e(A,B)\geq k$. This completes the proof. ∎

###  4.3 Problem for Hamilton-connectivity

A graph is Hamilton-connected if for every pair of vertices $u,v$, there is a
Hamilton path from $u$ to $v$. It is well-known [25, p. 474] that a graph $G$
is traceable from every vertex if and only if $G\vee K_{1}$ is Hamilton-
connected.

######  Theorem 4.18 (Dirac [53], Ore [155]).

If $G$ is a graph on $n\geq 3$ vertices with minimum degree
$\delta(G)\geq\frac{n+1}{2}$, then $G$ is Hamilton-connected.

######  Theorem 4.19 (Bondy–Chvatal [23]).

Let $G$ be a simple graph on $n$ vertices. Then $G$ is Hamilton-connected if
and only if the closure graph $\mathrm{cl}_{n+1}(G)$ is Hamilton-connected. In
particular, if $d(u)+d(v)\geq n+1$ for all non-edges $\\{u,v\\}$, then
$\mathrm{cl}_{n+1}(G)=K_{n}$ and $G$ is Hamilton-connected.

######  Theorem 4.20 (Berge [13]).

Let $G$ be an $n$-vertex graph with degree sequence $d_{1}\leq
d_{2}\leq\cdots\leq d_{n}$. If $G$ is not Hamilton-connected, then there
exists an integer $2\leq i\leq\frac{n}{2}$ such that $d_{i-1}\leq i$ and
$d_{n-i}\leq n-i$.

The following sufficient condition on the number of edges is due to Ore [156].

######  Theorem 4.21 (Ore [156]).

Let $G$ be a graph on $n$ vertices. If

$e(G)\geq{n-1\choose 2}+3,$

then $G$ is Hamilton-connected.

In 2017, Zhou and Wang [196] gave some sufficient conditions on the number of
edges, the spectral radius and the signless Laplacian spectral radius for a
graph to be Hamilton-connected. And they also studied sufficient conditions on
the number of edges, the spectral radius and the signless Laplacian spectral
radius for a graph to be traceable from every vertex.

######  Theorem 4.22 (Zhou–Wang [196]).

Let $G$ be a connected graph on $n\geq 6$ vertices with minimum degree
$\delta(G)\geq 3$. If

$e(G)\geq{n-2\choose 2}+6,$

then $G$ is Hamilton-connected unless $G=K_{3}\vee(K_{n-5}\cup I_{2})$ and the
following more exceptions: when $n=8$ and $G\in\\{K_{4}\vee
I_{4},K_{3}\vee(K_{1,3}\cup K_{1}),K_{3}\vee(K_{1,2}\cup K_{2}),K_{2}\vee
K_{2,4}\\}$; when $n=9$ and $G=K_{4}\vee(K_{2}\cup I_{3})$; when $n=10$ and
$G\in\\{K_{5}\vee I_{5},K_{4}\vee(K_{1,4}\cup K_{1}),K_{3}\vee K_{2,5}\\}$;
when $n=11$ and $G=K_{4}\vee(K_{1,3}\cup K_{2})$; when $n=12$ and $G=K_{6}\vee
I_{6}$.

######  Theorem 4.23 (Zhou–Wang [196]).

Let $G$ be a connected graph on $n\geq 6$ vertices with minimum degree
$\delta(G)\geq 3$. If

$\lambda(G)\geq\sqrt{(n-3)^{2}+10},$

then $G$ is Hamilton-connected.

######  Theorem 4.24 (Zhou–Wang [196]).

Let $G$ be a connected graph on $n\geq 6$ vertices with minimum degree
$\delta(G)\geq 3$. If

$q(G)\geq 2(n-3)+\frac{14}{n-1},$

then $G$ is Hamilton-connected unless $n=8$ and $G=K_{4}\vee I_{4}$.

In 2020, Zhou, Wang and Lu [198] provided a further improvement on Theorems
4.22, 4.23 and 4.24. More precisely, they proved that if $n\geq 11$ and $G$
satisfies $\delta(G)\geq 3$ and $e(G)\geq{n-3\choose 2}+13$, then $G$ is
Hamilton-connected unless $G$ belongs to some exceptions.

######  Theorem 4.25 (Zhou–Wang–Lu [198]).

Let $G$ be a connected graph on $n\geq 14$ vertices with minimum degree
$\delta\geq 3$. If

$\lambda(G)>n-3,$

then $G$ is Hamilton-connected unless $G=K_{3}\vee(K_{n-5}\cup{I_{2}})$ or
$G=K_{2}\vee(K_{n-4}\cup K_{2})$.

######  Theorem 4.26 (Zhou–Wang–Lu [198]).

Let $G$ be a connected graph on $n\geq 13$ vertices with minimum degree
$\delta\geq 3$. If

$q(G)>2(n-3)+\frac{6}{n-1},$

then $G$ is Hamilton-connected unless $G=K_{3}\vee(K_{n-5}\cup{I_{2}})$.

For notational convenience, we denote

$\boxed{S_{n,\delta}:=K_{\delta}\vee(K_{n-2\delta+1}\cup{I_{\delta-1}})}$

and

$\boxed{T_{n,\delta}:=K_{2}\vee(K_{n-\delta-1}\cup K_{\delta-1}).}$

Clearly, we can verify that both $S_{n,\delta}$ and $T_{n,\delta}$ are not
Hamilton-connected and $\delta(S_{n,\delta})=\delta(T_{n,\delta})=\delta$.
Moreover, we have $e(S_{n,\delta})={n-\delta+1\choose 2}+\delta(\delta-1)$ and
$e(T_{n,\delta})={n-\delta+1\choose 2}+{\delta-1\choose 2}+2(\delta-1)$.
Trivially, we have $S_{n,2}=T_{n,2}$ and $e(S_{n,\delta})>e(T_{n,\delta})$ for
every $\delta\geq 3$.

######  Theorem 4.27.

Let $\delta\geq 2$ and $G$ be a graph on $n\geq 6\delta-5$ vertices. If
$\delta(G)\geq\delta$ and

$e(G)\geq e(S_{n,\delta}),$

then either $G$ is Hamilton-connected or $G=S_{n,\delta}$.

###### Proof.

Assume that $G$ is not Hamilton-connected. By Theorem 4.19, we know that the
closure graph $H:=\mathrm{cl}_{n+1}(G)$ is also not Hamilton-connected. Let
$d_{1}^{\prime}\leq d_{2}^{\prime}\leq\cdots\leq d_{n}^{\prime}$ be the degree
sequence of $H$. By Theorem 4.20, there is an integer $2\leq m\leq\frac{n}{2}$
such that $d_{m-1}\leq m$ and $d_{n-m}\leq n-m$. Hence, we can get

$\displaystyle 2e(H)=\sum\limits_{i=1}^{n}d_{i}^{\prime}$
$\displaystyle\leq(n-1)m+(n-2m+1)(n-m)+m(n-1)$ (9)
$\displaystyle=3m^{2}-(2n+3)m+n^{2}+n.$

Let $f(m)=3m^{2}-(2n+3)m$ be a function on $m$. Note that
$\delta\leq\delta(G)\leq\delta(H)\leq m\leq\frac{n}{2}$, and the symmetric
line of $f(m)$ is $m_{0}=\frac{2n+3}{6}$. The condition $n\geq 6\delta-5$
implies $\frac{n}{2}-\frac{2n+3}{6}<\frac{2n+3}{6}-\delta$. So the maximum
value of $f(m)$ is attained at $m=\delta$, therefore

$2e(G)\leq 2e(H)\leq f(\delta)+n^{2}+n=2e(S_{n,\delta}),$

where $S_{n,\delta}=K_{\delta}\vee(I_{\delta-1}\cup K_{n-2\delta+1})$. The
condition in the theorem implies that $e(G)=e(H)=e(S_{n,\delta})$, and all
inequalities in (9) must be equalities, that is, $m=\delta$ and
$G=\mathrm{cl}_{n+1}(G)$, and hence the degree sequence of $G$ is
$d_{1}=\cdots=d_{\delta-1}=\delta$, $d_{\delta}=\cdots=d_{n-\delta}=n-\delta$,
and $d_{n-\delta+1}=\cdots=d_{n}=n-1$. Next we shall show that
$G=S_{n,\delta}$.

Let $v_{1},v_{2},\ldots,v_{n}$ be vertices of $G$ corresponding to the degrees
$d_{1},d_{2},\ldots,d_{n}$. We denote by
$X=\\{v_{1},v_{2},\ldots,v_{\delta-1}\\}$ and
$Y=\\{v_{\delta},v_{\delta+1},\ldots,v_{n}\\}$. First of all, we shall prove
that the induced subgraph $G[Y]=K_{n-\delta+1}$. Otherwise, there are two non-
adjacent vertices $v_{r},v_{s}\in G[Y]$. By the definition of the
$(n+1)$-closure graph, we know that

$d_{G}(v_{r})+d_{G}(v_{s})=d_{H}(v_{r})+d_{H}(v_{s})<n+1.$

On the other hand, we have $d_{G}(v_{r})+d_{G}(v_{s})\geq 2(n-\delta)>n+1$, a
contradiction. Thus, the induced subgraph $G[Y]=K_{n-\delta+1}$. Note that $Y$
contains $\delta$ vertices with degree $n-1$, we denote these vertices by
$F=\\{v_{n-\delta+1},\ldots,v_{n}\\}$. Every vertex of $F$ is adjacent to the
vertex of $X$. Since the vertex of $X$has degree $\delta$, we can get that $X$
is an independent set in $G$, thus we have $G[X,F]=K_{\delta-1,\delta}$. The
above discussion reveals that $G=K_{\delta}\vee(I_{\delta-1}\cup
K_{n-2\delta+1})$. This completes the proof. ∎

Recently, Chen et al. [37], Yu et al. [178], and Wei et al. [169]
independently showed the spectral version of Hamilton-connectedness for graphs
with large minimum degree.

######  Theorem 4.28 (Wei et al. [169]).

Let $\delta\geq 3$ and $n\geq n_{0}({\delta})$ where

$n_{0}({\delta})=\max\\{6\delta,(\delta^{3}-\delta^{2}+2\delta+8)/2\\}.$

If $G$ is a graph on $n$ vertices with the minimum degree
$\delta(G)\geq\delta$ and

$\lambda(G)\geq n-k,$

then $G$ is Hamilton-connected unless $G=S_{n,\delta}$ or $G=T_{n,\delta}$.

######  Corollary 4.29.

Let $\delta\geq 3$ and $n\geq n_{0}({\delta})$. If $G$ is a graph on $n$
vertices with the minimum degree $\delta(G)\geq\delta$ and

$\lambda(G)\geq\lambda(S_{n,\delta}),$

then $G$ is Hamilton-connected unless $G=S_{n,\delta}$.

In 2020, Zhou, Wang and Lu [199] presented the signless Laplacian spectral
conditions for Hamilton-connected graphs with large minimum degree.

For the graph $S_{n,\delta}$, let $X=\\{v\in
V(S_{n,\delta}):d(v)=\delta\\},Y=\\{v\in V(S_{n,\delta}):d(v)=n-1\\}$ and
$Z=\\{v\in V(S_{n,\delta}):d(v)=n-\delta\\}$. Let $E_{1}(S_{n,\delta})$ be the
subset of edges of $S_{n,\delta}$ whose both endpoints are from $Y\cup Z$. We
define the family of graphs as below

$\mathcal{S}_{n,\delta}^{(1)}=\left\\{S_{n,\delta}\setminus
E^{\prime}:E^{\prime}\subseteq
E_{1}(S_{n,\delta})~{}\text{and}~{}|E^{\prime}|\leq\bigl{\lfloor}{\delta(\delta-1)}/{4}\bigr{\rfloor}\right\\}.$

Here, we denote by $S_{n,\delta}\setminus E^{\prime}$ the graph obtained from
$S_{n,\delta}$ by deleting all edges of the edge set $E^{\prime}$. Similarly,
for the graph $T_{n,\delta}$, let $X=\\{v\in
V(T_{n,\delta}):d(v)=\delta\\},Y=\\{v\in V(T_{n,\delta}):d(v)=n-1\\}$ and
$Z=\\{v\in V(T_{n,\delta}):d(v)=n-\delta\\}$. Let $E_{1}(T_{n,\delta})$ be the
subset of $E(T_{n,\delta})$ containing the edges whose both endpoints are from
$Y\cup Z$. We denote

$\mathcal{T}_{n,\delta}^{(1)}=\Bigl{\\{}T_{n,\delta}\setminus
E^{\prime}:E^{\prime}\subseteq
E_{1}(T_{n,\delta})~{}\text{and}~{}|E^{\prime}|\leq\bigl{\lfloor}{(\delta-1)}/{2}\bigr{\rfloor}\Bigr{\\}}.$

When $G$ is a subgraph of $S_{n,\delta}$ or $T_{n,\delta}$, we can easily see
that $G$ is not Hamilton-connected. Moreover, we can verify that
$\delta(G)=\delta$ and $q(G)\geq 2(n-\delta)$ for every
$G\in\mathcal{S}_{n,\delta}^{(1)}\cup\mathcal{T}_{n,\delta}^{(1)}$.

######  Theorem 4.30 (Zhou–Wang–Lu [199]).

Let $\delta\geq 2$ and $n\geq n_{1}(\delta)$ where

$n_{1}(\delta)=\delta^{4}+5\delta^{3}+2\delta^{2}+8\delta+12.$

If $G$ is a graph of order $n$ with minimum degree $\delta(G)\geq\delta$ and

$q(G)\geq 2(n-\delta),$

then $G$ is Hamilton-connected unless $G\in\mathcal{S}^{(1)}_{n,\delta}$ or
$G\in\mathcal{T}^{(1)}_{n,\delta}$.

######  Corollary 4.31.

Let $\delta\geq 3$ and $n\geq n_{1}({\delta})$. If $G$ is a graph on $n$
vertices with minimum degree $\delta(G)\geq\delta$ and

$q(G)\geq q(S_{n,\delta}),$

then $G$ is Hamilton-connected unless $G=S_{n,\delta}$.

Recently, Xu, Zhai and Wang [176] present some sufficient conditions for a
graph to be Hamilton-connected in terms of size, spectral radius and signless
Laplacian spectral radius, respectively, which extend some corresponding
results.

##  5 Spectral problem for deficiency

###  5.1 Problem for given matching number

A matching in a graph is a set of disjoint edges, the matching number of $G$,
denoted by $\alpha^{\prime}(G)$, is the maximum size of a matching in $G$. A
perfect matching in $G$ is a matching covering all vertices.

In 1959, Erdős and Gallai [57] proved the following extremal problem for
$M_{k+1}$, a matching of $k+1$ edges; see [15, p. 58] and [4, Theorem 2] for
alternative proofs.

######  Theorem 5.1 (Erdős–Gallai [57]).

For any $n\geq 2k+1$, if $G$ is an $n$-vertex graph without copy of $M_{k+1}$,
then

$e(G)\leq\max\left\\{{2k+1\choose 2},{k\choose 2}+(n-k)k\right\\}.$

Moreover, the extremal are the following.
(1) If $2k+1\leq n<\frac{5k+3}{2}$, then $K_{2k+1}\cup I_{n-2k-1}$ is the
unique extremal graph.
(2) If $n=\frac{5k+3}{2}$, then there are two extremal graphs $K_{2k+1}\cup
I_{n-2k-1}$ and $K_{k}\vee I_{n-k}$.
(3) If $n>\frac{5k+3}{2}$, then $K_{k}\vee I_{n-k}$ is the unique extremal
graph.

Recently, Wang [175] proved that the two extremal graphs in Theorem 5.1 not
only have the maximum number of $s$-cliques for every $s\geq 2$, but also
attain the maximum number of $K_{s}\vee I_{t}$, which is the graph obtained
from $K_{s,t}$ by replacing the part of size $s$ by a clique of the same size.
We infer the interested reader to [175, 51] for recent progress.

In 2007, Feng, Yu and Zhang [66] proved the spectral version of Erdős–Gallai’s
theorem and determined the largest spectral radius with given matching number.
First of all, we can see that $K_{k}\vee I_{n-k}$ does not contain a matching
of size $k+1$ and

$\lambda(K_{k}\vee I_{n-k})=\frac{k-1+\sqrt{(k-1)^{2}+4k(n-k)}}{2}.$

######  Theorem 5.2 (Feng et el. [66]).

Let $G$ be a graph on $n$ vertices with matching number $k$.
(1) If $n=2k$ or $2k+1$, then $\lambda(G)\leq\lambda(K_{n})$ with equality if
and only if $G=K_{n}$.
(2) If $2k+2\leq n<3k+2$, then $\lambda(G)\leq 2k$ with equality if and only
if $G=K_{2k+1}\cup I_{n-2k-1}$.
(3) If $n=3k+2$, then $\lambda(G)\leq 2k$ with equality if and only if
$G=K_{k}\vee I_{n-k}$ or $G=K_{2k+1}\cup I_{n-2k-1}$.
(4) If $n>3k+2$, then $\lambda(G)\leq\lambda(K_{k}\vee I_{n-k})$ with equality
if and only if $G=K_{k}\vee I_{n-k}$.

In 2008, Yu [180] presented the spectral version for the signless Laplacian
radius. To some extent, the results and the extremal graphs are similar with
that of the adjacency spectral radius. Some tedious calculation yields

$q(K_{k}\vee I_{n-k})=\frac{n+2k-2+\sqrt{(n+2k-2)^{2}-8k^{2}+8k}}{2}.$

######  Theorem 5.3 (Yu [180]).

Let $G$ be a graph on $n$ vertices with matching number $k$.
(1) If $n=2k$ or $2k+1$, then $q(G)\leq q(K_{k})$, with equality if and only
if $G=K_{n}$.
(2) If $2k+2\leq n<\frac{5k+3}{2}$, then $q(G)\leq 4k$, with equality if and
only if $G=K_{2k+1}\cup I_{n-2k-1}$.
(3) If $n=\frac{5k+3}{2}$, then $q(G)\leq 4k$, with equality if and only if
$G=K_{k}\vee I_{n-k}$ or $G=K_{2k+1}\cup I_{n-2k-1}$.
(4) If $n>\frac{5k+3}{2}$, then $q(G)\leq q(K_{k}\vee I_{n-k})$ with equality
if and only if $G=K_{k}\vee I_{n-k}$.

###  5.2 Problem for perfect matching

The study of the relation between the eigenvalues and the matching number was
initiated by Brouwer and Haemers [27]. For regular graphs, they obtained

######  Theorem 5.4.

[27] Let $G$ be a connected $k$-regular graph on $n$ vertices with adjacency
eigenvalues
$k=\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}\geq\cdots\geq\lambda_{n}$. If $n$
is even and

$\lambda_{3}\leq\left\\{\begin{array}[]{ll}k-1+\frac{3}{k+1},&\hbox{if $k$ is
even,}\\\\[5.69054pt] k-1+\frac{3}{k+2},&\hbox{if $k$ is
odd,}\end{array}\right.$

then $G$ has a perfect matching.

Subsequently, Cioabă, Gregory and Haemers [44, 45] refined and generalized the
above result to obtain the following result for the $(r+1)$-th largest
eigenvalue.

######  Theorem 5.5.

[44] Let $G$ be a connected $k$-regular graph on $n$ vertices with eigenvalues
$k=\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}\geq\cdots\geq\lambda_{n}$. Assume
$r>0$ is an integer such that $n\equiv r{({\rm mod\,}2)}$. If

$k-\lambda_{r+1}>\left\\{\begin{array}[]{lll}0.1475,&\hbox{if
$k=3$,}\\\\[5.69054pt] 1-\frac{3}{k+1}-\frac{1}{(k+1)(k+2)},&\hbox{if $k$ is
even,}\\\\[5.69054pt] 1-\frac{3}{k+2}-\frac{1}{(k+2)^{2}},&\hbox{if $k\geq 5$
is odd,}\end{array}\right.$

then $G$ has a matching of size at least $\frac{n-r}{2}+1$.

Further, they found an explicit expression $\rho(k)$ in [45], and proved that
if $\lambda_{3}(G)<\rho(k)$, then $G$ has a matching of size
$\lfloor\frac{n}{2}\rfloor$. Other related results can be found in [126, 153].

In what follows, we shall consider the sufficient conditions on the existence
of perfect matching in terms of the number of edges. First of all, we define

$\boxed{R_{n}:=K_{1}\vee(K_{n-3}\cup I_{2}).}$

It is easy to verify that $R_{n}$ has no perfect matching and
$e(R_{n})={n-2\choose 2}+2$. In 2021, Suil O [152] proved that if an
$n$-vertex ($n\geq 10$) graph has more edges than $R_{n}$, then it has a
perfect matching. More precisely, they showed the following theorem even for
graphs with small order.

######  Theorem 5.6 (Suil O [152]).

Let $n\geq 10$ be an even integer or $n=4$. If $G$ is a connected graph of
order $n$ with $e(G)>\binom{n-2}{2}+2$. then $G$ has a perfect matching. For
$n=6$ or $n=8$, if $e(G)>9$ or $e(G)>18$, respectively, then $G$ has a perfect
matching.

We mention here that the extremal graphs in Theorem 5.6 can be characterized
easily. By a careful examination, we get show that if $e(G)\geq{n-2\choose
2}+2$, then $G$ has a perfect matching unless $n\geq 12$ and $G=R_{n}$, or
$n=6$ and $G\in\\{R_{6},K_{2}\vee I_{4},K_{2,4},K_{1}\vee(K_{1}\cup
K_{1,3})\\}$, or $n=8$ and $G\in\\{R_{8},K_{1}\vee K_{2,5},K_{2}\vee(K_{1}\cup
K_{1,4}),K_{2}\vee(K_{2}\cup K_{1,3}),K_{3}\vee I_{5}\\}$, or $n=10$ and
$G\in\\{R_{10},K_{4}\vee I_{6}\\}$. The proof is a standard case analysis, so
we omit the details. Moreover, Suil O [152] proved the following lower bound
for spectral radius in an $n$-vertex graph to guarantee the existence of a
perfect matching.

######  Theorem 5.7 (Suil O [152]).

Let $n$ be an even integer and $G$ be an $n$-vertex graph.
(1) If $n=4$ or $n\geq 8$ and $\lambda(G)>\lambda(R_{n})$, then $G$ has a
perfect matching.
(2) If $n=6$ and $\lambda(G)>\frac{1+\sqrt{33}}{2}$, then $G$ has a perfect
matching.

The condition is best possible since both $R_{n}$ and $K_{2}\vee I_{4}$ have
no perfect matching. Some calculations yield that $\lambda(K_{2}\vee
I_{4})=\frac{1+\sqrt{33}}{2}\approx 3.372$ and $\lambda(R_{6})\approx 3.177$.
Moreover, it is not hard to see that $\lambda(R_{n})$ is the largest root of

$x^{3}-(n-4)x^{2}-(n-1)x+2(n-4)=0.$

We here make a brief proof. Let $\bm{x}=(x_{1},\ldots,x_{n})$ be the
eigenvector corresponding to $\lambda=\lambda(R_{n})$. By the symmetry, we
know that the entries of eigenvector corresponding to the two vertices of
degree $1$ are equal, we may denote by $x_{1}=x_{2}=x$. Similarly, the entries
of eigenvector corresponding to the $n-3$ vertices with degree $n-3$ are
denoted by $x_{3}=\cdots=x_{n-1}=y$, and the entry of eigenvector
corresponding to the vertex with degree $n-1$ is denoted by $x_{n}=z$. The
eigen-equation $A\bm{x}=\lambda\bm{x}$ implies that

$\begin{cases}\lambda x=z,\\\ \lambda y=(n-4)y+z,\\\ \lambda
z=2x+(n-3)y.\end{cases}$

We can obtain that $x=\frac{1}{\lambda}z$ and $y=\frac{1}{\lambda-n+4}z$, and
thus

$\lambda^{3}-(n-4)\lambda^{2}-(n-1)\lambda+2(n-4)=0$

Next, we shall show that

$n-3<\lambda(R_{n})<\sqrt{(n-3)^{2}+1}.$

Since $K_{n-2}$ is a proper subgraph of $K_{1}\vee(K_{n-3}\cup I_{2})$, the
second inequality holds immediately. Let
$f(x)=x^{3}-(n-4)x^{2}-(n-1)x+2(n-4)$. We can compute the derivation
$f^{\prime}(x)=3x^{2}-2(n-4)x-(n-1)$, which has two distinct roots
$x_{1}=\frac{1}{3}(n-4-\sqrt{n^{2}-5n+13})$ and
$x_{2}=\frac{1}{3}(n-4+\sqrt{n^{2}-5n+13})$. Note that $f(x_{2})<0$. An easy
calculation reveals that $x_{2}<\sqrt{(n-3)^{2}+1}$ and
$f(\sqrt{(n-3)^{2}+1})>0$ for $n\geq 8$, hence $\sqrt{(n-3)^{2}+1}$ is greater
than the largest root of $f(x)$. By the above discussion, we know that the
largest root of $f(x)$ is approximately equal to $n-3$. Given a graph $G$, it
is not straightforward to verify the condition $\lambda(G)>\lambda(R_{n})$.
Hence, it is possible and meaningful to relax the condition to $\lambda(G)\geq
n-3$ and characterize more extremal graphs.

In 2020, Liu, Pan and Li [122] presented the result about the relationship
between the signless Laplacian spectral radius and prefect matching in graphs.
Recall that $R_{n}=K_{1}\vee(K_{n-3}\cup I_{2})$ and $R_{n}$ has no perfect
matching.

######  Theorem 5.8 (Liu–Pan–Li [122]).

Let $n$ be even and $G$ be an $n$-vertex connected graph.
(1) If $n=4$ or $n\geq 10$ and $q(G)>q(R_{n})$, then $G$ has a perfect
matching.
(2) If $n=6$ and $q(G)>4+2\sqrt{3}$, then $G$ has a perfect matching.
(3) If $n=8$ and $q(G)>6+2\sqrt{6}$, then $G$ has a perfect matching.

First of all, we can show that $q(R_{n})$ is the largest root of the equation

$x^{3}-(3n-7)x^{2}+n(2n-7)x-2(n^{2}-7n+12)=0.$

Moreover, we can see that $K_{2}\vee I_{4}$ and $K_{3}\vee I_{5}$ have no
perfect matching. By some calculations, we can get that $q(K_{2}\vee
I_{4})=4+2\sqrt{3}\approx 7.464$ and $q(R_{6})\approx 6.909$. For $n=8$, we
have $q(K_{3}\vee I_{5})=6+2\sqrt{6}\approx 10.899$ and $q(R_{8})\approx
10.513$.

###  5.3 Problem for graph deficiency

The deficiency of a graph $G$, denoted by def$(G)$, is the number of unmatched
vertices under a maximum matching in $G$. In particular, $G$ has a perfect
matching if and only if $\mathrm{def}(G)=0$. And $G$ has a nearly perfect
matching if and only if $\mathrm{def}(G)=1$.

Let $G=(V,E)$ be a simple graph on $n$ vertices and $\alpha^{\prime}(G)$
denote the number of edges in a maximum matching of $G$. To generalize the
result of Tutte [167], Berge [12] obtained the well-known Berge–Tutte formula.

######  Theorem 5.9 (Berge–Tutte).

Let $S\subseteq V$ be a set of vertices. We denote by $\mathrm{odd}(G-S)$ the
number of components with odd vertices in the induced subgraph $G-S$. Then

$\alpha^{\prime}(G)=\frac{1}{2}\bigl{(}n-\max_{S\subseteq
V}\\{\mathrm{odd}(G-S)-|S|\\}\bigr{)}.$

With the help of the Berge–Tutte formula, we can get

$\mathrm{def}(G)=\max_{S\subseteq V}\\{\mathrm{odd}(G-S)-|S|\\}.$

We say that $G$ is _$\beta$ -deficient_ if def$(G)\leq\beta$. In particular,
$G$ is $0$-deficient if and only if $G$ has a perfect matching. And $G$ is
$1$-deficient if and only if $G$ has a perfect matching or a nearly perfect
matching.

######  Theorem 5.10 (Bondy–Chvatal [23]).

Let $G$ be a simple graph on $n$ vertices. Then $G$ is $\beta$-deficient if
and only if the closure graph $\mathrm{cl}_{n-\beta-1}(G)$ is
$\beta$-deficient. In particular, if $d(u)+d(v)\geq n-\beta-1$ for all non-
edges $\\{u,v\\}$, then $\mathrm{cl}_{n-\beta-1}(G)=K_{n}$ and $G$ is
$\beta$-deficient.

######  Lemma 5.11.

[8, 108] Let $G$ be a connected graph on $n$ vertices with degree sequence
$d_{1}\leq d_{2}\leq\cdots\leq d_{n}$. Suppose $0\leq\beta\leq n$ and
$n\equiv\beta\ ({\rm mod\,}2)$. If $G$ is not $\beta$-deficient, then there
exists $1\leq i\leq\frac{n+\beta-2}{2}$ such that $d_{i+1}\leq i-\beta$ and
$d_{n+\beta-i}\leq n-i-2$.

######  Lemma 5.12 (Feng et al. [70]).

Let $G$ be a graph of order $n\geq 11$. Let $0\leq\beta\leq n$ with
$n\equiv\beta\ (\textup{mod}\ 2)$. If
$e(G)\geq\frac{1}{2}(n^{2}-5n-4\beta+10)$, then $G$ is $\beta$-deficient,
unless $\beta=0$ and $G=K_{1}\vee(I_{2}\cup K_{n-3})$, or $\beta=1$ and
$G=I_{2}\cup K_{n-2}$.

For every integers $\beta\geq 0$ and $\delta\geq 1$, we denote

$\boxed{R_{n,\delta,\beta}:=K_{\delta}\vee(K_{n-2\delta-\beta-1}\cup{I_{\delta+\beta+1}}).}$

It is easy to see that $R_{n,\delta,\beta}$ is a graph with minimum degree
$\delta$ and deficiency $\beta+1$, so it is not $\beta$-deficient.
Furthermore, we can easily prove the following theorem.

######  Theorem 5.13.

For every $\beta\geq 0$ and $\delta\geq 1$, there exists an
$n_{0}(\delta,\beta)$ such that for every $n\geq n_{0}(\delta,\beta)$ with
$n\equiv\beta({\rm mod\,}2)$, if $G$ is an $n$-vertex connected graph with
minimum degree $\delta(G)\geq\delta$ and

$e(G)\geq e(R_{n,\delta,\beta}),$

then $G$ is $\beta$-deficient unless $G=R_{n,\delta,\beta}$.

In 2018, Liu et al. [123] proved the following spectral extremal problem for
$\beta$-deficient.

######  Theorem 5.14 (Liu et al. [123]).

Let $\beta\geq 0$ and $\delta\geq 1$ and $n\equiv\beta({\rm mod\,}2)$ with
$n\geq\widetilde{n_{0}}(\delta,\beta)$ where

$\widetilde{n_{0}}(\delta,\beta)=\max\\{\delta^{3}\\!+\\!\delta^{2}(\beta\\!+\\!1)\\!+\\!\delta\\!+\\!\beta\\!+\\!6,2\delta^{2}\\!+\\!2\delta\beta\\!+\\!7\delta\\!+\\!3\beta\\!+\\!7,(\delta\\!+\\!\beta\\!+\\!2)(\delta\\!+\\!1)\delta\\}.$

If $G$ is an $n$-vertex connected graph with minimum degree
$\delta(G)\geq\delta$ and

$\lambda(G)\geq n-\delta-\beta-2,$

then $G$ is $\beta$-deficient unless $G=R_{n,\delta,\beta}$.

######  Corollary 5.15 (Liu et al. [123]).

Let $\beta\geq 0$ and $\delta\geq 1$ and $n\equiv\beta({\rm mod\,}2)$ with
$n\geq{n_{0}}(\delta,\beta)$ where

$n_{0}(\delta,\beta):=\max\\{7+7\delta+2\delta^{2}+2\delta\beta+3\beta,(\delta+\beta+2)(\delta+1)\delta\\}.$

If $G$ is an $n$-vertex connected graph with minimum degree
$\delta(G)\geq\delta$ and

$\lambda(G)\geq\lambda(R_{n,\delta,\beta}),$

then $G$ is $\beta$-deficient unless $G=R_{n,\delta,\beta}$.

For some special cases, one can relax the bound on order of graphs. For
example, when $\delta=1$ and $\beta=0$, i.e., the existence of perfect
matching, the desired result holds for all $n\geq 8$; see the previous Theorem
5.7.

Furthermore, Liu et al. [124] obtained a tight $Q$-spectral condition for a
graph to be $\beta$-deficient. In order to state their main result, we need to
fix some notation. Recall that
${R}_{n,\delta,\beta}=K_{\delta}\vee(K_{n-2\delta-\beta-1}\cup{I_{\delta+\beta+1}})$.
In the graph ${R}_{n,\delta,\beta}$, we denote by $X=\\{v\in
V({R}_{n,\delta,\beta}):d(v)=\delta\\},Y=\\{v\in
V({R}_{n,\delta,\beta}):d(v)=n-1\\}$ and $Z=\\{v\in
V({R}_{n,\delta,\beta}):d(v)=n-\beta-\delta-2\\}$. Let
$E_{1}({R}_{n,\delta,\beta})$ denote the set of edges of
${R}_{n,\delta,\beta}$ whose endpoints are both in $Y\cup Z.$ We further
define the following family of graphs.

$\displaystyle\mathcal{R}^{(1)}_{n,\delta,\beta}=\left\\{{R}_{n,\delta,\beta}\setminus
E^{\prime}:\text{$E^{\prime}\subseteq E_{1}({R}_{n,\delta,\beta})$ with
$|E^{\prime}|\leq\left\lfloor{(\delta+\beta+1)\delta}/{4}\right\rfloor$}\right\\}.$

Here, we denote by $R_{n,\delta,\beta}\setminus E^{\prime}$ the graph obtained
from $R_{n,\delta,\beta}$ by deleting all edges of the edge set $E^{\prime}$.
As a $Q$-spectral counterpart, we obtain the following analogue of signless
Laplacian spectral radius.

######  Theorem 5.16 (Liu et al. [124]).

Let $\beta\geq 0$ and $\delta\geq 1$ and $n\equiv\beta({\rm mod\,}2)$ with
$n\geq{n_{1}}(\delta,\beta)$ where

$n_{1}(\delta,\beta)=\delta^{4}+(2\beta+7)\delta^{3}+(\beta^{2}+11\beta+15)\delta^{2}+(4\beta^{2}+13\beta+20)\delta+10\beta+21.$

If $G$ is a connected graph on $n$ vertices with the minimum degree
$\delta(G)\geq\delta$ and

$q(G)\geq 2(n-\delta-\beta-2),$

then either $G$ is $\beta$-deficient or
$G\in\mathcal{R}^{(1)}_{n,\delta,\beta}$.

######  Corollary 5.17.

Let $\beta\geq 0$ and $\delta\geq 1$ and $n\equiv\beta({\rm mod\,}2)$ with
$n\geq{n_{1}}(\delta,\beta)$. If $G$ is an $n$-vertex connected graph with
minimum degree $\delta(G)\geq\delta$ and

$q(G)\geq q(R_{n,\delta,\beta}),$

then $G$ is $\beta$-deficient unless $G=R_{n,\delta,\beta}$.

For some special cases, one can relax the bound on order of graphs. For
example, when $\delta=1$ and $\beta=0$, i.e., the existence of perfect
matching, the desired result holds for all $n\geq 10$; see the previous
Theorem 5.8.

## Acknowledgements

The first author is now a doctoral student (2019–2023) under the guidance of
Prof. Yuejian Peng (Hunan University). He would like to thank Prof. Peng who
provided many constructive suggestions for his academic study. Thanks also go
to Dr. Xiaocong He and Dr. Peng-Li Zhang for reading an earlier draft of the
paper. Last but not least, the authors would like to thank anonymous reviewers
and editors for their valuable comments and suggestions to improve the
presentation of this paper. This work was supported by NSFC (Grant No.
11871479, 12071484 and 11931002), Hunan Provincial Natural Science Foundation
(Grant No. 2020JJ4675 and 2018JJ2479) and Mathematics and Interdisciplinary
Sciences Project of CSU.

## References

  * [1] Abreu N.D., Nikiforov V., Maxima of the $Q$-index: abstract graph properties, Electronic J. Linear Algebra, 2012, 23: 782–789.
  * [2] Abreu N.D., Nikiforov V., Maxima of the $Q$-index: Graphs with bounded clique number, Electronic J. Linear Algebra, 2013, 26: 121–130.
  * [3] Aigner M., Ziegler G.M., Proofs from THE BOOK, 5th edition, Springer-Verlag, New-York, 2014.
  * [4] Akiyama J., Frankl P., On the size of graphs with complete factors, J. Graph Theory, 1985, 9: 197–201.
  * [5] Alon N., Rónyai L., Szabó T., Norm-graphs: variations and applications, J. Combin. Theory Ser. B, 1999, 76: 280–290.
  * [6] Alon N., Krivelevich M., Sudakov B., Turán numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput., 2003, 12: 477–494.
  * [7] Babai L., Guiduli B., Spectral extrema for graphs: the Zarankiewicz problem, Electronic J. Combin., 2009, 16: #R123.
  * [8] Bauer D., Broersma H.J., Heuvel J.V., Kahl N., Nevo A., Schmeichel E., Woodall D.R., Yatauro M., Best monotone degree conditions for graph properties: a survey, Graphs Combin., 2015, 31: 1–22.
  * [9] Bauer D., Hakimi S.L., Kahl N., Schmeichel E., Sufficient degree conditions for $k$-edge-connectedness of a graph, Networks, 2009, 54: 95–98.
  * [10] Benediktovich V.I., Spectral condition for Hamiltonicity of a graph, Linear Algebra Appl., 2016, 494: 70–79.
  * [11] Berman A., Zhang X.-D., On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B, 2001, 83: 233–240.
  * [12] Berge C., Sur le couplage maximum d’un graphe, C.R. Acad. Sci. Paris, 1958, 247: 258–259.
  * [13] Berge C., Graphs and hypergraphs, Minieka E, translator. 2nd, Vol. 6, North-Holland Mathematical Library, American Elsevier Publishing Co., Inc., 1976.
  * [14] Blagojević P.V.M., Bukh B., Karasev R., Turán numbers for $K_{s,t}$-free graphs: topological obstructions and algebraic constructions, Israel J. Math., 2013, 197: 199–214.
  * [15] Bollobás B., Extremal Graph Theory, Academic Press, New York, 1978.
  * [16] Bollobás B., Nikiforov V., Books in graphs, European J. Combin., 2005, 26: 259–270.
  * [17] Bollobás B., Nikiforov V., Cliques and the spectral radius, J. Combin. Theory Ser. B, 2007, 97: 859–865.
  * [18] Bollobás B., Nikiforov V., Joints in graphs, Discrete Math., 2008, 308: 9–19.
  * [19] Bollobás B., Nikiforov V., Large joints in graphs. European J. Combin., 2011, 32: 33–44.
  * [20] Bondy J.A., Properties of graphs with constraints on degrees, Studia. Sci. Math. Hungar., 1969, 4: 473–475.
  * [21] Bondy J.A., Large cycles in graphs, Discrete Math., 1971, 1: 121–132.
  * [22] Bondy J.A., Variations on the Hamiltonian theme, Canad. Math. Bull., 1972, 15: 57–62.
  * [23] Bondy J.A., Chvátal V., A method in graph theory, Discrete Math., 1976, 15: 111–135.
  * [24] Bondy J.A., Murty U.S.R., Graph Theory with Applications, North-Holland, Amsterdam, 1976.
  * [25] Bondy J.A., Murty U.S.R., Graph theory, GTM 244, New York, Springer, 2008.
  * [26] Bondy J.A., Simonovits M., Cycles or even length in graphs, J. Combin. Theory Ser. B, 1974, 16: 97–105.
  * [27] Brouwer A., Haemers W., Eigenvalues and perfect matchings, Linear Algebra Appl., 2005, 395: 155–162.
  * [28] Brown W.G., On graphs that do not contain a Thomsen graph, Canad. Math. Bull., 1966, 9: 281–285.
  * [29] Brualdi R.A., Solheid E.S., On the spectral radius of complementary acyclic matrices of zeros and ones, SIAM J. Algebra. Discrete Method, 1986, 7: 265–272.
  * [30] Bukh B., Random algebraic construction of extremal graphs, Bull. Lond. Math. Soc., 2015, 47: 939–945.
  * [31] Bukh B., Jiang Z.L., A bound on the number of edges in graphs without an even cycle, Combin. Probab. Comput., 2017, 26(1): 1–15. Final correct version, arXiv: 1403.1601v3.
  * [32] Bukh B., Extremal graphs without exponentially-small bicliques, 16 pages, 2021, arXiv:2107.04167.
  * [33] Cai G.X., Fan Y.Z., The signless Laplacian spectral radius of graphs with given chromatic number, Math. Appl. (Wuhan), 2009, 22: 161–167.
  * [34] Chartrand G., Kapoor S.F., Lick D.R., $n$-Hamiltonian graphs, J. Combinatorial Theory, 1970, 9: 308–312.
  * [35] Chen G.T., Gould R.J., Pfender F., Wei B., Extremal graphs for intersecting cliques, J. Combin. Theory. Ser. B, 2003, 89: 159–171.
  * [36] Chen X.D., Hou Y.P., Qian J.G., Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius, Linear Multilinear Algebra, 2018, 66: 919–936.
  * [37] Chen M.-Z., Zhang X.-D., The number of edges, spectral radius and hamilton-connectedness of graphs, J. Comb. Optim., 2018, 35: 1104–1127.
  * [38] Chen M.-Z., Liu A.-M., Zhang X.-D., The signless Laplacian spectral radius of graphs without intersecting odd cycles, 11 pages, 9 August, 2021, arXiv:2108.03895.
  * [39] Cheng T., Feng L.H., Li Y.T., Liu W.J., A tight $Q$-index condition for a graph to be $k$-path-coverable involving minimum degree, 13 pages, 2020, arXiv:2109.07347.
  * [40] Chvátal V., On Hamilton’s ideals, J. Combin. Theory Ser. B, 1972, 12: 163–168.
  * [41] Cioabă S.M., Eigenvalues and edge-connectivity of regular graphs, Linear Algebra Appl., 2010, 432: 458–470.
  * [42] Cioabă S.M., Feng L.H., Tait M., Zhang X.-D., The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Combin., 2020, 27: P4.22.
  * [43] Cioabă S.M., Desai D.N., Tait M., The spectral radius of graphs with no odd wheels, 19 pages, 15 April, 2021, arXiv: 2104.07729.
  * [44] Cioabă S.M., Gregory D., Large matchings from eigenvalues, Linear Algebra Appl., 2007, 422: 308–317.
  * [45] Cioabă S.M., Gregory D., Haemers W., Matchings in regular graphs from eigenvalues, J. Combin. Theory Ser. B, 2009, 99: 287–297.
  * [46] Cioabă S.M., Gu X., Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs, Czech. Math. Journal, 2016, 141: 913–924.
  * [47] Conlon D., Fox J., Graph removal lemmas, in Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., vol. 409, Cambridge Univ. Press, Cambridge, 2013, pp. 1–49.
  * [48] Conlon D., Lee J., On the extremal number of subdivisions, Int. Math. Res. Not. IMRN 2021, 12: 9122–9145.
  * [49] Conlon D., Janzer O., Lee J., More on the extremal number of subdivisions, Combinatorica, 2020, in press.
  * [50] Desai D.N., Kang L., Li Y., Ni Z., Tait M., Wang J., Spectral extremal graphs for intersecting cliques, 18 pages, 2021, arXiv:2108.03587v2.
  * [51] Duan X.Z., Ning B., Peng X., Wang J., Yang W.H., Maximizing the number of cliques in graphs with given matching number, Discrete Appl. Math., 2020, 287: 110–117.
  * [52] Diestel R., Graph theory, Fifth edition, GTM, 173, Springer, Berlin, 2017.
  * [53] Dirac D.A., Some theorems on abstract graphs, Proc. London Math. Soc., 1952, 2: 69–81.
  * [54] Dzido T., A note on Turán numbers for even wheels, Graphs and Combinatorics, 2013, 29: 1305–1309.
  * [55] Edwards C.S., A lower bound for the largest number of triangles with a common edge, 1977 (unpublished manuscript).
  * [56] Erdős P., Stone A.H., On the structure of linear graphs, Bull. Amer. Math. Soc., 1946, 52: 1087–1091.
  * [57] Erdős P., Gallai T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar., 1959, 10: 337–356.
  * [58] Erdős P., Remarks on a paper of Pósa, Magyar Tud. Akad. Mat. Kut. Int. Közl, 1962, 7: 227–229.
  * [59] Erdős P., On the number of complete subgraphs contained in certain graphs, Magy. Tud. Akad. Mat. Kut. Intéz. Közl., 1962, 7: 459–474.
  * [60] Erdős P., On extremal problems of graphs and generalized graphs, Israel J. Math., 1964, 2: 183–190.
  * [61] Erdős P., Rényi A., Sós V. T., On a problem of graph theory, Studia Sci. Math. Hungar., 1966, 1: 215–235.
  * [62] Erdős P., Simonovits M., A limit theorem in graph theory, Stud. Sci. Math. Hungar., 1966, 1: 51–57.
  * [63] Erdős P., Frankl P., Rödl V., The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin., 1986, 2: 113–121.
  * [64] Erdős P., Füredi Z., Gould R.J., Gunderson D.S., Extremal Graphs for Intersecting Triangles, J. Combin. Theory. Ser. B, 1995, 64: 89–100.
  * [65] Favaron O., Mahéo M., Saclé J.F., Some eigenvalue properties in graphs (conjectures of Graffiti II), Discrete Math., 1993, 111: 197–220.
  * [66] Feng L.H., Yu G.H., Zhang X.-D., Spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (2007), no. 1, 133–138.
  * [67] Feng L.H., Li Q., Zhang X.-D., Spectral radii of graphs with given chromatic number, Appl. Math. Lett., 2007, 20: 158–162.
  * [68] Feng L.H., Yu G.H., On three conjectures involving the signless Laplacian spectral radius of graphs. Publ. Inst. Math., 2009, 85: 35–38.
  * [69] Feng L.H., Cao J.X., Liu W.J., Ding S.F., Liu H., The spectral radius of edge chromatic critical graphs, Linear Algebra Appl., 2016, 492: 78–88.
  * [70] Feng L.H., Zhang P.L., Liu H., Liu W.J., Liu M.M., Hu Y.Q., Spectral conditions for some graphical properties, Linear Algebra Appl., 2017, 524: 182–198.
  * [71] Feng L.H., Zhang P.L., Liu W.J., Spectral radius and $k$-connectedness of graphs, Monatsh. Math., 2018, 185: 651–661.
  * [72] Fiedler M., Algebraic connectivity of graphs, Czech. Math. J., 1973, 23: 298–305.
  * [73] Fiedler M., Nikiforov V., Spectral radius and Hamiltonicity of graphs, Linear Algebra Appl., 2010, 432: 2170–2173.
  * [74] Fox J., A new proof of the graph removal lemma, Ann. of Math., 2011, 174: 561–579.
  * [75] Füredi Z., On a Turán type problem of Erdős, Combinatorica, 1991, 11: 75–79.
  * [76] Füredi Z., An upper bound on Zarankiewicz’s problem, Comb. Probab. Comput., 1996, 5: 29–33.
  * [77] Füredi Z., New asympotics for bipartite Turán numbers, J. Combin. Theory, Ser. A, 1996, 75: 141–144.
  * [78] Füredi Z., On the number of edges of quadrilateral-free graphs, J. Combin. Theory Ser. B, 1996, 68: 1–6.
  * [79] Füredi Z., Naor A., Verstraëte J., On the Turán number for the hexagon, Adv. Math., 2006, 203: 476–496.
  * [80] Füredi Z., Simonovits M., The history of degenerate (bipartite) extremal graph problems, Erdős centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013, pp. 169–264.
  * [81] Füredi Z., Kostochka A., Luo R., A stability version for a theorem of Erdős on nonhamiltonian graphs, Discrete Math., 2017, 340: 2688–2690.
  * [82] Freitas M.A.A., Nikiforov V., Patuzzi L., Maxima of the $Q$-index: forbidden 4-cycle and 5-cycle, Electron. J. Linear Algebra, 2013, 26: 905–916.
  * [83] Ge J., Ning B., Spectral radius and Hamiltonian properties of graphs II, Linear Multilinear Algebra, 2020, 68: 2298–2315.
  * [84] Gu X.F., Lai H.-J., Li P., Yao S.M., Edge-disjoint spanning trees, edge connectivity and eigenvalues in graphs, J. Graph Theory, 2016, 81: 16–29.
  * [85] Guiduli B.D., Spectral extrema for graphs, Thesis (Ph.D.)– The University of Chicago, 1996.
  * [86] Gao J., Hou X.M., The spectral radius of graphs without long cycles, Linear Algebra Appl., 2019, 566: 17–33.
  * [87] Hansen P., Stevanović D., On bags and bugs, Discrete Appl. Math., 2008, 156: 986–997.
  * [88] He B., Jin Y.-L., Zhang X.-D., Sharp bounds for the signless Laplacian spectral radius in terms of clique number, Linear Algebra Appl., 2013, 438: 3851–3861.
  * [89] He Z.Y., A new upper bound on the Turán number of even cycles, Electron. J. Combin., 2021, 28: # P2.41.
  * [90] Horn R.A., Johnson C.R., Matrix Analysis, 2nd edition, Cambridge University Press, Cambridge, 2013.
  * [91] Hong Y., A bound on the spectral radius of graphs, Linear Algebra Appl., 1988, 108: 135–139.
  * [92] Hong Y., Shu J.-L, Fang K.F., A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser. B, 2001, 81: 177–183.
  * [93] Hou X.M., Qiu Y., Liu B.Y., Extremal graph for intersecting odd cycles, Electron. J. Combin., 2016, 23: P2.29.
  * [94] Hou X.M., Qiu Y., Liu B.Y., Turán number and decomposition number of intersecting odd cycles, Discrete Math., 2018, 341: 126–137.
  * [95] Jiang G.-S., Yu G.-D., Fang Y., Spectral conditions and Hamiltonicity of a balanced bipartite graph with large minimum degree, Appl. Math. Comput., 2019, 356: 137–143.
  * [96] Kang L.Y., Nikiforov V., Extremal problem for the $p$-spectral radius of graphs, Electronic J. Combin., 2014, 21: 87–101.
  * [97] Kang L.Y., Nikiforov V., Yuan X.Y., The $p$-spectral radius of $k$-partite and $k$-chromatic uniform hypergraphs, Linear Algebra Appl., 2015, 478: 81–107.
  * [98] Keevash P., Hypergraph Turán problems, Surveys in combinatorics, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011, pp. 83–139.
  * [99] Keevash P., Lenz J., Mubayi D., Spectral extremal problems for hypergraphs, SIAM J. Discrete Math., 2014, 28:1838–1854.
  * [100] Khadžiivanov N., Nikiforov V., Solution of a problem of P. Erdős about the maximum number of triangles with a common edge in a graph, C. R. Acad. Bulgare Sci., 1979, 32: 1315–1318 (in Russian).
  * [101] Kővári T., Sós V.T., Turán P., On a problem of K. Zarankiewicz, Colloq. Math., 1954, 3: 50–57.
  * [102] Kollár J., Rónyai L., Szabó T., Norm-graphs and bipartite Turán numbers, Combinatorica, 1996, 16: 399–406.
  * [103] Krivelevich M., Sudakov B., Vu V., Wormald N., Random regular graphs of high degree, Random Structures and Algorithms, 2001, 18: 346–363.
  * [104] Krivelevich M., Sudakov B., Sparse pseudo-random graphs are Hamiltonian, J. Graph Theory, 2003, 42: 17–33.
  * [105] Krivelevich M., Sudakov B., Pseudo-random graphs, in More Sets, Graphs and Numbers, in: Bolyai Soc. Math. Stud., vol.15, 2006, pp.199–262.
  * [106] Kronk H.V., Generalization of a theorem of Pósa, Proc. Amer. Math. Soc., 1969, 21: 77–78.
  * [107] Kronk H.V., A note on $k$-path Hamiltonian graphs, J. Combin. Theory,1969, 7: 104–106.
  * [108] Las Vergnas M., Problèmes de Couplages et Problèmes Hamiltoniens en Théorie des Graphes, PhD Thesis, Université Paris VI–Pierre et Marie Curie, 1972.
  * [109] Lazebnik F., Ustimenko V. A., Woldar A. J., Polarities and $2k$-cycle-free graphs, Discrete Math., 1999, 197/198: 503–513.
  * [110] Lesniak L., On $n$-Hamiltonian graphs, Discrete Math.,1976, 14: 165–169.
  * [111] Li B.L., Ning B., Spectral analogues of Erdős’ and Moon–Moser’s theorems on Hamilton cycles, Linear Multilinear Algebra, 2016, 64: 2252–2269.
  * [112] Li B.L., Ning B., Spectral analogues of Moon–Moser’s theorem on Hamilton paths in bipartite graphs, Linear Algebra Appl., 2017, 515: 180–195.
  * [113] Li B.L., Ning B., The stability method, eigenvalues and cycles of consecutive lengths, arXiv:2102.03855v1.
  * [114] Li Y.W., Liu Y., Peng X., Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree, Linear Multilinear Algebra, 2018, 66: 2011–2023.
  * [115] Li Y.T., Peng Y.J., The spectral radius of graphs with no intersecting odd cycles, Discrete Math., in press, 22 pages, 2021, arXiv:2106.00587.
  * [116] Li Y.T., Peng Y.J., Sufficient spectral conditions for graphs being $k$-edge-Hamiltonian or $k$-Hamiltonian, 19 pages, 2021, arXiv:2109.01973.
  * [117] Li H., Generalizations of Dirac’s theorem in Hamiltonian graph theory–A survey, Discrete Math., 2013 313: 2034–2053.
  * [118] Li J., Li X.L., Shi Y.T., On the maximal energy tree with two maximum degree vertices, Linear Algebra Appl., 2011, 435: 2272–2284.
  * [119] Li J.P., Steiner G., Partitioning a graph into vertex-disjoint paths, Studia Sci. Math. Hungar., 2005, 42: 277–294.
  * [120] Li R., Spectral conditions for some stable properties of graphs, J. Combin. Math. Combin. Comput.,2014, 88:199–205.
  * [121] Lin H.Q., Ning B., Wu B., Eigenvalues and triangles in graphs, Combin. Probab. Comput., 2021, 30: 258–270.
  * [122] Liu C., Pan Y.G., Li J.P., Signless Laplacian spectral radius and matching in graphs, 2020, arXiv:2007.04479v1.
  * [123] Liu W.J., Liu M.M., Feng L.H., Spectral conditions for graphs to be $\beta$-deficient involving minimum degree, Linear Multilinear Algebra, 2018, 66: 792–802.
  * [124] Liu W.J., Huang Z., Li Y.T., Feng L.H., A sufficient Q-spectral condition for a graph to be $\beta$-deficient involving minimum degree, Discrete Appl. Math., 2019, 265: 158–167.
  * [125] Liu W.J., Liu M.M., Zhang P.L., Feng L.H., Spectral conditions for graphs to be $k$-Hamiltonian or $k$-path-coverable, Discuss. Math. Graph Theory, 2020, 40: 161–179.
  * [126] Liu H.Q., Lu M., Tian F., Edge-connectivity and (signless) Laplacian eigenvalue of graphs, Linear Algebra Appl., 2013, 439: 3777–3784.
  * [127] Liu M.H., Lai H.-J., Das K.Ch., Spectral results on Hamiltonian problem, Discrete Math., 2019, 342: 1718–1730.
  * [128] Liu M.H., Wu Y., Lai H.-J., Unified spectral Hamiltonian results of balanced bipartite graphs and complementary graphs, Graphs and Combinatorics, 2020, 36: 1363–1390.
  * [129] Liu R.F., Shiu W.C., Xue J., Sufficient spectral conditions on Hamiltonian and traceable graphs, Linear Algebra Appl., 2015, 467: 254–266.
  * [130] Lu M., Liu H.Q., Tian F., Spectral radius and Hamiltonian graphs, Linear Algebra Appl., 2012, 437: 1670–1674.
  * [131] Lu Y., Some generalizations of spectral conditions for 2s-hamiltonicity and 2s-traceability of bipartite graphs, Linear Multilinear Algebra, 2020, https://doi.org/10.1080/03081087.2020.1778621
  * [132] Mantel W., Problem 28, Wiskundige Opgaven, 1907, 10: 60–61.
  * [133] Mokzkin T.S., Straus E.G., Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., 1965, 17: 533–540.
  * [134] Moon J., Moser L., On Hamiltonian bipartite graphs, Israel J. Math., 1963, 1: 163–165.
  * [135] Nikiforov V., Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput., 2002, 11: 179–189.
  * [136] Nikiforov V., Walks and the spectral radius of graphs, Linear Algebra Appl., 2006, 418: 257–268.
  * [137] Nikiforov V., Bounds on graph eigenvalues I, Linear Algebra Appl., 2007, 420: 667–671.
  * [138] Nikiforov V., Bounds on graph eigenvalues II, Linear Algebra Appl., 2007, 427: 183–189.
  * [139] Nikiforov V., A spectral condition for odd cycles in graphs, Linear Algebra Appl., 2008, 428: 1492–1498.
  * [140] Nikiforov V., Graphs with many $r$-cliques have large complete $r$-partite subgraphs, Bull. Lond. Math. Soc., 2008, 40: 23–25.
  * [141] Nikiforov V., More spectral bounds on the clique and independence numbers, J. Combin. Theory Ser. B, 2009, 99: 819–826.
  * [142] Nikiforov V., A spectral Erdős–Stone–Bollobás theorem, Combin. Probab. Comput., 2009, 18: 455–458.
  * [143] Nikiforov V., The maximum spectral radius of $C_{4}$-free graphs of given order and size, Linear Algebra Appl., 2009, 430: 2898–2905.
  * [144] Nikiforov V., Spectral saturation: inverting the spectral Turán theorem. Electron. J. Combin., 2009, 16, no. 1, R 33.
  * [145] Nikiforov V., A contribution to the Zarankiewicz problem, Linear Algebra Appl., 2010, 432: 1405–1411.
  * [146] Nikiforov V., The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl., 2010, 432: 2243–2256.
  * [147] Nikiforov V., Some new results in extremal graph theory, in Surveys in Combinatorics, Cambridge University Press, 2011, pp. 141–181.
  * [148] Nikiforov V., Yuan X., Maxima of the $Q$-index: Forbidden even cycles, Linear Algebra Appl., 2015, 471: 636–653.
  * [149] Nikiforov V., Spectral radius and Hamiltonicity of graphs with large minimum degree, Czech. Math. Journal, 2016, 141: 925–940.
  * [150] Ning B., Ge J., Spectral radius and Hamiltonian properties of graphs, Linear Multilinear Algebra, 2015, 63: 1520–1530.
  * [151] Ning B., Peng X., Extension of Erdős–Gallai Theorem and Luo’s Theorem with applications, Combin. Probab. Comput., 2020, 29: 128–136.
  * [152] O S., Spectral radius and matchings in graphs, Linear Algebra Appl., 2021, 614: 316–324.
  * [153] O S., Cioabă S.M., Edge-connectivity, eigenvalues, and matchings in regular graphs, SIAM J. Discrete Math., 2010, 24: 1470–1481.
  * [154] Oboudi M.R., A relation between the signless Laplacian spectral radius of complete multipartite graphs and majorization, Linear Algebra Appl., 2019, 565: 225–238.
  * [155] Ore O., Note on Hamilton circuits, Amer. Math. Monthly, 1960, 67: 55.
  * [156] Ore O., Hamiltonian connected graphs, J. Math. Pures Appl., 1963, 42: 21–27.
  * [157] Pikhurko O., A note on the Turán function of even cycles, Proc. Amer. Math. Soc., 2012, 140: 3687–3692.
  * [158] Shapira, Extremal graph theory, 2016, http://www.math.tau.ac.il/~asafico/ext-graph-theory/notes.pdf
  * [159] Simonovits M., A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, Proc. Colloq., Tihany, Academic Press, New York, 1968, pp. 279–319.
  * [160] Simonovits M., Paul Erdős’ influence on Extremal graph theory, in The Mathematics of Paul Erdős II, R.L. Graham, Springer, New York, 2013, pp. 245–311.
  * [161] Steiner G., On the $k$-path partition of graphs, Theoretical Computer Science, 2003, 290: 2147–2155.
  * [162] Stevanović D., Spectral Radius of Graphs, Academic Press, Amsterdam, 2015.
  * [163] Stevanović D., Aouchiche M., Hansen P., On the spectral radius of graphs with a given domination number, Linear Algebra Appl., 2008, 428: 1854–1864.
  * [164] Tang Q.S., Peng Y.J., Zhang X.D., Zhao C., Some results on Lagrangians of hypergraphs, Discrete Appl. Math., 2014, 166: 222–238.
  * [165] Tang Q.S., Peng Y.J., Zhang X.D., Zhao C., Connection between the clique number and the Lagrangian of 3-uniform hypergraphs, Optim. Lett., 2016, 10: 685–697.
  * [166] Turán P., Research problem, Közl MTA Mat. Kutató Int., 1961, 6: 417–423.
  * [167] Tutte W.T., The factorization of linear graphs, J. Lond. Math. Soc., 1947, 22: 107–111.
  * [168] Verstraëte J., On arithmetic progressions of cycle lengths in graphs, Combin. Probab. Comput., 2000, 9: 369–373.
  * [169] Wei J., You Z.F., Lai H.-J., Spectral analogues of Erdős’ theorem on Hamilton-connected graphs, Appl. Math. Comput., 2019, 340: 242–250.
  * [170] Wei J., You Z.F., Spectral radius and traceability of graphs with large minimum degree, Linear Multilinear Algebra, 2020, 68: 161–176.
  * [171] Wilf H., Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B, 1986, 40: 113–117.
  * [172] Woodall D.R., Sufficient conditions for circuits in graphs, Proc. London Math. Soc., 1972, 24: 739–755.
  * [173] Wu Q.F., Zhang P.L., Feng L.H., Connectivity and spectral radius of graphs, Ars Combin., 2019, 142: 197–206.
  * [174] West D.B., Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
  * [175] Wang J., The shifting method and generalized Turán number of matchings, European J. Combin., 2020, 85: ID 103057.
  * [176] Xu Y., Zhai M.Q., Wang B., An improvement of spectral conditions for Hamilton-connected graphs, Linear Multilinear Algebra, 2021, https://doi.org/10.1080/03081087.2021.1946465.
  * [177] Yu G.D., Fan Y.Z., Spectral conditions for a graph to be Hamilton-connected, Applied Mechanics and Materials, 2013, 336: 2329–2334.
  * [178] Yu G.D., Ye M.L., Cai G.X., Cao J.D., Signless Laplacian spectral conditions for Hamiltonicity of graphs, J. Appl. Math., 2014, Article ID 282053.
  * [179] Yu G.-L., Wu Y.-R., Shu J.-L., Signless Laplacian spectral radii of graphs with given chromatic number, Linear Algebra Appl., 2011, 435: 1813–1822.
  * [180] Yu G.H., On the maximal signless Laplacian spectral radius of graphs with given matching number, Proc. Japan Acad. Ser. A Math. Sci., 2008, 84: 163–166.
  * [181] Yuan L.-T., Extremal graphs for the $k$-flower, J. Graph Theory, 2018, 89: 26–39.
  * [182] Yuan L.-T., Extremal graphs for odd wheels, 2021, arXiv:2001.02628v2.
  * [183] Yuan X.Y., Maxima of the $Q$-index: Forbidden odd cycles, Linear Algebra Appl., 2014, 458: 207–216.
  * [184] Yuan W.L., Wang B., Zhai M.Q., On the spectral radii of graphs without given cycles, Electron. J. Linear Algebra, 2012, 23: 599–606.
  * [185] Zhai M.Q., Wang B., Proof of a conjecture on the spectral radius of $C_{4}$-free graphs, Linear Algebra Appl., 2012, 430: 1641–1647.
  * [186] Zhai M.Q., Lin H.Q., Spectral extrema of graphs: forbidden hexagon, Discrete Math., 2020, 343: ID 112028.
  * [187] Zhai M.Q., Lin H.Q., Shu J.L., Spectral extrema of graphs with fixed size: Cycles and complete bipartite graphs, European J. Combin., 2021, 95: ID 103322.
  * [188] Zhai M.Q., Lin H.Q., A strengthening of the spectral color critical edge theorem: books and theta graphs, 2021, arXiv: 2102.04041v2.
  * [189] Zhang M.J., Li S.C., Extremal Halin graphs with respect to the signless Laplacian spectra, Discrete Appl. Math., 2016, 213: 207–218.
  * [190] Zhang M.J., Li S.C., Extremal cacti of given matching number with respect to the distance spectral radius, Appl. Math. Comput., 2016, 291: 89–97.
  * [191] Zhang P.L., Feng L.H., Liu W.J., Zhang X.-D., The $Q$-index and connectivity of graphs, 11 pages, 2020, arXiv:2109.07656.
  * [192] Zhang X.-D., The signless Laplacian spectral radius of graphs with given degree sequence, Discrete Appl. Math., 2009, 157: 2928–2937.
  * [193] Zhao Y.F., Graph Theory and Additive Combinatorics, notes for MIT 18.217, Fall 2019, https://yufeizhao.com/gtac/gtac.pdf
  * [194] Zhao Y.H., Huang X.Y., Guo H.T., The signless Laplacian spectral radius of graphs with no intersecting triangles, Linear Algebra Appl., 2021, 618: 12–21.
  * [195] Zhou B., Signless Laplacian spectral radius and Hamiltonicity, Linear Algebra Appl., 2010, 432: 566–570.
  * [196] Zhou Q.N., Wang L.G., Some sufficient spectral conditions on Hamilton-connected and traceable graphs, Linear Multilinear Algebra, 2017, 65: 224–234.
  * [197] Zhou Q.N., Wang L.G., Lu Y., Some sufficient conditions on $k$-connected graphs, Applied Math. Comput., 2018, 325: 332–339.
  * [198] Zhou Q.N., Wang L.G., Lu Y., Sufficient conditions for Hamilton-connected graphs in terms of (signless Laplacian) spectral radius, Linear Algebra Appl., 2020, 594: 205–225.
  * [199] Zhou Q.N., Wang L.G., Lu Y., Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree, Linear Algebra Appl., 2020, 592: 48–64.
  * [200] Zhou Q.N., Broersma H., Wang L.G., Lu Y., On sufficient spectral radius conditions for hamiltoniancity of $k$-connected graphs, Linear Algebra Appl., 2020, 604: 129–145.
  * [201] Zhou Q.N., Broersma H., Wang L.G., Lu Y., On sufficient spectral radius conditions for Hamiltonicity, Discrete Applied Math., 2021, 296: 26–38.