# A survey on spectral conditions for some
extremal graph problems††thanks:  This paper will be published on Advances in
Mathematics (China), 2022, in press; see the official website:
http://www.oaj.pku.edu.cn/sxjz/CN/1000-0917/home.shtml or CNKI (China National
Knowledge Internet) https://navi.cnki.net/knavi/journals/SXJZ/detail. This
work was supported by NSFC (Grant Nos. 12071484, 11871479, 11931002), Hunan
Provincial Natural Science Foundation (Grant Nos. 2020JJ4675, 2018JJ2479) and
Mathematics and Interdisciplinary Sciences Project of CSU. This article is a
survey paper and it is very long with LABEL:LastPage pages. In such survey, it
is impossible to refer to all the nice papers. So if a paper is missing from
this survey, which does not mean that it is not worth including it. Last but
not least, if there are some elegant results and new progresses related to
this topic but it missed in our survey, please let me know. Any suggestions
and comments are welcome. E-mail addresses<EMAIL_ADDRESS>(Yǒngtāo Lǐ),
<EMAIL_ADDRESS>(Wěijùn Liú<EMAIL_ADDRESS>(Lìhuá Féng, corresponding
author).

Yongtao Li†, Weijun Liu‡, Lihua Feng‡,∗
†School of Mathematics, Hunan University
Changsha, Hunan, 410082, P.R. China
‡School of Mathematics and Statistics, Central South University
Changsha, Hunan, 410083, P.R. China

###### Abstract

This survey is two-fold. We first report new progress on the spectral extremal
results on the Turán type problems in graph theory. More precisely, we shall
summarize the spectral Turán function in terms of the adjacency spectral
radius and the signless Laplacian spectral radius for various graphs. For
instance, the complete graphs, general graphs with chromatic number at least
three, complete bipartite graphs, odd cycles, even cycles, color-critical
graphs and intersecting triangles.

The second goal is to conclude some recent results of the spectral conditions
on some graphical properties. By a unified method, we present some sufficient
conditions based on the adjacency spectral radius and the signless Laplacian
spectral radius for a graph to be Hamiltonian, $k$-Hamiltonian, $k$-edge-
Hamiltonian, traceable, $k$-path-coverable, $k$-connected, $k$-edge-connected,
Hamilton-connected, perfect matching and $\beta$-deficient.

Key words: extremal graph theory; spectral radius; Turán theorem; Hamilton
cycle; connectivity; matching number.

MSC (2020): 05C50, 15A18, 05C38

Chinese Library Classification:  O157.5

Document code: A

###### Contents

  1. 1 Extremal spectral problem for Turán type
    1. 1.1 Spectral problem for complete graphs
    2. 1.2 Spectral problem for general graphs
    3. 1.3 Spectral problem for bipartite graphs
    4. 1.4 Spectral problem for odd cycles
    5. 1.5 Spectral problem for even cycles
    6. 1.6 Spectral problem for color-critical graphs
    7. 1.7 Spectral problem for intersecting triangles
  2. 2 Spectral problem for Hamiltonianity
    1. 2.1 Spectral results for Hamilton cycle
    2. 2.2 Hamilton cycle in balanced bipartite graph
    3. 2.3 Problem for $k$-Hamiltonicity
    4. 2.4 Problem for $k$-edge-Hamiltonicity
  3. 3 Spectral problem for path coverability
    1. 3.1 Problem for Hamilton path
    2. 3.2 Problem for path coverability
  4. 4 Spectral problem for connectivity
    1. 4.1 Problem for $k$-connectivity
    2. 4.2 Problem for $k$-edge-connectivity
    3. 4.3 Problem for Hamilton-connectivity
  5. 5 Spectral problem for deficiency
    1. 5.1 Problem for given matching number
    2. 5.2 Problem for perfect matching
    3. 5.3 Problem for graph deficiency

## Introduction

We only consider simple connected graphs throughout paper. The notations we
used are standard from the monograph written by Bondy and Murty [24, 25]. Let
$G$ be a simple connected graph with vertex set $V(G)$ and edge set $E(G)$
such that $|V(G)|=v(G)$ and $|E(G)|=e(G)$. We usually write $n$ and $m$ for
the number of vertices and edges respectively. We use $d(v)$ to denote the
degree of the vertex $v$ in $G$. The minimum degree is denoted by $\delta(G)$.
We write $K_{n}$ and $I_{n}$ for the complete graph and empty graph on $n$
vertices respectively. Let $K_{s,t}$ be the complete bipartite graph with
parts of sizes $s$ and $t$. We write $C_{t}$ for the cycle graph on $t$
vertices. Let $\omega(G)$ denote the clique number, which is defined as the
number of vertices in a largest complete subgraph in $G$. The vertex-chromatic
number $\chi(G)$ of $G$ is the minimum integer $s\in\mathbb{N}^{*}$ such that
there exists a coloring of $V(G)$ with $s$ colors and the adjacent vertices
have different colors. For two vertex-disjoint graphs $G$ and $H$, $G\cup H$
denotes the disjoint union of $G$ and $H$; $G\vee H$ denotes the join of $G$
and $H,$ which is obtained from $G\cup H$ by adding all possible edges between
$G$ and $H$. For instance, we have $K_{s,t}=I_{s}\vee I_{t}$ and
$K_{n}=K_{t}\vee K_{n-t}$. We use the symbol $i\sim j$ to denote the vertices
$i$ and $j$ are adjacent, and $i\nsim j$ otherwise.

The Turán number of a graph $F$ is the maximum number of edges in an
$n$-vertex graph without a subgraph isomorphic to $F$, and it is usually
denoted by $\mathrm{ex}(n,F)$. We say that a graph $G$ is $F$-free if it does
not contain an isomorphic copy of $F$ as a subgraph. A graph on $n$ vertices
with no subgraph $F$ and with $\mathrm{ex}(n,F)$ edges is called an extremal
graph for $F$ and we denote by $\mathrm{Ex}(n,F)$ the set of all extremal
graphs on $n$ vertices for $F$. It is a cornerstone of extremal graph theory
to understand $\mathrm{ex}(n,F)$ and $\mathrm{Ex}(n,F)$ for various graphs
$F$; see [80, 98, 160] for surveys.

Question 1.(Extremal graph problem) What is the maximum number of edges of a
graph $G$ on $n$ vertices without a subgraph isomorphic to a given graph $F$?

In 1941, Turán [166] posed the natural question of determining
$\mathrm{ex}(n,K_{r+1})$ for $r\geq 2$. Let $T_{r}(n)$ denote the complete
$r$-partite graph on $n$ vertices where its part sizes are as equal as
possible. In other words, $T_{r}(n)=K_{t_{1},t_{2},\ldots,t_{r}}$, the
complete $r$-partite graph on vertex classes with sizes
$t_{1},t_{2},\ldots,t_{r}$, where $\sum_{i=1}^{r}t_{i}=n$ and
$|t_{i}-t_{j}|\leq 1$ for all $i\neq j$. Turán [166] (see [15, p. 294])
extended a result of Mantel [132] and obtained that if $G$ is an $n$-vertex
graph containing no $K_{r+1}$, then $e(G)\leq e(T_{r}(n))$, equality holds if
and only if $G=T_{r}(n)$. There are many extensions and generalizations on
Turán’s result. The problem of determining $\mathrm{ex}(n,F)$ is usually
called the Turán-type extremal problem. The most celebrated extension always
attributes to a result of Erdős, Stone and Simonovits [56, 62], which states
that

$\mathrm{ex}(n,F)=\left(1-\frac{1}{\chi(F)-1}+o(1)\right)\frac{n^{2}}{2},$

where $\chi(F)$ is the vertex-chromatic number of $F$. This provides good
asymptotic estimates for the extremal numbers of non-bipartite graphs.
However, for bipartite graphs, where $\chi(F)=2$, it only gives the bound
$\mathrm{ex}(n,F)=o(n^{2})$. Although there have been numerous attempts on
finding better bounds of $\mathrm{ex}(n,F)$ for various bipartite graphs $F$,
we know very little in this case. The history of such a case began in 1954
with the theorem of Kővari, Sós and Turán [101], which states that if
$K_{s,t}$ is the complete bipartite graph with vertex classes of size $s\geq
t$, then $\mathrm{ex}(n,K_{s,t})=O(n^{2-1/t})$; see [76, 77] for more details.
In particular, we refer the interested reader to the comprehensive survey
[80].

Let $G$ be a simple graph on $n$ vertices. The _adjacency matrix_ of $G$ is
defined as $A(G)=[a_{ij}]_{n\times n}$ where $a_{ij}=1$ if two vertices
$v_{i}$ and $v_{j}$ are adjacent in $G$, and $a_{ij}=0$ otherwise. We say that
$G$ has eigenvalues $\lambda_{1},\ldots,\lambda_{n}$ if these values are
eigenvalues of the adjacency matrix $A(G)$. Let $\lambda(G)$ be the maximum
value in absolute among the eigenvalues of $G$, which is known as the spectral
radius of graph $G$, that is, $\lambda(G)=\max\\{|\lambda|:\text{$\lambda$ is
an eigenvalue of $G$}\\}$. By the Perron–Frobenius Theorem [90, p. 534], the
spectral radius of a graph $G$ is actually the largest eigenvalue of $G$ since
the adjacency matrix $A(G)$ is nonnegative. We usually write $\lambda_{1}(G)$
for the spectral radius of $G$. The spectral radius of a graph sometimes can
give some information about the structure of graphs. For example, it is well-
known that the average degree of $G$ is at most $\lambda(G)$, which is at most
the maximum degree of $G$. The _diagonal matrix_ of $G$ is
$D(G)=[d_{ii}]_{n\times n}$ with diagonal entry $d_{ii}=d(i)$, the degree of
vertex $i$. The _signless Laplacian matrix_ is defined as $Q(G)=D(G)+A(G).$
The largest eigenvalue of $Q(G)$, denoted by $q(G)$, is called the $Q$-index
or the signless Laplacian spectral radius of $G$. For people that working on
spectral graph theory, one of the most well-known problems is the
Brualdi–Solheid problem [29], which states that

Question 2. (Brualdi–Solheid problem) Given a set ${\cal{G}}$ of graphs, find
a tight upper bound for the spectral radius in ${\cal{G}}$ and characterize
the extremal graphs.

This problem is well studied in the literature for many classes of graphs,
such as graphs with cut vertices [11], given diameter [87], edge chromatic
number [69], domination number [163]. For the $Q$-index counterpart of the
above problem, Zhang [192] gave the $Q$-index of graphs with given degree
sequence, Zhou [195] studied the $Q$-index and Hamiltonicity. Also, from both
theoretical and practical viewpoint, the eigenvalues of graphs have been
successfully used in many other disciplines, one may refer to [118, 189, 190].

In this paper we shall consider spectral analogues of Turán-type problems for
graphs. That is, determining
$\mathrm{ex}_{\lambda}(n,F)=\max\\{\lambda(G):|G|=n,F\nsubseteq G\\}$. It is
well-known that

$\mathrm{ex}(n,F)\leq\frac{n}{2}\mathrm{ex}_{\lambda}(n,F)$

because of the fundamental inequality ${2m}/{n}\leq\lambda(G)$. For most
graphs, this study is again fairly complete due in large part to a
longstanding work of Nikiforov [147]. The Brualdi–Solheid problem asks to
determine the maximum spectral radius of a graph $G$ on $n$ vertices belonging
to a specified class of graphs. Analogous to the Brualdi–Solheid problem, the
following question regarding the adjacency spectral radius is a natural
extension.

Question 3. (Spectral extremal problem) What is the maximum spectral radius of
a graph $G$ on $n$ vertices without a subgraph isomorphic to a given graph
$F$?

This problem regarding the adjacency spectral radius was early proposed in
[135]. Wilf [171] and Nikiforov [135] obtained spectral strengthening of
Turán’s theorem when the forbidden substructure is the complete graph. Soon
after, Nikiforov [138] showed that if $G$ is a $K_{r+1}$-free graph on $n$
vertices, then $\lambda(G)\leq\lambda(T_{r}(n))$, equality holds if and only
if $G=T_{r}(n)$. Moreover, Nikiforov [138] (when $n$ is odd), and Zhai and
Wang [185] (when $n$ is even) determined the maximum spectral radius of
$K_{2,2}$-free graphs. Furthermore, Nikiforov [145], Babai and Guiduli [7]
independently obtained the spectral generalization of the theorem of Kővari,
Sós and Turán when the forbidden graph is the complete bipartite graph
$K_{s,t}$. Finally, Nikiforov [146] characterized the spectral radius of
graphs without paths and cycles of specified length. In addition, Fiedler and
Nikiforov [73] obtained tight sufficient conditions for graphs to be
Hamiltonian or traceable. For many other spectral analogues of results in
extremal graph theory we refer the reader to the survey [147]. It is worth
mentioning that a corresponding spectral extension [142] of the theorem of
Erdős, Stone and Simonovits [56, 62] states that

$\mathrm{ex}_{\lambda}(n,F)=\left(1-\frac{1}{\chi(F)-1}+o(1)\right)n.$

In the following sections, we shall survey a large number of extremal graph
results and its corresponding spectral extremal results in some details.

##  1 Extremal spectral problem for Turán type

###  1.1 Spectral problem for complete graphs

The first theorem of extremal graph theory is commonly regarded as the theorem
of Mantel, which shows that the extremal triangle-free graphs are balanced
complete bipartite graphs. There are many proofs of this result; see, e.g.,
[15, 158, 193].

######  Theorem 1.1 (Mantel [132]).

If $G$ is an $n$-vertex graph with no triangle, then

$e(G)\leq\left\lfloor\frac{n^{2}}{4}\right\rfloor,$

equality holds if and only if $G=K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$.

A natural extension of Mantel’s theorem is the famous Turán theorem, which
extended the forbidden subgraph $K_{3}$ to large complete subgraph $K_{r+1}$
for integers $r\geq 2$. The Turán graph $T_{r}(n)$ is an $n$-vertex complete
$r$-partite graph with each part of size $n_{i}$ such that $|n_{i}-n_{j}|\leq
1$ for all $1\leq i,j\leq r$, that is, $n_{i}$ equals
$\lfloor\frac{n}{r}\rfloor$ or $\lceil\frac{n}{r}\rceil$. Sometimes, we call
$T_{r}(n)$ the balanced complete $r$-partite graph and denote the number of
its edges by $t_{r}(n)$. Clearly, we can verify that

$e(T_{r}(n))=\sum_{0\leq i<j\leq
r-1}\left\lfloor\frac{n+i}{r}\right\rfloor\left\lfloor\frac{n+j}{r}\right\rfloor.$

Moreover, if we write $n=r\\!\cdot\\!\lfloor\frac{n}{r}\rfloor+s$ for some
$0\leq s<r$, then

$e(T_{r}(n))=\left(1-\frac{1}{r}\right)\frac{(n^{2}-s^{2})}{2}+{s\choose 2}.$

In particular, we have
$T_{2}(n)=K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$ and
$t_{2}(n)=\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil=\lfloor{n^{2}}/{4}\rfloor$.

######  Theorem 1.2 (Turán [166], weak version).

If $G$ is a graph on $n$ vertices contains no copy of the complete graph
$K_{r+1}$, then

$e(G)\leq\left(1-\frac{1}{r}\right)\frac{n^{2}}{2}.$

Furthermore, equality holds if and only if $r$ divides $n$ and $G=T_{r}(n)$.

By an easy calculation, we can see that
$e(T_{r}(n))\leq(1-\frac{1}{r})\frac{n^{2}}{2}$, equality holds if and only if
$r$ divides $n$. This inequality also can be seen from Theorem 1.2 since
$T_{r}(n)$ does not contain $K_{r+1}$ as a subgraph. More generally, one can
prove the strong version of the Turán theorem in a similar way.

######  Theorem 1.3 (Turán [166], strong version).

If $G$ is a graph on $n$ vertices with no copy of $K_{r+1}$, then

$e(G)\leq e(T_{r}(n)),$

equality holds if and only if $G$ is the Turán graph $T_{r}(n)$.

Turán’s theorem initiated the rapid development of extremal graph theory and
was rediscovered many times with various different proofs; see, e.g., [3,
Chapter 40]. In the sequel, we shall present an elegant proof of the weaker
version of Turán’s theorem. This proof was proposed by Motzkin and Straus
[133] based on applying the optimization method, which is now known as the
Lagrangian method; see [164, 165] for more generalizations, and we recommend
highly a recent survey written by Yuejian Peng, Hyperhraph Lagrangian Function
(click). It is worth noting that the theorem of Motzkin and Straus was also
applied to the spectral version of Turán’s theorem; see, e.g., [135, 136, 141]
for related results.

######  Definition 1.4.

[133] Let $G$ be a graph on vertex set $[n]$. We associate a function

$\lambda(G,\bm{x}):=\sum\limits_{\\{i,j\\}\in
E(G)}x_{i}x_{j},\quad(\forall\bm{x}\in\mathbb{R}^{n}).$

We denote $\Delta:=\\{\bm{x}:x_{1},\ldots,x_{n}\geq
0,\sum_{i=1}^{n}x_{i}=1\\}$. The $Lagrangian$ of graph $G$ is defined as the
maximum of $\lambda(G,\bm{x})$ over all $\bm{x}\in\Delta$, that is,

$\lambda(G):=\max\bigl{\\{}\lambda(G,\bm{x}):{\bm{x}\in\Delta}\bigr{\\}}.$

We remark that the notation $\lambda(G)$ is frequently denoted by the spectral
radius of $G$ beyond this section. Recall that $\omega(G)$ is the number of
vertices in a largest complete subgraph of $G$, which is called the clique
number of $G$. In 1965, Motzkin and Straus [133] published a new proof of the
Turán theorem by proving the following result.

######  Theorem 1.5 (Motzkin–Straus [133]).

For any graph $G$, we have

$\lambda(G)=\frac{1}{2}\left(1-\frac{1}{\omega(G)}\right).$

###### Proof.

First of all, we write $\omega(G)=\omega$ for short. Let $K_{\omega}$ be the
largest clique in $G$. We define the vector $\bm{w}$ by setting
$w_{i}={1}/{\omega}$ for each $i\in V(K_{\omega})$ and $w_{i}=0$ for $i\in
V\setminus V(K_{\omega})$. Clearly, we have $\bm{w}$ is nonnegative and
$\sum_{i=1}^{n}w_{i}=1$. Here, we say that a vector is nonnegative if all of
its coordinates are nonnegative. Hence, we can get

$\lambda(G)\geq\lambda(G,\bm{w})=\sum_{\\{i,j\\}\in
E(K_{\omega})}\frac{1}{\omega^{2}}=\frac{1}{2}\left(1-\frac{1}{\omega}\right).$
(1)

There may exist many nonnegative vectors $\bm{x}$ with $\sum_{i=1}^{n}x_{i}=1$
satisfying $\lambda(G,\bm{x})=\lambda(G)$, we further select a vector $\bm{x}$
among these vectors such that the cardinality of its supporting set
$|\mathrm{Supp}(\bm{x})|:=\\#\\{i\in[n]:x_{i}>0\\}$ is minimal. We shall
complete the proof by the following two steps.

Step 1. We first show that the vertex set $\mathrm{Supp}(\bm{x})$ forms a
clique in $G$.

If $\mathrm{Supp}(\bm{x})$ does not form a clique in $G$, we may suppose that
$\\{i,j\\}\notin E(G)$ for some $i,j\in\mathrm{Supp}(\bm{x})$. Denoting
$s_{v}:=\sum_{u\sim v}x_{u}$ for each vertex $v\in V(G)$. We may assume
without loss of generality that $s_{i}\geq s_{j}$. Now we move the weight
$x_{j}$ from vertex $j$ to vertex $i$, that is, the new weight of vertex $i$
is $x_{i}+x_{j}$, while the weight of vertex $j$ drops to $0$. In other words,
we construct a new nonnegative vector $\bm{y}$ such that
$y_{i}=x_{i}+x_{j},y_{j}=0$ and $y_{k}=x_{k}$ for $k\in V\setminus\\{i,j\\}$.
We compute

$f_{G}(\bm{y})-f_{G}(\bm{x})=y_{i}s_{i}+y_{j}s_{j}-x_{i}s_{i}-x_{j}s_{j}=x_{j}s_{i}-x_{j}s_{j}\geq
0.$

Therefore, $\bm{y}$ also satisfies $\lambda(G,\bm{y})=\lambda(G)$ and
$|\mathrm{Supp}(\bm{y})|<|\mathrm{Supp}(\bm{x})|$, which contradicts the
minimality of the supporting set of $\bm{x}$.

Step 2. According to Step 1, the clique formed by $\mathrm{Supp}(\bm{x})$ is
now denoted by $K_{t}$ for some integer $t\leq\omega$, we next prove that
$x_{i}=1/t$ for all $i\in\mathrm{Supp}(\bm{x})$.

Otherwise, if $x_{i}>x_{j}>0$ for some $i,j\in\mathrm{Supp}(\bm{x})$, then we
choose $\varepsilon$ with $0<\varepsilon<x_{i}-x_{j}$, and change the weight
$x_{i}$ to $x_{i}-\varepsilon$ and $x_{j}$ to $x_{j}+\varepsilon$, that is to
say, we define a new non-negative vector $\bm{z}$ with
$z_{i}=x_{i}-\varepsilon,z_{j}=x_{j}+\varepsilon$ and $z_{k}=x_{k}$ for $k\in
V\setminus\\{i,j\\}$. We obtain from Step 1 that

$\lambda(G,\bm{z})-\lambda(G,\bm{x})=\sum_{\\{i,j\\}\in
E(K_{t})}z_{i}z_{j}-\sum_{\\{i,j\\}\in
E(K_{t})}x_{i}x_{j}=\varepsilon(x_{i}-x_{j})-\varepsilon^{2}>0.$

This contradicts with the fact $\lambda(G,\bm{x})=\lambda(G)$. Therefore, the
values of $x_{i}$ are all equal for every $i\in V(K_{t})$, which gives
$x_{i}=1/t$ for every $i\in V(K_{t})$. Therefore,

$\lambda(G)=\lambda(G,\bm{x})=\sum_{\\{i,j\\}\in
E(K_{t})}\frac{1}{t^{2}}=\frac{1}{2}\left(1-\frac{1}{t}\right)\leq\frac{1}{2}\left(1-\frac{1}{\omega}\right).$
(2)

Combining (1) and (2), we get $\lambda(G)=\frac{1}{2}(1-\frac{1}{\omega})$.
Moreover, the argument also showed that the nonzero weights of the maximizer
$\bm{x}$ with minimal supporting set are concentrated on a clique, which is a
largest clique of $G$, and all weights on this clique are equal. ∎

######  Corollary 1.6.

Motzkin–Straus’ Theorem 1.5 $\Rightarrow$ Turán’s Theorem 1.2.

###### Proof.

Let $G$ be a graph that does not contain $K_{r+1}$ as a subgraph. Clearly, we
have $\omega(G)\leq r$. We define the vector
$\bm{x}=\left({1}/{n},{1}/{n},\ldots,{1}/{n}\right)$, then

$\lambda(G,\bm{x})=\sum_{\\{i,j\\}\in E(G)}x_{i}x_{j}=\frac{m}{n^{2}}.$

By the Motzkin–Straus theorem, we know that

$\lambda(G,\bm{x})\leq\lambda(G)=\frac{1}{2}\left(1-\frac{1}{\omega}\right)\leq\frac{1}{2}\left(1-\frac{1}{r}\right).$

Combining the above two results, we can get
$m\leq(1-\frac{1}{r})\frac{n^{2}}{2}$. ∎

For convenience, we usually write the Motzkin–Straus theorem as the following
form.

######  Theorem 1.7 (Equivalent).

Let $G$ be an $n$-vertex graph. If $(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$
such that $x_{1},\ldots,x_{n}\geq 0$ and $x_{1}+\cdots+x_{n}=1$, then

$\sum_{\\{i,j\\}\in E(G)}x_{i}x_{j}\leq\frac{\omega(G)-1}{2\omega(G)}.$

As promised, we shall compare the extremal results based on the number of
edges and the spectral extremal results through the whole survey. In what
follows, we shall introduce some spectral version of Mantel’s theorem and
Turán’s theorem. Interestingly, the spectral versions of these extremal
results are greatly related to the Motzkin–Straus theorem.

######  Theorem 1.8 (Nosal, 1970).

Let $G$ be a graph with no triangles. Then

$\lambda(G)\leq\sqrt{e(G)},$

equality holds if and only if $G=K_{p,q}$ with $n-p-q$ isolated vertices.

This theorem together with Mantel’s Theorem 1.1 yields the following
corollary.

######  Corollary 1.9.

If $G$ is an $n$-vertex graph without triangles, then

$\lambda(G)\leq\sqrt{\lfloor n^{2}/4\rfloor}\leq{n}/{2}.$

In 1986, Wilf extended this corollary to the following theorem.

######  Theorem 1.10 (Wilf [171]).

Let $\lambda(G)$ be the largest eigenvalue of $G$. Then

${\lambda(G)\leq\left(1-\frac{1}{\omega(G)}\right)n}.$

######  Corollary 1.11 (Equivalent).

Let $G$ be a $K_{r+1}$-free graph on $n$ vertices. Then

$\lambda(G)\leq\left(1-\frac{1}{r}\right)n.$

The proof is based on the Motzkin–Straus Theorem 1.5. Recalling that

${1-\frac{1}{\omega(G)}=\max\limits_{\bm{x}\geq
0,\lVert\bm{x}\rVert_{1}=1}\bm{x}^{T}A(G)\bm{x}=\max\limits_{\bm{x}\geq
0}\frac{\bm{x}^{T}A(G)\bm{x}}{\lVert\bm{x}\rVert_{1}^{2}}.}$

###### Proof.

We show our proof in three steps.

  * •

By the Perron–Frobenius Theorem, there exists a nonnegative vector $\bm{z}$
such that

$A(G)\bm{z}=\lambda_{1}\bm{z}\Rightarrow\bm{z}^{T}A(G)\bm{z}=\lambda_{1}\bm{z}^{T}\bm{z}\Rightarrow{\lambda_{1}}=\frac{\bm{z}^{T}A(G)\bm{z}}{\bm{z}^{T}\bm{z}}.$

  * •

By the Motzkin–Straus Theorem, we have

${\frac{\bm{z}^{T}A(G)\bm{z}}{\bigl{(}\sum_{i=1}^{n}z_{i}\bigr{)}^{2}}\leq
1-\frac{1}{\omega}.}$

  * •

By the Cauchy–Schwarz inequality, we get

$\bm{z}^{T}\bm{z}=\left(\sum_{i=1}^{n}z_{i}^{2}\right)\geq\frac{1}{n}\left(\sum_{i=1}^{n}z_{i}\right)^{2}.$

Combining the above three results, we can get the required inequality. ∎

Remark. We have the following potential applications. Since the Turán graph
$T_{r}(n)$ does not contain $K_{r+1}$ as a subgraph, the Wilf theorem implies
that $\lambda(T_{r}(n))\leq\left(1-{1}/{r}\right)n$. Moreover, the Rayleigh
theorem implies that
$\lambda(G)=\max_{\bm{x}\in\mathbb{R}^{n}}{\bm{x}^{T}A\bm{x}}/{\bm{x}^{T}\bm{x}}\geq{2m}/{n}$,
hence the Wilf theorem can imply the weak version of the Turán Theorem 1.2.

Recall that $q(G)$ denotes the signless Laplacian spectral radius, i.e., the
largest eigenvalue of the signless Laplacian matrix $Q(G)=D(G)+A(G)$, where
$D(G)=\mathrm{diag}(d_{1}$, $\ldots,d_{n})$ is the degree diagonal matrix and
$A(G)$ is the adjacency matrix of a graph $G$. Note that
$Q(G)=D(G)+A(G)=L(G)+2A(G)$, where $L(G)=D(G)-A(G)$ is the so-called Laplacian
matrix, which is a positive semidefinite matrix, so we can get
$2\lambda(G)\leq q(G)$.

In 2012, Abreu and Nikiforov [1, 2] enhanced the Wilf theorem and proved that
$q(G)\leq 2\left(1-\frac{1}{\omega}\right)n$, where $\omega$ is the number of
vertices of a largest clique of $G$. In other words, this result can be
equivalently written as that if $G$ is a $K_{r+1}$-free graph on $n$ vertices,
then $q(G)\leq 2\left(1-\frac{1}{r}\right)n$.

######  Theorem 1.12 (Abreu–Nikiforov [2]).

Let $G$ be an $n$-vertex graph containing no copy of $K_{r+1}$. Then

$q(G)\leq\left(1-\frac{1}{r}\right)2n.$

We remark here that Abreu and Nikiforov did not characterize the extremal
graphs attaining the equality. We can show by a careful examination that the
equality holds if and only if $G$ is a complete bipartite for $r=2$, or $r$
divides $n$ and $G=T_{r}(n)$ for $r\geq 3$.

In 2002, Nikiforov [135] generalized the Wilf theorem by given the number of
edges.

######  Theorem 1.13 (Nikiforov [135, 136, 141]).

Let $\lambda(G)$ be the largest eigenvalue of $G$. Then

${\lambda(G)\leq\sqrt{2m\left(1-\frac{1}{\omega(G)}\right)}}.$

Moreover, the equality holds if and only if $G$ is a complete bipartite graph
for $r=2$, or a complete regular $r$-partite graph for $r\geq 3$ with possibly
some isolated vertices.

######  Corollary 1.14 (Equivalent).

Let $G$ be a $K_{r+1}$-free graph with $m$ edges. Then

$\lambda(G)\leq\sqrt{2m\left(1-\frac{1}{r}\right)}.$

This result has some similarity with the Wilf theorem. Its proof is also based
on the celebrated Motzkin–Straus Theorem, which states that for any
$x_{1},x_{2},\ldots,x_{n}\geq 0$, we have

${\frac{\sum_{\\{i,j\\}\in
E(G)}x_{i}x_{j}}{\bigl{(}\sum_{i=1}^{n}x_{i}\bigr{)}^{2}}\leq\frac{1}{2}\left(1-\frac{1}{\omega}\right).}$

###### Proof.

Let $\bm{y}=(y_{1},\ldots,y_{n})$ be an (nonnegative) eigenvector of
$\lambda(G)$.

  * •

Using the Motzkin–Straus Theorem with respect to
$(y_{1}^{2},y_{2}^{2},\ldots,y_{n}^{2})$, we have

${\frac{\left(\sum_{\\{i,j\\}\in
E(G)}y_{i}^{2}y_{j}^{2}\right)}{\bigl{(}\sum_{i=1}^{n}y_{i}^{2}\bigr{)}^{2}}\leq\frac{1}{2}\left(1-\frac{1}{\omega}\right).}$

  * •

On the other hand, we can get by Cauchy–Schwarz’s inequality that

$\displaystyle\lambda_{1}^{2}=\frac{(\bm{y}^{T}A(G)\bm{y})^{2}}{(\bm{y}^{T}\bm{y})^{2}}=\frac{\left(2\sum_{\\{i,j\\}\in
E(G)}y_{i}y_{j}\right)^{2}}{\bigl{(}\sum_{i=1}^{n}y_{i}^{2}\bigr{)}^{2}}\leq\frac{4m\left(\sum_{\\{i,j\\}\in
E(G)}y_{i}^{2}y_{j}^{2}\right)}{\bigl{(}\sum_{i=1}^{n}y_{i}^{2}\bigr{)}^{2}}.$

This completes the proof by taking square root. ∎

Remark. We have the following interesting applications. Note that the Turán
graph $T_{r}(n)$ does not contain $K_{r+1}$ as a subgraph, Nikiforov’s result
tells us that

$\lambda(T_{r}(n))\leq\sqrt{2t_{r}(n)\left(1-\frac{1}{r}\right)}\leq\left(1-\frac{1}{r}\right)n.$

Moreover, the case $r=2$ in Nikiforov’s result reduces to the Nosal Theorem
1.8. Additionally, applying the lower bound $\lambda(G)\geq{2m}/{n}$, we can
see that Nikiforov’s result implies the weak version of the Turán Theorem 1.2.
Furthermore, Nikiforov’s result implies the Wilf Theorem 1.10 by applying the
weak version of Turán theorem $m\leq(1-\frac{1}{r})\frac{n^{2}}{2}$.

We make the following conjecture for signless Laplacian spectral radius.

######  Conjecture 1.15.

Let $G$ be a $K_{r+1}$-free graph with $m$ edges. Then

$q(G)\leq\sqrt{8m\left(1-\frac{1}{r}\right)}.$

In 2002, Bollobás and Nikiforov [17] proposed the following conjecture in
terms of the first and second largest eigenvalues of $G$. Let $\lambda_{k}(G)$
be the $k$-th largest eigenvalue of $G$.

######  Conjecture 1.16 (Bollobás–Nikiforov [17]).

If $G$ does not contain a copy of $K_{r+1}$, then

$\lambda_{1}^{2}(G)+\lambda_{2}^{2}(G)\leq 2m\Bigl{(}1-\frac{1}{r}\Bigr{)}.$

Very recently, the special case $r=2$ of this conjecture was proved by Lin,
Ning and Wu [121] by using tools from doubly stochastic matrix theory, and
also characterize all families of extremal graphs. The general case $r\geq 3$
remains open.

Recall in Theorem 1.8 that if $G$ is a $C_{3}$-free graph on $n$ vertices with
$m$ edges, then $\lambda(G)\leq\sqrt{m}$, equality holds if and only if
$G=K_{p,q}$ with $n-p-q$ isolated vertices. In 2009, Nikiforov [143] proved an
interesting result, which gives an upper bound on the spectral radius for
$C_{4}$-free graph with given number of edges. Note that the star graph
$K_{m,1}$ has $m$ edges and $m+1$ vertices, and it contains no copy of
$C_{4}$. Let $S_{m,1}$ be the graph obtained from the star $K_{m-1,1}$ by
adding an edge within its independent set. Note that the graph $S_{m,1}$ has
$m$ edges and $m$ vertices. For $m=4,5,6,7,8$, we can verify that
$\lambda(S_{m,1})>\sqrt{m}$; for $m=9$, we have $\lambda(S_{9,1})=3$; for
$m=10,11,\ldots$, we can get $\lambda(S_{m,1})<\sqrt{m}$. For example, we can
calculate that $\lambda(S_{10,1})\approx 3.151<\sqrt{10}\approx 3.162$.

######  Theorem 1.17 (Nikiforov [143]).

Let $m\geq 9$ and $G$ be a graph with $m$ edges. If $G$ contains no $C_{4}$,
then

$\lambda(G)\leq\sqrt{m},$

equality holds if and only if $G$ is a star $K_{1,m}$ or $S_{9,1}$ with
possibly some isolated vertices.

Motivated by Nosal’s Theorem 1.8 and Nikiforov’s Theorems 1.17, Zhai, Lin and
Shu [187] proved the following analogue when the forbidden graph is the
bipartite graph $K_{2,r+1}$.

######  Theorem 1.18 (Zhai–Lin–Shu [187]).

Let $r\geq 2$ and $G$ be a $K_{2,r+1}$-free graph of size $m\geq 16r^{2}$.
Then

$\lambda(G)\leq\sqrt{m},$

equality holds if and only if $G$ is a complete bipartite graph with possibly
some isolated vertices.

Moreover, we denote by $B_{k}$ the book graph with $k$ pages, i.e., the graph
obtained from $k$ triangles by sharing a common edge. In [187, Conjecture
5.2], the authors presented the following conjecture, which is an extension of
the above Theorem 1.18.

######  Conjecture 1.19 (Zhai–Lin–Shu, 2021).

Let $k\geq 3$ and $m$ be large enough and $G$ be a $B_{k}$-free graph with $m$
edges. Then

$\lambda(G)\leq\sqrt{m},$

with equality if and only if $G$ is a complete bipartite graph with possibly
some isolated vertices.

We end this section with a more general conjecture. Let $B_{r,k}$ be the
generalized book, which is a graph by joining every vertex of a clique $K_{r}$
to every vertex of an independent set $I_{k}$. In the language of the join of
graphs, we have

$B_{r,k}=K_{r}\vee I_{k}.$

Clearly, we can see that $B_{2,k}=B_{k}$ and $B_{r,k}$ contains $k$ copies of
$K_{r+1}$. Hence, our conjecture is more general than Corollary 1.14.

######  Conjecture 1.20.

Let $m$ be large enough and $G$ be a $B_{r,k}$-free graph with $m$ edges. Then

$\lambda(G)\leq\sqrt{\left(1-\frac{1}{r}\right)2m},$

with equality if and only if $G$ is a complete bipartite graph for $r=2$, and
$G$ is a complete regular $r$-partite graph for $r\geq 3$ with possibly some
isolated vertices.

Note that the Wilf Theorem 1.10 and Nikiforov Theorem 1.13 can be viewed as
the spectral generalization of the weak version of Turán Theorem 1.2. In what
follows, we shall introduce the spectral generalization of the strong version
of the Turán Theorem 1.3. In 2007, Feng, Li and Zhang [67] proved that the
Turán graph $T_{r}(n)$ attains the maximum spectral radius among all
$n$-vertex graphs with given chromatic number.

######  Theorem 1.21 (Feng–Li–Zhang [67]).

Let $G$ be an $n$-vertex complete $r$-partite graph. Then

$\lambda(G)\leq\lambda({T_{r}(n)}),$

equality holds if and only if $G$ is the Turán graph $T_{r}(n)$.

Recall that $Q(G)=D(G)+A(G)=L(G)+2A(G)$ and $L(G)=D(G)-A(G)$ is positive
semidefinite, which implies $q(G)\geq 2\lambda(G)$. The following result on
the signless Laplacian spectral radius of a complete $r$-partite graph is also
well-known in the literature.

######  Theorem 1.22 (Cai–Fan [33, 154, 179]).

Let $G$ be an $n$-vertex complete $r$-partite graph. Then

$q(G)\leq q({T_{r}(n)}),$

equality holds if and only if $r=2$ and $G=K_{s,n-s}$ for some $s$, or $r\geq
3$ and $G=T_{r}(n)$.

In the meantime, Nikiforov [138] generalized Feng–Li–Zhang’s result since
every $r$-partite graph is $K_{r+1}$-free, as well as enhanced Wilf’s Theorem
1.10 since we can verify that $\lambda(T_{r}(n))\leq(1-\frac{1}{r})n$, where
the equality holds if and only if $r$ divides $n$. However, this result on
extremal graph problems was early established by Guiduli [85, pp. 58–61] on
his PH.D. thesis dating from 1996. In addition, the Wilf Theorem 1.10 can be
viewed as the weak version of the following spectral Turán Theorem.

######  Theorem 1.23 (Spectral Turán Theorem, Guiduli–Nikiforov).

Let $G$ be a graph on $n$ vertices not containing $K_{r+1}$ as a subgraph.
Then

$\lambda(G)\leq\lambda({T_{r}(n)}),$

equality holds if and only if $G$ is the Turán graph $T_{r}(n)$.

The main idea of the proof of Theorem 1.23 in [138] is based on the
characteristic polynomial of the Turán graph and two important theorems. The
first theorem is also presented early by Nikiforov in [135, Theorem 3.1],
which states that if $G$ is a $K_{r+1}$-free graph, then

$\lambda^{r}\leq
k_{2}\lambda^{r-2}+\cdots+(j-1)k_{j}\lambda^{r-j}+\cdots+(r-1)k_{r},$

where $\lambda=\lambda(G)$ and $k_{i}=k_{i}(G)$ are the spectral radius and
the number of $i$-cliques of $G$ respectively. In particular, the case $r=2$
yields the Nosal Theorem 1.8, that is, $\lambda\leq\sqrt{k_{2}}=\sqrt{e(G)}$
for all $K_{3}$-free graphs. The second used theorem is an old result of Erdős
[59], which says that if $G$ is a $K_{r+1}$-free graph, then

$k_{i}(G)\leq k_{i}(T_{r}(n)).$

In other words, the Turán graph attains the maximum number of cliques of order
$i$ among all $K_{r+1}$-free graphs. Clearly, the case $i=2$ reduces to the
Turán theorem.

We remark here that there is another proof for the spectral Turńn theorem in
[96] (early shown in [85]). The proof given in [96, Lemma 9] reduces Theorem
1.23 to complete $r$-partite graphs, then one can show that the balanced
complete $r$-partite graph attains the maximum value of the spectral radius;
see [67] or [97, Theorem 2] for more details. The advantage of this proof is
that we can avoid the use of the characteristic polynomials of the adjacency
matrices of graphs, and this proof allows us to extend the spectral result to
the $p$-spectral radius for every $p>1$, which is defined as

$\lambda^{(p)}(G):=\max\bigl{\\{}\bm{x}^{T}A(G)\bm{x}:{\bm{x}\in\mathbb{R}^{n},\lVert\bm{x}\rVert_{p}=1}\bigr{\\}}.$

Note that the $p$-spectral radius is just an extremal function on graph, and
there is no characteristic polynomial corresponding to the $p$-spectral
radius.

It is easy to see that Theorem 1.23 implies the weak version of Turán’s
Theorem. A more natural question you can ask may be the following one.

Question. Does Theorem 1.23 imply the strong version of Turán’s Theorem?

This question was also proposed in [141]. The answer is positive. It is well-
known that ${e(G)}\leq\frac{n}{2}\lambda(G)$, with equality if and only if $G$
is regular. Although the Turán graph $T_{r}(n)$ is sometimes not regular, but
it is nearly regular. Upon calculation, we can verify that

${e(T_{r}(n))}=\left\lfloor\frac{n}{2}\lambda(T_{r}(n))\right\rfloor.$ (3)

Let $n=rs+t$ where $0\leq t<r$ and $s=\lfloor n/r\rfloor$. Hence the Turán
graph $T_{r}(n)$ has $t$ parts of size $s+1$ and $r-t$ parts of size $s$, and
we can compute that

$\displaystyle e(T_{r}(n))$
$\displaystyle=\frac{1}{2}\bigl{(}(n-s-1)(s+1)t+(n-s)s(r-t)\bigr{)}.$

and

$\lambda(T_{r}(n))=\frac{1}{2}(n-2s-1+\sqrt{n^{2}-4sn-2n+4rs^{2}+4rs+1}).$

With the help of the observation in (3), the spectral Turán theorem implies
that

$e(G)\leq\left\lfloor\frac{n}{2}\lambda(G)\right\rfloor\leq\left\lfloor\frac{n}{2}\lambda(T_{r}(n))\right\rfloor=e(T_{r}(n)).$

In 2013, He, Jin and Zhang [88, Theorem 1.3] proved the signless Laplacian
spectral version of the Turán theorem, which improved Theorem 1.12 showing by
Abreu and Nikiforov since $q(T_{r}(n))\leq 2\left(1-\frac{1}{r}\right)n$.
However, if $r$ divides $n$, then $q(T_{r}(n))=2\left(1-\frac{1}{r}\right)n$.
Moreover, they also illustrated that the signless Laplacian spectral version
implies the original Turán theorem.

######  Theorem 1.24 (He–Jin–Zhang [88]).

Let $G$ be a $K_{r+1}$-free graph of order $n$. Then

$q(G)\leq q({T_{r}(n)}),$

equality holds if and only if $r=2$ and $G=K_{s,n-s}$ for some $s$, or $r\geq
3$ and $G=T_{r}(n)$.

As mentioned in [88, Corollary 2.5], this spectral version of the signless
Laplacian radius implies the strong version of the Turán Theorem 1.3 since

$e(G)\leq\left\lfloor\frac{n}{4}q(G)\right\rfloor\leq\left\lfloor\frac{n}{4}q(T_{r}(n))\right\rfloor=e(T_{r}(n)).$

From what has been discussed above, we conclude that the edge version of the
Turán theorem can be deduced from the spectral version of either the adjacency
matrix or the signless Laplacian matrix. Along with the development of the
spectral graph theory, it is commonly recognized that the spectral versions of
extremal graph problems are more challenging and interesting.

###  1.2 Spectral problem for general graphs

In this section, we shall consider the extremal number $\mathrm{ex}(n,F)$ for
general graph $F$. In 1946, Erdős and Stone [56] proved a celebrated theorem,
which states that

######  Theorem 1.25 (Erdős–Stone [56]).

For every $r\geq 1,t\geq 1$ and $\varepsilon>0$, there is
$n_{0}=n_{0}(r,t,\varepsilon)$ such that every graph $G$ on $n\geq n_{0}$
vertices with $e(G)\geq(1-\frac{1}{r}+\varepsilon)\frac{n^{2}}{2}$ contains a
copy of a complete $(r+1)$-partite graph $K_{r+1}(t)$, whose every vertex
class has $t$ vertices.

This result is sharp in the following qualitative sense. Let $T_{r}(n)$ denote
the complete $r$-partite graph of order $n$ whose vertex classes have the
number of vertices as equal as possible. Clearly, $T_{r}(n)$ contains no
complete subgraph of order $r+1$ and
$e(T_{r}(n))=(1-\frac{1}{r})\frac{n^{2}}{2}+O(n)$. From this observation, we
can get a lower bound on $\mathrm{ex}(n,K_{r+1}(t))$. Hence Theorem 1.25
yields the following two corollaries.

######  Corollary 1.26.

For every integers $r\geq 1$ and $t\geq 1$, then

$\mathrm{ex}(n,K_{r+1}(t))=\left(1-\frac{1}{r}+o(1)\right)\frac{n^{2}}{2},$

where $o(1)\to 0$ whenever $n\to\infty$.

######  Corollary 1.27 (Equivalent).

For every integer $t\geq 1$, we have

$\lim\limits_{n\to\infty}\frac{\mathrm{ex}(n,K_{r+1}(t))}{{n\choose
2}}=1-\frac{1}{r}.$

A proper vertex-coloring of a graph is a coloring of its vertex set for which
each color class forms an independent set. The chromatic number of a graph
$G$, denoted by $\chi(G)$, is the minimum number of colors needed in a proper
coloring of $G$. A graph is $r$-partite if it has chromatic number at most
$r$. In other words, the vertex-chromatic number $\chi(G)$ of $G$ is the
minimum integer $s\in\mathbb{N}^{*}$ such that there exists a coloring of
$V(G)$ with $s$ colors and the adjacent vertices have different colors. For
example, we can see that $\chi(K_{r+1})=r+1$ and $\chi(K_{s,t})=2$. In fact, a
graph $H$ has $\chi(H)=r+1$ if and only if $H$ is an $(r+1)$-partite graph.

This powerful result of Erdős and Stone has many important applications in
extremal graph theory. Consequently, the Erdős–Stone theorem implies the
following theorem since if $F$ is a graph with chromatic number $\chi(F)=r+1$,
then $F$ is contained in $K_{r+1}(t)$ for an appropriate integer $t$. By
applying the monotonicity of the Turán function, we get
$\mathrm{ex}(n,F)\leq\mathrm{ex}(n,K_{r+1}(t))$. This theorem was established
by Erdős and Simonovits in [62].

######  Theorem 1.28 (Erdős–Simonovits [62]).

For every graph $H$, we have

$\mathrm{ex}(n,H)=\left(1-\frac{1}{\chi(H)-1}\right)\frac{n^{2}}{2}+o(n^{2}).$

Equivalently, we can write the above result as the limitation.

$\boxed{\lim_{n\to\infty}\frac{\mathrm{ex}(n,H)}{{n\choose
2}}=\frac{1}{\chi(H)-1}.}$

Although this result was formally established by Erdős and Simonovits, we
always call it the Erdős–Stone–Simonovits theorem for the sake of their
equivalence relation. We mention here that Erdős, Stone and Simonovits never
wrote a paper together. First Erdős and Stone solved it for $H$ a complete
multipartite graph, and then Erdős and Simonovits proved it for general $H$ in
this way.

###### Proof.

First of all, we denote $\chi(H)=r+1$. It is easy to see that the $n$-vertex
complete $r$-partite Turán graph $T_{r}(n)$ contains no copy of $H$ otherwise
$H$ is $r$-partite, so $H$ can be colored by $r$ colors, a contradiction.
Thus, we can get

$\mathrm{ex}(n,H)\geq
t_{r}(n)\geq\left(1-\frac{1}{r}\right)\frac{n^{2}}{2}-\frac{r}{8}=\left(1-\frac{1}{r}-o(1)\right)\frac{n^{2}}{2}.$

For the upper bound, since $\chi(H)=r+1$, there exists an integer $t$ such
that $H$ is a subgraph of $K_{r+1}(t)$. By the Erdős–Stone Theorem 1.25, we
can get

$\mathrm{ex}(n,H)\leq\mathrm{ex}(n,K_{r+1}(t))\leq t_{r}(n)+o(n^{2}).$

Hence, we have proved that for some fixed integer $v$,

$t_{r}(n)\leq\mathrm{ex}(n,H)\leq\mathrm{ex}(n,K_{r+1}(t))\leq
t_{r}(n)+o(n^{2}).$

This completes the proof. ∎

The Erdős–Stone–Simonovits theorem implies straightforward the following
extremal number for graphs corresponding to the five regular polyhedrons.

  * •

The regular tetrahedron forms the graph $K_{4}$, we have
$\mathrm{ex}(n,K_{4})=e(T_{3}(n))=\lfloor n^{2}/3\rfloor$.

  * •

Let $Q_{8}$ be the cube graph on $8$ vertices. Then $\chi(Q_{8})=2$ and
$\mathrm{ex}(n,Q_{8})=o(n^{2})$.

  * •

Let $O_{6}$ be the octahedron graph on $6$ vertices. It is easy to see that
$O_{6}$ is a complete $3$-partite graph with each part of size $2$, i.e.,
$O_{6}=K_{2,2,2}$. Then $\chi(O_{6})=3$ and

$\mathrm{ex}(n,O_{6})=\frac{n^{2}}{4}+o(n^{2}).$

  * •

Let $D_{20}$ be the dodecahedron graph on $20$ vertices. Then $\chi(D_{20})=3$
and

$\mathrm{ex}(n,D_{20})=\frac{n^{2}}{4}+o(n^{2}).$

  * •

Let $I_{12}$ be the icosahedron graph on $12$ vertices. Then $\chi(I_{12})=4$
and

$\mathrm{ex}(n,I_{12})=\frac{n^{2}}{3}+o(n^{2}).$

We remark here that although the Erdős–Stone–Simonovits theorem provides good
asymptotic estimates for the extremal numbers of non-bipartite graphs.
However, for bipartite graphs, where $\chi(F)=2$, it only gives the bound
$\mathrm{ex}(n,F)=o(n^{2})$. Although there have been numerous attempts of
finding better bounds on $\mathrm{ex}(n,F)$ for various bipartite graphs $F$,
we know very little in this case; see [80] for a survey.

We know that the Rayleigh formula implies $\lambda(G)\geq 2e(G)/n$. In 2009,
Nikiforov [142] proved a spectral generalization of the Erdős–Stone–Simonovits
theorem. Moreover, Nikiforov also gave an explicit bound on the size of each
vertex part of the complete multipartite graph in terms of the adjacency
spectral radius. The main idea of the proof of Nikiforov is based on two
results from [17] and [140].

######  Theorem 1.29 (Nikiforov [142]).

Let $n\geq r\geq 3$ be integers with $(c/r^{r})^{r}\ln n\geq 1$. If $G$ is a
graph on $n$ vertices with

$\lambda(G)\geq\left(1-\frac{1}{r-1}+c\right)n,$

then $G$ contains a copy of $K_{r}(s,\ldots,s,t)$ with $s\geq(c/r^{r})^{r}\ln
n$ and $t>n^{1-c^{r-1}}$.

Similarly, one can get the following asymptotic spectral extremal number for
general graphs. This result was early proved by Guiduli in his PH.D. thesis
[85] in 1996. Analogous to the Turán function, we define the spectral Turán
function as $\mathrm{ex}_{\lambda}(n,F)$, which is the maximum spectral radius
in an $n$-vertex graph without subgraph isomorphic to $F$. It is important and
meaningful to determine the function $\mathrm{ex}_{\lambda}(n,F)$ for various
graphs $F$.

######  Corollary 1.30 (Guiduli–Nikiforov).

For every integers $r\geq 2$ and $t\geq 1$, we have

$\mathrm{ex}_{\lambda}(n,K_{r}(t))=\left(1-\frac{1}{r-1}\right)n+o(n).$

Consequently, if $F$ is a graph with chromatic number $\chi(F)$, then

$\mathrm{ex}_{\lambda}(n,F)=\left(1-\frac{1}{\chi(F)-1}\right)n+o(n).$

This result can be rewritten as the following limitation.

$\boxed{\lim_{n\to\infty}\frac{\mathrm{ex}_{\lambda}(n,F)}{n}=1-\frac{1}{\chi(F)-1}.}$

We mentioned here that Guiduli [85] proved Corollary 1.30 by using a result
proved by Erdős, Frankl and Rödl [63], which states that for any $r,t\geq 1$
and $\varepsilon>0$, there exists an integer $n_{0}$ such that if $G$ is a
$K_{r}(t)$-free graph on $n\geq n_{0}$ vertices, then we can remove at most
$\varepsilon n^{2}$ edges from $G$ to make it being $K_{r}$-free. This result
is a direct consequence of the celebrated Szemerédi Regularity Lemma.

Next, we shall provide an alternative proof of Corollary 1.30 by applying the
Graph Removal Lemma, which states that for every graph $H$ on $h$ vertices and
every $\varepsilon>0$, there exists $\delta=\delta_{H}(\varepsilon)>0$ such
that any graph on $n$ vertices with at most $\delta n^{h}$ copies of $H$ can
be made $H$-free by removing at most $\varepsilon n^{2}$ edges; see, e.g.,
[74, 47].

###### Alternative Proof.

Let $F$ be a fixed graph with $\chi(F)=r$ for some $r\geq 2$. For any
$\varepsilon>0$, if $G$ is an $n$-vertex graph with
$\lambda(G)\geq(1-\frac{1}{r-1}+\varepsilon)n$, the Wilf theorem implies that
$G$ contains at least one copy of $K_{r}$. Next, we shall show that the number
of copies of $K_{r}$ is at least $\delta_{K_{r}}({\varepsilon}/{2})\cdot
n^{r}$ where $\delta_{H}(\varepsilon)$ is the function determined in the Graph
Removal Lemma. This is the spectral version of the supersaturation lemma for
$K_{r}$. Indeed, suppose on the contrary that $G$ has less than
$\delta_{K_{r}}({\varepsilon}/{2})\cdot n^{r}$ copies of $K_{r}$, then the
Graph Removal Lemma yields that we can remove at most
$\frac{\varepsilon}{2}n^{2}$ edges from $G$ such that the remaining subgraph
$G^{*}$ is $K_{r}$-free. The Wilf theorem gives that
$\lambda(G^{*})\leq(1-\frac{1}{r-1})n$. Hence, the Rayleigh formula yields

$\lambda(G)\leq\lambda(G^{*})+\lambda(G\setminus
G^{*})<\lambda(G^{*})+\sqrt{2e(G\setminus
G^{*})}\leq\left(1-\frac{1}{r-1}\right)n+\varepsilon n,$

a contradiction. Hence $G$ has at least
$\delta_{K_{r}}({\varepsilon}/{2})\cdot n^{r}$ copies of $K_{r}$.

Now, we define an $r$-uniform hypergraph $\mathcal{G}^{(r)}$ on the vertex set
$V(G)$ where an $r$-element subset $E\subseteq V(G)$ is defined to be a
hyperedge if and only if it induces a copy of $K_{r}$ in the $2$-graph $G$.
Under this definition, we know that $\mathcal{G}^{(r)}$ has at least
$\delta_{K_{r}}({\varepsilon}/{2})\cdot n^{r}$ edges. We denote by
$K^{(r)}_{t,t,\ldots,t}$ the complete $r$-partite $r$-uniform hypergraph with
each vertex part of size $t$. A well-known result of Erdős [60] states that

$\mathrm{ex}(n,K^{(r)}_{t,t,\ldots,t})=O(n^{r-({1}/{t})^{r-1}}).$

Therefore, for sufficiently large $n$, the hypergraph $\mathcal{G}^{(r)}$
contains a copy of $K^{(r)}_{t,t,\ldots,t}$. Note that every copy of
$K^{(r)}_{t,t,\ldots,t}$ in $\mathcal{G}^{(r)}$ corresponds to a copy of
$K_{r}(t)$ in $G$. Hence $G$ contains a copy of $K_{r}(t)$ for any
$\varepsilon>0$ and large enough $n$. ∎

######  Conjecture 1.31.

If $G$ is an $F$-free graph with $m$ edges, then

$\lambda(G)\leq\sqrt{\left(1-\frac{1}{\chi(F)-1}+o(1)\right)2m}.$

A natural question is to extend the above-mentioned results on the adjacency
spectral radius to that of the signless Laplacian spectral radius. We define
$\mathrm{ex}_{q}(n,F)$ to be the largest eigenvalue of the signless Laplacian
matrix in an $n$-vertex graph that contains no copy of $F$. That is,

$\mathrm{ex}_{q}(n,F):=\max\bigl{\\{}q(G):|G|=n~{}\text{and}~{}F\nsubseteq
G\bigr{\\}}.$

Note that $Q(G)=D(G)-A(G)+2A(G)$ and $D(G)-A(G)$ is positive semidefinite. It
is known by the Weyl theorem for monotonicity of eigenvalues that $q(G)\geq
2\lambda(G)$. Comparing to Corollary 1.30, one may ask the following question:

Question. Let $F$ be a fixed graph. Is it true that
$\mathrm{ex}_{q}(n,F)=\left(1-\frac{1}{\chi(F)-1}\right)2n+o(n)$.

The answer of this question is negative. Let $k\geq 2$ be a positive integer
and $S_{n,k}$ be the graph consisting of a clique on $k$ vertices and an
independent set on $n-k$ vertices in which each vertex of the clique is
adjacent to each vertex of the independent set. Let $S_{n,k}^{+}$ be the graph
obtained from $S_{n,k}$ by adding an edge to the independent set $I_{n-k}$. In
the language of join of graphs, we have

$S_{n,k}^{+}=K_{k}\vee I_{n-k}^{+}.$

Clearly, we can see that $S_{n,k}^{+}$ does not contain $C_{2k+2}$ as a
subgraph. It was proved by Nikiforov and Yuan [148] that
$\mathrm{ex}_{q}(n,C_{2k+2})=q(S_{n,k}^{+})$ for $n\geq 400k^{2}$. However
$\chi(C_{2k+2})=2$ and $q(S_{n,k}^{+})\neq o(n)$.

###  1.3 Spectral problem for bipartite graphs

The history of studying the extremal number for bipartite graphs began in 1954
with the Kővari–Sós–Turán theorem [101], which states that if $K_{s,t}$ is the
complete bipartite graph with vertex classes of size $s\geq t$, then
$\mathrm{ex}(n,K_{s,t})=O(n^{2-1/t})$; see [76, 77] for more details. In
particular, we refer the interested reader to the comprehensive survey by
Füredi and Simonovits [80] for the history of bipartite extremal graph
problems.

######  Theorem 1.32 (Kővari–Sós–Turán, 1954).

For all $t\geq s\geq 2$, If $G$ is an $n$-vertex graph and contains no copy of
$K_{s,t}$, then

$e(G)\leq\frac{1}{2}(t-1)^{\frac{1}{s}}n^{2-\frac{1}{s}}+\frac{1}{2}(s-1)n.$

In other words, we have

$\mathrm{ex}(n,K_{s,t})\leq\frac{1}{2}(t-1)^{\frac{1}{s}}n^{2-\frac{1}{s}}+\frac{1}{2}(s-1)n{\,\,\approx\frac{1}{2}(t-1)^{\frac{1}{s}}n^{2-\frac{1}{s}}.}$

For convenience of readers, we here include a standard proof, which is a well
application of the double counting technique.

###### Proof.

Let $G$ be a $K_{s,t}$-free $n$-vertex graph with $m$ edges. We denote the
number of copies of $K_{s,1}$ in $G$ as $\\#K_{s,1}$. The proof establishes an
upper bound and a lower bound on $\\#K_{s,1}$, and then gets a bound on $m$ by
combining the upper bound and the lower bound. Since $K_{s,1}$ is a tree, we
can call the side with $s$ vertices the leaf vertices, and the side with $1$
vertices the root vertex.

On the one hand, we can count $\\#K_{s,1}$ by enumerating the leaf vertices.
For any subset $S$ of $s$ vertices, the number of $K_{s,1}$ is exactly the
number of common neighbors of these $s$ vertices. We write $d(S)$ for the
number of common neighbors of vertices of $S$, i.e., $d(S)=|\cap_{v\in
S}N(v)|$. Since $G$ is $K_{s,t}$-free, we get $d(S)\leq t-1$. Thus, we
establish that

$\\#K_{s,1}=\sum_{S\in{V\choose s}}d(S)\leq\binom{n}{s}(t-1).$

On the other hand, for each vertex $v\in V(G)$, the number of copies of
$K_{s,1}$ where $v$ is the root vertex is exactly $\binom{d(v)}{s}$.
Therefore,

$\\#K_{s,1}=\sum_{v\in V(G)}\binom{d(v)}{s}\geq n\binom{\frac{1}{n}\sum_{v\in
V(G)}d(v)}{s}=n\binom{2m/n}{s},$

where the inequality uses the convexity of $x\mapsto\binom{x}{s}$. Here we
regard $\binom{x}{s}$ as a degree $s$ polynomial in $x$, so it makes sense for
$x$ to be non-integers.

Combining the upper bound and lower bound of $\\#K_{s,1}$, we obtain that
$n\binom{2m/n}{s}\leq\binom{n}{s}(t-1)$. For constant $s$, we can use
$\binom{x}{s}=(1+o(1))\frac{x^{s}}{s!}$ to get
$n\left(\frac{2m}{n}\right)^{s}\leq(1+o(1))n^{s}(t-1)$. The above inequality
simplifies to $m\leq\left(\frac{1}{2}+o(1)\right)(t-1)^{1/s}n^{2-{1}/{s}}$. ∎

######  Definition 1.33 (Zarankiewicz).

Let $z(m,n,s,t)$ be the maximum number of edges in a bipartite graph $G$ with
vertex parts $M$ of size $m$ and $N$ of size $n$ such that $G$ does not
contain a copy of $K_{s,t}$ with vertex part of size $s$ in $M$ and vertex
part of size $t$ in $N$.

In the language of matrix, the value $z(m,n,s,t)$ can be defined as the
maximum number of ones in a matrix consisting only of zeros and ones of size
$m\times n$ that does not contain an all ones submatrix of size $s\times t$.
The problem of finding this number is known as the Zarankiewicz problem.

Clearly, we can see from the definition that
$z(n,n,s,t)\leq\mathrm{ex}(2n,K_{s,t})$. We next show that
$2\mathrm{ex}(n,K_{s,t})\leq z(n,n,s,t)$. To prove this inequality, we just
need to construct a bipartite graph $G$ that has $2\mathrm{ex}(n,K_{s,t})$
edges and contains no copy of $K_{s,t}$. Let $G$ be an extremal graph with
$\mathrm{ex}(n,K_{s,t})$ edges and contains no copy of $K_{s,t}$. We define a
bipartite graph $H$ on vertex sets $V_{1}$ and $V_{2}$ where
$V_{1}=V_{2}=V(G)$ with edge set $E(H)=\\{\\{u,v\\}:u\in V_{1},v\in
V_{2},\\{u,v\\}\in E(G)\\}$. We can verify that $H$ does not contain any copy
of $K_{s,t}$ and $H$ has $2e(G)$ edges. Thus, we get
$2\mathrm{ex}(n,K_{s,t})\leq z(n,n,s,t)$. We now state the above observation
as the following proposition.

######  Proposition 1.34.

$2\mathrm{ex}(n,K_{s,t})\leq z(n,n,s,t)\leq\mathrm{ex}(2n,K_{s,t})$.

From this proposition, it turns the problems of finding an upper bound for the
Turán number into an upper bound of the Zarankiewicz problems. Using the
counting method in the proof of the Kővári–Sós–Turán theorem, we can similarly
prove that

$z(m,n,s,t)\leq(s-1)^{\frac{1}{t}}\cdot(n-t+1)m^{1-\frac{1}{t}}+(t-1)m.$

In 1996, Füredi [76] improved the coefficient of this bound to
$(s-t+1)^{1/t}$.

######  Theorem 1.35 (Füredi [76]).

For all $s\geq t\geq 1$, we have

$z(m,n,s,t)\leq{(s-t+1)}^{\frac{1}{t}}nm^{1-\frac{1}{t}}+tm^{2-\frac{2}{t}}+tn.$
(4)

In 2010, Nikiforov proved by an elegant induction that

######  Theorem 1.36 (Nikiforov [145]).

If $s,t\geq 2$, then for every $k=0,1,\ldots,s\\!-\\!2$,

$z(m,n,s,t)\leq(s-k-1)^{\frac{1}{t}}nm^{1-\frac{1}{t}}+(t-1)m^{1+\frac{k}{t}}+kn.$

For $k=0$, the upper bound of Kővari, Sós and Turán is obtained, and, if
$s\geq t$, considering $k=t-2$, the author improved slightly Füredi’s bound
since the case $k=t-2$ leads to
$z(m,n,s,t)\leq(s-t+1)^{{1}/{t}}nm^{1-{1}/{t}}+(t-1)m^{2-{2}/{t}}+(t-2)n$.

We remark that finding the lower bound of $\mathrm{ex}(n,K_{s,t})$ is
extremely difficult. By using the Probabilistic Method, one can get a lower
bound of $\mathrm{ex}(n,K_{s,t})$.

######  Theorem 1.37.

For all $t\geq s\geq 2$, we have

$\mathrm{ex}(n,K_{s,t})\geq\frac{1}{16}n^{2-\frac{s+t-2}{st-1}}.$

######  Corollary 1.38.

For all positive integer $s$, we have

$c_{1}(s)\cdot n^{2-\frac{2}{s+1}}\leq\mathrm{ex}(n,K_{s,s})\leq c_{2}(s)\cdot
n^{2-\frac{1}{s}},$

where $c_{1}(s)$ and $c_{2}(s)$ are constants depending only on $s$.

###### Proof of Theorem 1.37.

We consider the random graph $G(n,p)$, a graph on $n$ vertices where each each
is chosen independently from $K_{n}$ with probability $p$. Let $\\#K_{s,t}$
denote the number of copies of $K_{s,t}$ in $G(n,p)$. Then the expected number
of edges and copies of $K_{s,t}$ are given by $\mathbb{E}[e(G)]=p{n\choose 2}$
and $\mathbb{E}[\\#K_{s,t}]={n\choose s}{n-s\choose t}p^{st}$ respectively. By
the linearity of expectation, we have

$\mathbb{E}[e(G)-\\#K_{s,t}]=\mathbb{E}[e(G)]-\mathbb{E}[\\#K_{s,t}]\geq\frac{1}{4}pn^{2}-n^{s+t}p^{st}.$

We now want to pick $p$ so that the right hand side in above is as large as
possible. By setting $p=\frac{1}{2}n^{-\frac{s+t-2}{st-1}}$, we can get
$\mathbb{E}[e(G)-\\#K_{s,t}]\geq\frac{1}{8}pn^{2}=\frac{1}{16}n^{2-\frac{s+t-2}{st-1}}$.
Thus there exists a graph $G$ in which
$e(G)-\\#K_{s,t}\geq\frac{1}{16}n^{2-\frac{s+t-2}{st-1}}$, and by removing one
edge from each copy of $K_{s,t}$, we can get a $K_{s,t}$-free graph with at
least $\frac{1}{16}n^{2-\frac{s+t-2}{st-1}}$ edges. ∎

######  Conjecture 1.39.

For $t\geq s\geq 2$, we have $\mathrm{ex}(n,K_{s,t})=\Theta(n^{2-{1}/{s}})$.

We here list the recent progress of this conjecture in the literature. In
1996, Kollár, Rónyai and Szabó [102] confirmed this conjecture for the case
$t>s!$. In 1999, Alon, Rónyai and Szabó [5] slightly improved to the case
$t>(s-1)!$. In 2013, Blagojević, Bukh and Karasev [14] and later Bukh [30]
used the random algebraic method to give different constructions which yield
the same lower bound $\mathrm{ex}(n,K_{s,t})=\Omega(n^{2-1/s})$, provided that
$t$ is sufficiently large. In 2021, Bukh made a further improvement [32] by
applying the random algebraic construction again.

Note that ${2e(G)}/{n}\leq\lambda(G)$. Hence finding the upper bounds on the
adjacency spectral radius extends the general extremal bounds on number of
edges. In 2007, Babai and Guiduli [7] published an asymptotic bound of the
Kővári–Sós–Turán upper bound on the spectral radius (Their work dates back to
1996 on the PH.D. thesis of Guiduli [85]).

######  Theorem 1.40 (Babai–Guiduli [85, 7]).

Let $\lambda(G)$ denote the spectral radius of $G$.
(1) Let $s\geq 2$ be an integer. If $G$ is an $n$-vertex $K_{s,2}$-free graph,
then

$\lambda(G)\leq(s-1)^{\frac{1}{2}}n^{\frac{1}{2}}+O(n^{\frac{1}{4}}).$

(2) Let $s\geq t\geq 2$ be integers. If $G$ is an $n$-vertex $K_{s,t}$-free
graph, then

$\lambda(G)\leq\Bigl{(}(s-1)^{\frac{1}{t}}+o(1)\Bigr{)}n^{1-\frac{1}{t}}.$

Nikiforov [138] proved the following spectral extremal problem for
$K_{2,\ell}$ and the book graph $B_{k+1}=K_{2}\vee I_{k+1}$, a graph obtained
by joining each vertex of $K_{2}$ to each vertex of an independent set of size
$k+1$.

######  Theorem 1.41 (Nikiforov [138]).

Let $\ell\geq k\geq 0$ be integers. If $G$ is a graph on $n$ vertices and
contains no copy of $K_{2,\ell+1}$ and $K_{2}\vee{I_{k+1}}$, then

$\lambda(G)\leq\frac{1}{2}\Bigl{(}k-\ell+1+\sqrt{(k-\ell+1)^{2}+4\ell(n-1)}\Bigr{)}.$

In particular, this theorem implies the following result.

######  Corollary 1.42.

Let $s\geq 2$. If $G$ is an $n$-vertex $K_{s,2}$-free graph, then

$\lambda(G)\leq\frac{1}{2}+\sqrt{(s-1)(n-1)+{1}/{4}}.$

As a consequence of Theorem 1.36, Nikiforov [145] improved the result of Babai
and Guiduli concerning the largeness of the spectral radius of a graph of
certain order that does not contain a complete bipartite subgraph $K_{s,t}$.

######  Theorem 1.43 (Nikiforov [145]).

Let $s\geq t\geq 3$ be integers. If $G$ is an $n$-vertex $K_{s,t}$-free graph
with spectral radius $\lambda(G)$. Then

$\lambda(G)\leq{(s-t+1)^{\frac{1}{t}}}n^{1-\frac{1}{t}}+(t-1)n^{1-\frac{2}{t}}+t-2.$

A natural question is that how to characterize the extremal graphs attaining
the equality in Theorems 1.36 and 1.43. For the edge version, it is extremely
difficult to find the graph attaining the upper bound even for the special
graph $K_{2,2}$. Surprisingly, the extremal graphs of the spectral problem for
$K_{2,2}$ was determined by Nikiforov [138], and Zhai and Wang [185]. We infer
the readers to Subsection 1.5 for more details.

###  1.4 Spectral problem for odd cycles

Let $C_{2k+1}$ denote the cycle on $2k+1$ vertices. Note that $C_{2k+1}$ has
chromatic number $\chi(C_{2k+1})=3$. The Erdős–Stone Theorem 1.25 or
Erdős–Simonovits Theorem 1.28 implies that
$\mathrm{ex}(n,C_{2k+1})={n^{2}}/{4}+o(n^{2})$. In 1971, Bondy [21] and
Woodall [172] proved independently a more stronger result, which implies that
the extremal number for odd-length cycle is exactly equal to $n^{2}/4$; see
[15, p. 150] for more details.

######  Theorem 1.44 (Bondy [21]; Woodall [172]).

If $G$ is a graph on $n$ vertices with $e(G)>\lfloor{n^{2}}/{4}\rfloor$, then
$G$ contains a cycle of length $\ell$ for every
$\ell=3,4,\ldots,\lfloor{(n+3)}/{2}\rfloor$.

From this theorem, we can easily get the following corollary for the extremal
number of $C_{2k+1}$. This result can also be proved by the well-known
stability method for $n$ sufficiently large; see [98, Theorem 5.3] for more
details.

######  Corollary 1.45.

If $k\geq 1$ and $n\geq 4k+1$, then

$\mathrm{ex}(n,C_{2k+1})=\left\lfloor\frac{n^{2}}{4}\right\rfloor.$

A wheel $W_{n}$ is a graph on $n$ vertices obtained from $C_{n-1}$ by adding
one vertex $w$ and making $w$ adjacent to all vertices of the $C_{n-1}$. In
the language of join graph, we have

$W_{n}=K_{1}\vee C_{n-1}.$

It is easy to see that the vertex-chromatic number $\chi(W_{2k})=4$ and
$W_{2k}$ is color-critical, that is, there is an edge $e\in W_{2k}$ such that
$\chi(W_{2k}\setminus e)=3$. The Erdős–Stone–Simonovits Theorem 1.28 implies
that $\mathrm{ex}(n,W_{2k})=e(T_{3}(n))+o(n^{2})$. In 2013, Dzido proved the
exact Turán number by using Corollary 1.45.

######  Theorem 1.46 (Dzido [54]).

For all $k\geq 3$ and $n\geq 6k-10$, then

$\mathrm{ex}(n,W_{2k})=e(T_{3}(n))=\left\lfloor\frac{n^{2}}{3}\right\rfloor.$

For odd wheels, we know that $\chi(W_{2k+1})=3$ and the Erdős–Stone–Simonovits
Theorem 1.28 implies the asymptotic value
$\mathrm{ex}(n,W_{2k+1})=n^{2}/4+o(n^{2})$. We remark here that the exact
extremal number of odd wheels was recently determined by Yuan [182] for
sufficiently large $n$ by applying the stability method. The problem for odd
wheels is more complicated than that of even wheels since the odd wheels are
not color-critical.

In 2008, Nikiforov [139] proved an analogue of the Bondy–Woodall Theorem 1.44
in terms of the spectral radius for the existence of cycles with consecutive
lengths.

######  Theorem 1.47 (Nikiforov [139]).

Let $G$ be a graph of sufficiently large order $n$ with
$\lambda(G)>\sqrt{\left\lfloor{n^{2}}/{4}\right\rfloor}$. Then $G$ contains a
cycle of length $t$ for $t\leq{n}/{320}$.

The result is sharp because the complete bipartite graph $T_{2}(n)$ with parts
of size $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$ has no odd cycles, and its
largest eigenvalue is $\sqrt{\left\lfloor{n^{2}}/{4}\right\rfloor}$. Moreover,
it is clear that the constant $1/320$ in Theorem 1.47 can be increased even
with careful calculations in the Nikiforov methods. Thus, the following
question may arise:

######  Conjecture 1.48.

What is the maximum $C$ such that for all positive $\varepsilon<C$ and
sufficiently large $n$, every graph $G$ of order $n$ with
$\lambda(G)>\sqrt{\left\lfloor{n^{2}}/{4}\right\rfloor}$ contains a cycle of
length $t$ for every $t\leq(C-\varepsilon)n$.

It is known from Theorem 1.44 that if $G$ is a graph of order $n$ with
$e(G)>\left\lfloor{n^{2}}/{4}\right\rfloor$, then $G$ contains a cycle of
length $t$ for every $3\leq t\leq\lceil n/2\rceil$. Therefore, one can
conjecture that $C=1/2$. Unfortunately, this is not true by taking the join of
a complete graph of order $k$ and an empty graph of order $n-k$, we can obtain
a graph

$S_{n,k}=K_{k}\vee I_{n-k}.$

Setting $k=\lceil(3-\sqrt{5})n/4\rceil$, an easy calculation gives

$\lambda(S_{n,k})=\frac{k-1}{2}+\sqrt{kn-\frac{1}{4}(3k^{2}+2k-1)}>\frac{n}{2}\geq\left\lfloor\frac{n^{2}}{4}\right\rfloor.$

However, $S_{n,k}$ does not contain cycles longer than $2k\approx 0.382n<n/2$.
Recently, Ning and Peng [151] slightly refined this as $C=1/160$. Zhai and Lin
[188] improved these results to $C\geq 1/7$, and Li and Ning [113] proved that
$C\geq 1/4$ by applying a method different from previous ones.

As a consequence of Theorem 1.47, we can get the following corollary.

######  Corollary 1.49.

Let $k\geq 1$ and $G$ be a graph of sufficiently large order $n\geq 640k+320$.
If $G$ does not contain a copy of $C_{2k+1}$, then
$\lambda(G)\leq\sqrt{\left\lfloor{n^{2}}/{4}\right\rfloor}$.

For the extremal problems on the signless Laplacian spectral radius, the
following results on odd cycles are proved in [82] and [183].

######  Theorem 1.50 (Freitas–Nikiforov–Patuzzi [82]).

If $G$ is a graph on $n\geq 6$ vertices with no copy of $C_{5}$, then either
$q(G)<q(K_{2}\vee I_{n-2})$ or $G=K_{2}\vee I_{n-2}$.

In 2014, Yuan proved the general result for the signless Laplacian radius.

######  Theorem 1.51 (Yuan [183]).

Let $k\geq 3,n\geq 100k^{2}$ and $G$ be an $n$-vertex graph. If $G$ has no
copy of $C_{2k+1}$, then either $q(G)<q(K_{k}\vee I_{n-k})$ or $G=K_{k}\vee
I_{n-k}$.

Recall that $S_{n,k}=K_{k}\vee I_{n-k}$, it is not hard to show that

$q(S_{n,k})=\frac{n+2k-2+\sqrt{(n+2k-2)^{2}-8k(k-1)}}{2}.$

Note that the extremal graphs for spectral problem and signless Laplacian
spectral problem are different when we forbid the odd-length cycles, the
former is the balanced complete bipartite graph $T_{2}(n)$ and the latter is
the split graph $S_{n,k}$.

###  1.5 Spectral problem for even cycles

In this section, we shall review extremal problems involving the cycles of
even length. Note that even cycles are clearly bipartite, the Kővari–Sós–Turán
Theorem 1.32 implies that
$\mathrm{ex}(n,C_{2k})\leq\mathrm{ex}(n,K_{k,k})=O(n^{2-1/k})$ for every
integer $k\geq 2$.

There have abundant references of the study of $\mathrm{ex}(n,C_{4})$ in the
literature; see, e.g., [61, 28, 78]. By double counting method, Reiman showed
an upper bound that

$\mathrm{ex}(n,C_{4})\leq\frac{n}{4}(1+\sqrt{4n-3}).$ (5)

Furthermore, the equality holds if and only if every pair of vertices has
exactly one common neighbor. However, The well-known Friendship Theorem (see,
e.g., [61] or [3, Chapter 43]) states that if $G$ is an $n$-vertex graph in
which every pair of vertices has exactly one common neighbor, then $n$ is odd
and there is a vertex which is adjacent to all other vertices in $G$, i.e.,
$G=K_{1}\vee\frac{n-1}{2}K_{2}$. This implies that $e(G)={3(n-1)}/{2}$. Hence,
the equality in (5) never holds. Such graph $G$ is called the friendship graph
or the windmill graph.

Using orthogonal polarity graphs constructed from finite projective planes,
Erdős, Rényi and Sós [61] and Brown [28] proved a lower bound, which states
that

$\mathrm{ex}(n,C_{4})\geq\frac{1}{2}n^{\frac{3}{2}}+o(n^{\frac{3}{2}}).$

This result together with (5) implies the following asymptotic Turán number.

######  Theorem 1.52 (Erdős–Rényi–Sós, 1966).

$\mathrm{ex}(n,C_{4})=\frac{1}{2}n^{3/2}+o(n^{3/2})$.

We remark here that there are many constructions of graphs attaining this
lower bound asymptotically; see, e.g., [80]. We next include a famous
construction by using the projective plane over the finite field, which is now
known as the Erdős–Rényi projective polarity graph.

###### Proof.

Let $q$ be a prime power. Then the field of order $q$ exists and denoted by
$\mathbb{F}_{q}$. We consider the three-dimensional vector space
$\mathbb{F}_{q}^{3}$ over the field $\mathbb{F}_{q}$. Since space
$\mathbb{F}_{q}^{3}$ contains $q^{3}-1$ non-zero vectors, $q^{2}+q+1$ one-
dimensional subspaces and $q^{2}+q+1$ two-dimensional subspaces. Moreover,
each one-dimensional subspace contains $q-1$ nonzero vectors, every two
distinct one-dimensional subspaces intersect only in $(0,0,0)$. Furthermore,
each one-dimensional subspace is contained in $q+1$ two-dimensional subspaces,
and each two-dimensional subspace contains $q+1$ one-dimensional subspaces.
For every nonzero vector $\vec{a}=(a_{1},a_{2},a_{3})\in\mathbb{F}_{q}^{3}$,
let $A$ denote the one-dimensional subspace spanning by $\vec{a}$, that is,
$A:=\\{k(a_{1},a_{2},a_{3}):k\in\mathbb{F}_{q}\\}$.

Step 1. We now construct the desired graph $G$ whose vertices are all one-
dimensional subspaces of $\mathbb{F}_{q}^{3}$, that is,
$V(G)=\left\\{A=\mathrm{Span}\\{\vec{a}\\}:\vec{a}\in\mathbb{F}_{q}^{3}\right\\}$.
Therefore, we get $|V(G)|=\frac{q^{3}-1}{q-1}=q^{2}+q+1$. Let two vertices $A$
and $B$ be adjacent if and only if

$a_{1}b_{1}+a_{2}b_{2}+a_{3}b_{3}=0~{}(\text{over}~{}\mathbb{F}_{q}).$

This definition is clearly well-defined, in other words, it does not depend on
the choices of representative elements of the one-dimensional subspaces.

Next, we are going to count the number of edges. For each vertex
$A=\mathrm{Span}\\{\vec{a}\\}$, since $a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}=0$ has
$q^{2}-1$ nonzero solutions in $\mathbb{F}_{q}^{3}$, which forms exactly $q+1$
one-dimensional subspaces (vertices). Note that the graph $G$ may have loops
(the case $a_{1}^{2}+a_{2}^{2}+a_{3}^{2}=0$ is possible), we remove all loops
of $G$ to get a simple subgraph $\widetilde{G}$ on the same vertex set. Thus,

$d_{\widetilde{G}}(A)=\left\\{\begin{array}[]{ll}q,&\text{if}~{}a_{1}^{2}+a_{2}^{2}+a_{3}^{2}=0,\\\
q+1,&\text{otherwise}.\end{array}\right.$

Anyway, we have $d_{\widetilde{G}}(A)\geq q$ for every vertex $A$. Therefore,
we get

$e(\widetilde{G})=\frac{1}{2}\sum_{v\in V}d(v)\geq\frac{1}{2}(q^{2}+q+1)q.$

Step 2. We are going to prove that $\widetilde{G}$ is $K_{2,2}$-free.

Let $V$ and $W$ be two distinct vertices of $G$, if
$U=\mathrm{Span}\\{\vec{u}\\}$ is a common neighbor of $V$ and $W$, then
$u_{1},u_{2},u_{3}$ is a solution of the linear equations

$\begin{cases}v_{1}u_{1}+v_{2}u_{2}+v_{3}u_{3}=0,\\\
w_{1}u_{1}+w_{2}u_{2}+w_{3}u_{3}=0.\end{cases}$

Since $V$ and $W$ are two distinct one-dimensional subspaces, then the vectors
$(v_{1},v_{2},v_{3})$ and $(w_{1},w_{2},w_{3})$ are linearly independent,
which means that the space of solutions has dimension one. Hence the number of
common neighbors of $V$ and $W$ in $G$ is exactly one. Note that the unique
common neighbor of $V$ and $W$ in $G$ may be $V$ or $W$ itself, and we have
removed all loops from $G$ to obtain $\widetilde{G}$ so $V$ and $W$ is at most
one common neighbor in the loopless graph $\widetilde{G}$. For example, when
$q=2$, the vertices $\mathrm{Span}\\{(0,0,1)\\}$ and
$\mathrm{Span}\\{(1,1,0)\\}$ have the common neighbor
$\mathrm{Span}\\{(1,1,0)\\}$ in $G$. However, in the loopless graph
$\widetilde{G}$, $\mathrm{Span}\\{(0,0,1)\\}$ and $\mathrm{Span}\\{(1,1,0)\\}$
have no common neighbor.

Combining the above two steps, we conclude that

$\mathrm{ex}(q^{2}+q+1,K_{2,2})\geq
e(\widetilde{G})\geq\frac{1}{2}(q^{2}+q+1)q.$

By the denseness of the prime numbers, we get
$\mathrm{ex}(n,K_{2,2})=(\frac{1}{2}+o(1))n^{3/2}$ ∎

We mention here that the graph $\widetilde{G}$ constructed in the above is
called the Erős–Renyi projective polarity graph, and denoted by $ER_{q}$.
Furthermore, we can compute the exact number of edges of $ER_{q}$ by applying
the argument of the standard linear algebra method. More precisely, the graph
$ER_{q}$ has $q+1$ vertices with degree $q$, and $q^{2}$ vertices with degree
$q+1$. Consequently, we get

$e({ER_{q}})=\frac{1}{2}\bigl{(}(q+1)q+q^{2}(q+1)\bigr{)}=\frac{1}{2}(q+1)^{2}q.$

Generally speaking, determining the exact value of $\mathrm{ex}(n,C_{4})$
seems to be an extremely difficult problem and far beyond reach. In 1996,
Füredi [78] showed that for $n$ large enough with the form $n=q^{2}+q+1$, the
extremal number is attained by the polarity graph $ER_{q}$ of a projective
plane.

######  Theorem 1.53 (Füredi [78]).

Let $q\geq 15$ be a prime power. Then

$\mathrm{ex}(q^{2}+q+1,C_{4})=\frac{1}{2}q(q+1)^{2}.$

For the extremal number of $C_{6}$, the best possible is the following.

######  Theorem 1.54 (Füredi–Naor–Verstraëte [79]).

$0.5338n^{\frac{4}{3}}\leq\mathrm{ex}(n,C_{6})\leq 0.6272n^{\frac{4}{3}}.$

The asymptotic extremal number for $C_{8}$ remains open.

######  Conjecture 1.55.

Let $C_{8}$ be the cycle on $8$ vertices. Then

$\mathrm{ex}(n,C_{8})=\Theta(n^{\frac{5}{4}}).$

######  Theorem 1.56 (Lazebnik–Ustimenko–Woldar [109]).

$\mathrm{ex}(n,C_{10})\geq(4\cdot
5^{-\frac{6}{5}}+o(1))n^{\frac{6}{5}}\approx(0.5798+o(1))n^{\frac{6}{5}}.$

######  Theorem 1.57 (Bondy–Simonovits [26]).

If $G$ is an $n$-vertex graph with

$e(G)>100k\cdot n^{1+\frac{1}{k}},$

then $G$ contains a copy of $C_{2\ell}$ for every integer
$\ell\in[k,kn^{1/k}]$.

The Bondy–Simonovits theorem implies that $\mathrm{ex}(n,C_{2k})\leq
100kn^{1+1/k}$. Next, we shall list some improvements on this upper bound in
the literature.

  * •

(Verstraëte [168]) $\mathrm{ex}(n,C_{2k})\leq 8(k-1)n^{1+{1}/{k}}$.

  * •

(Pikhurko [157]) $\mathrm{ex}(n,C_{2k})\leq(k-1)n^{1+{1}/{k}}+16(k-1)n$.

  * •

(Bukh–Jiang [31]) $\mathrm{ex}(n,C_{2k})\leq 80\sqrt{k}\log k\cdot
n^{1+1/k}+O(n)$.

  * •

(He [89]) $\mathrm{ex}(n,C_{2k})\leq\bigl{(}16\sqrt{5}\sqrt{k\log
k}+o(1)\bigr{)}\cdot n^{1+1/k}$.

######  Conjecture 1.58 (Erdős–Simonovits, 1982).

$\mathrm{ex}(n,C_{2k})=\Theta(n^{1+\frac{1}{k}}).$

In the sequel, we shall review the results on extremal spectral problems for
even cycles. Let $n$ be an odd integer and $G=K_{1}\vee\frac{n-1}{2}K_{2}$ be
the friendship graph on $n$ vertices. By an easy calculation, we know that
$e(G)=\frac{3}{2}(n-1)$ and $\lambda(G)=\frac{1+\sqrt{4n-3}}{2}$.

######  Theorem 1.59 (Nikiforov [138]).

Let $G$ be a graph on $n$ vertices. If $G$ has no $4$-cycle $C_{4}$, then
$\lambda(G)\leq\frac{1+\sqrt{4n-3}}{2}$, equality holds if and only if $n$ is
odd and $G=K_{1}\vee\frac{n-1}{2}K_{2}$.

This theorem states that if $G$ is $C_{4}$-free, then

$\lambda(G)\leq\frac{1+\sqrt{4n-3}}{2}.$ (6)

This spectral result implies $\mathrm{ex}(n,C_{4})=O(n^{3/2})$ since the
inequality $\lambda(G)\geq 2m/n$.

The Friendship Theorem [3, Chapter 43] states that if $G$ is a graph on $n$
vertices such that every two distinct vertices have exactly one common
neighbor, then $n$ is odd and $G=K_{1}\vee\frac{n-1}{2}K_{2}$, a graph
obtained from $\frac{n-1}{2}$ triangles sharing a single common vertex. Such a
graph is usually called the friendship graph. The equality in Theorem 1.59 is
best possible only for $n$ odd, and Nikiforov’s result may be improved for
even $n$.

Erdős and Renyi showed that if $q$ is a prime power, then the polarity graph
$ER_{q}$ is $C_{4}$-free on $n=q^{2}+q+1$ vertices with
$e(ER_{q})=\frac{q(q+1)^{2}}{2}$. Thus, we have

$\lambda(ER_{q})\geq\frac{2e(ER_{q})}{n}=\frac{q(q+1)^{2}}{q^{2}+q+1}>q+1-\frac{1}{q}=\frac{1+\sqrt{4n-3}}{2}-\frac{1}{\sqrt{n}-1}.$

This lower bound is quite close to the upper bound in (6).

In 2012, Zhai and Wang improved the result of Nikiforov when $n$ is even.

######  Theorem 1.60 (Zhai–Wang [185]).

Let $G$ be a graph of even order $n$. If $G$ has no copy of $C_{4}$, then
$\lambda(G)\leq x_{0}$, where $x_{0}$ is the largest root of the equation

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

Moreover, the equality holds if and only if $G$ is a graph obtained from the
star $K_{1,n-1}$ by adding $\frac{n}{2}-1$ disjoint edges in its independent
set.

Let $K_{k}\vee I_{n-k}$ be the graph obtained by joining each vertex of
$K_{k}$ to $n-k$ isolated vertices of $I_{n-k}$, and let $K_{k}\vee
I_{n-k}^{+}$ be the graph obtained by adding one edge within the independent
set of $K_{k}\vee I_{n-k}$. We can see that

  * •

$C_{2k+1}\nsubseteq K_{k}\vee I_{n-k}$ and $C_{2k+2}\nsubseteq K_{k}\vee
I_{n-k}$.

  * •

$C_{2k+2}\nsubseteq K_{k}\vee I_{n-k}^{+}$.

######  Conjecture 1.61 (Nikiforov [146]).

Let $k\geq 2$ and $G$ be a graph of sufficiently large order $n$. If $G$ is
$C_{2k+2}$-free, then

$\lambda(G)\leq\lambda(K_{k}\vee I_{n-k}^{+}),$

equality holds if and only if $G=K_{k}\vee I_{n-k}^{+}$.

In 2020, Zhai and Lin [186] proved Conjecture 1.61 for the case $k=2$ and
$n\geq 23$.

######  Conjecture 1.62 (Nikiforov [146]).

Let $k\geq 2$ and $G$ be a graph of sufficiently large order $n$. If $G$ is
both $C_{2k+1}$-free and $C_{2k+2}$-free, then

$\lambda(G)\leq\lambda(K_{k}\vee I_{n-k}),$

equality holds if and only if $G=K_{k}\vee I_{n-k}$.

The case $k=1$ in Conjecture 1.62 was early proved by Favaron, Mahéo and Saclé
[65]. In 2012, Yuan, Wang and Zhai [184] proved conjecture 1.62 for the case
$k=2$ and $n\geq 6$. In 2019, Gao and Hou [86] proved a weaker conclusion than
Conjectures 1.61 and 1.62.

######  Theorem 1.63 (Gao–Hou [86]).

Let $k\geq 2$ and $G$ be a graph of order $n\geq 13k^{2}$. If $G$ does not
contain a cycle of length at least $2k+2$, then
$\lambda(G)\leq\lambda(K_{k}\vee I_{n-k}^{+})$, equality holds if and only if
$G=K_{k}\vee I_{n-k}^{+}$.

######  Theorem 1.64 (Gao–Hou [86]).

Let $k\geq 2$ and $G$ be a graph of order $n\geq 13k^{2}$. If $G$ does not
contain a cycle of length at least $2k+1$, then
$\lambda(G)\leq\lambda(K_{k}\vee I_{n-k})$, equality holds if and only if
$G=K_{k}\vee I_{n-k}$.

For odd $n$, we write $F_{n}$ for the friendship graph on $n$ vertices, that
is, $F_{n}=K_{1}\vee\frac{n-1}{2}K_{2}$; for even $n$, we write $F_{n}$ for
the graph obtained from $F_{n-1}$ by adding an extra edge hung to its center.
In other words, the $F_{n}$ can be viewed as a graph obtained from $K_{1,n-1}$
by adding a maximum matching within the independent set $I_{n-1}$. The
following result is an analogue of both Theorem 1.59 and Theorem 1.60 for the
signless Laplacian spectral radius.

######  Theorem 1.65 (Freitas–Nikiforov–Patuzzi [82]).

If $G$ is a graph on $n\geq 4$ vertices with no copy of $C_{4}$, then
$q(G)\leq q(F_{n})$, equality holds if and only if $G=F_{n}$.

In addition, Freitas et. al. [82] proposed a conjecture for forbidden even
cycles of length at least $6$, which was solved by Nikiforov and Yuan [148].

######  Theorem 1.66 (Nikiforov–Yuan [148]).

Let $k\geq 2,n\geq 400k^{2}$ and $G$ be a graph on $n$ vertices. If $G$ has no
copy of $C_{2k+2}$, then $q(G)\leq q(K_{k}\vee I_{n-k}^{+})$, equality holds
if and only if $G=K_{k}\vee I_{n-k}^{+}$.

###  1.6 Spectral problem for color-critical graphs

In this section, we shall review a special class of graphs, which is now known
as the color-critical graphs (also known as edge-color-critical graphs). The
definition is stated as below.

######  Definition 1.67.

Let $e$ be an edge of graph $F$. We say that $e$ is a color-critical edge if
$\chi(F-e)<\chi(F)$. We say that $F$ is color-critical if $F$ contains a
color-critical edge.

The following are some examples. Clearly, the complete graph $K_{r+1}$ is
color-critical and $\chi(K_{r+1})=r+1$. The odd cycle $C_{2k+1}$ is color-
critical and $\chi(C_{2k+1})=3$.

Let $G$ and $H$ be two graphs. The join of $G$ and $H$ is defined as a graph
$G\vee H$ obtained from the disjoint union $G\cup H$ by adding all edges
connecting every vertex of $G$ to every vertex of $H$. For example, the wheel
graph $W_{n}=K_{1}\vee C_{n-1}$ and the book graph
$B_{t}=K_{2}\vee\overline{K_{t}}$. In addition, we can also see that
$K_{s_{1},s_{2},\ldots,s_{r}}=I_{s_{1}}\vee
K_{s_{2},\ldots,s_{r}}=K_{s_{1},s_{2}}\vee K_{s_{3},\ldots,s_{r}}$.

######  Example 1.68 (The wheel graph).

Let $W_{2k}=K_{1}\vee C_{2k-1}$ be the wheel graph, a vertex that connects all
vertices of an odd cycle $C_{2k-1}$. Then $W_{2k}$ is color-critical and
$\chi(W_{2k})=4$. However, we can check that $W_{2k+1}=K_{1}\vee C_{2k}$ is
not color-critical.

Moreover, for integer $s\geq 2$, we define $W_{s,m}:=K_{s}\vee C_{m}$ as the
generalized wheel graph. Since $s\geq 2$, the generalized wheel graph
$W_{s,m}$ is always color-critical. Moreover, we have $\chi(W_{s,2k-1})=s+3$
and $\chi(W_{s,2k})=s+2$.

######  Example 1.69 (The book graph).

Let $B_{k}=K_{2}\vee I_{k-2}$ be the book graph, that is, $k$ triangles
sharing a common edge. Then $B_{k}$ is color-critical and $\chi(B_{k})=3$.

To extend the above result, we can consider the extremal number of the
generalized book graph $B_{s,t}:=K_{s}\vee\overline{K_{t}}$ for some integer
$s\geq 3$. This graph can also be viewed as $t$ cliques $K_{s+1}$ sharing a
common sub-clique $K_{s}$. We can see that $B_{s,t}$ is color-critical and
$\chi(B_{s,t})=s+1$.

On the other hand, the book graph $B_{t}$ is defined as the $t$ triangles
sharing a common edge. Let $SE_{G,t}$ be the graph obtained from $t$ copies of
$G$ by sharing a common edge. We can extend this definition to $t$ cliques
$K_{r}$ sharing a common edge. It is easy to see that $SE_{K_{r},t}$ is color-
critical and $\chi(SE_{K_{r},t})=r$. In addition, we also can extend the book
graph to $t$ odd-length cycles $C_{2k+1}$ sharing a common edge. It is clear
that $SE_{C_{2k+1},t}$ is a color-critical graph and
$\chi(SE_{C_{2k+1},t})=3$.

Let $K_{1,1,n_{3},\ldots,n_{r}}$ be the complete $r$-partite graph with two
parts of order $1$ and other parts of order $n_{i}$ for each $i\in[3,r]$. Then
$K_{1,1,n_{3},\ldots,n_{r}}$ is color-critical and
$\chi(K_{1,1,n_{3},\ldots,n_{r}})=r$. Note that $SE_{K_{r},t}\subseteq
K_{1,1,t,\ldots,t}$. Let $K_{r}(s_{1},s_{2},\ldots,s_{r})$ be the complete
$r$-partite graph on the vertex sets $V_{1}$, $V_{2}$, $\ldots,V_{s}$, where
each part $V_{i}$ has $s_{i}$ vertices.

######  Example 1.70.

Let $s_{1}\geq 2$ be an integer. We write
$K_{r}^{+}(s_{1},s_{2},\ldots,s_{r})$ for the graph obtained from
$K_{r}(s_{1},s_{2},\ldots,s_{r})$ by adding an edge within the part $V_{1}$.
It is easy to see that $K_{r}^{+}(s_{1},s_{2},\ldots,s_{r})$ is color-critical
and $\chi=r+1$.

It is important that for any color-critical graph $G$ with $\chi(G)=r+1$,
there exist some integers $s_{1},\ldots,s_{r}$ such that $G$ is a subgraph of
$K_{r}^{+}(s_{1},s_{2},\ldots,s_{r})$.

The famous Erdős–Stone–Simonovits Theorem 1.28 states that if $F$ is a graph
with the vertex-chromatic number $\chi(F)=r+1$, then

$t_{r}(n)\leq\mathrm{ex}(n,F)=\left(1-\frac{1}{r}\right)\frac{n^{2}}{2}+o(n^{2})=t_{r}(n)+o(n^{2}).$

In previous section, we have proved that for some special graphs, we can
remove the error term $o(n^{2})$. For example, the Turán Theorem 1.3 states
that $\mathrm{ex}(n,K_{r+1})=t_{r}(n)$, the Bondy–Woodall Theorem 1.44 implies
that $\mathrm{ex}(n,C_{2k+1})=t_{2}(n)$ holds for $n\geq 4k+1$, and the Dzido
Theorem 1.46 states that $\mathrm{ex}(n,W_{2k})=t_{3}(n)$ holds for $n\geq
6k-10$. Moreover, a result of Edwards [55], and Khadžiivanov–Nikiforov [100]
independently implies that $\mathrm{ex}(n,B_{k})=t_{2}(n)$ holds for $n\geq
6k$; see, e.g., [16, 18, 19] for more details.

In what follows, we present a more general result proved by Simonovits.

######  Theorem 1.71 (Simonovits [159]).

Let $F$ be a graph with $\chi(F)=r+1$ where $r\geq 2$. If $F$ is color-
critical, then for sufficiently large $n$,

$\mathrm{ex}(n,F)=t_{r}(n).$

Moreover, the unique extremal graph is Turán graph $T_{r}(n)$.

In 2009, Nikiforov [144] extended Theorem 1.71 by showing that there is
$n_{0}$ such that if $G$ has $n\geq n_{0}$ vertices and
$\lambda(G)>\lambda(T_{r}(n))$, then $G$ contains a copy of the complete
$r$-partite graph with parts of size $\Omega(\ln n)$ plus an extra edge.

######  Theorem 1.72 (Nikiforov [144]).

Let $r\geq 2$ and $2/\ln n\leq c\leq 1/r^{(2r+9)(r+1)}$. If $G$ is a graph on
$n$ vertices with $\lambda(G)>\lambda(T_{r}(n))$, then $G$ contains a copy of

$K_{r}^{+}(\lfloor c\ln n\rfloor,\ldots,\lfloor c\ln n\rfloor,\lceil
n^{1-\sqrt{c}}\rceil).$

As a consequence of Theorem 1.72, we can easily get the following corollary.

######  Corollary 1.73.

If $F$ is color-critical and $\chi(F)=r+1$ where $r\geq 2$, then

$\boxed{\mathrm{ex}_{\lambda}(n,F)=\lambda(T_{r}(n))}$

holds for sufficiently large $n$, and the unique extremal graph is $T_{r}(n)$.

In 2014, Kang and Nikiforov [96, Theorem 6], and Keevash, Lenz and Mubayi [99,
Corollary 1.5] independently extended the above spectral version in Corollary
1.73 to the $p$-spectral radius $\lambda^{(p)}(G)$ for every $p>1$, where
$\lambda^{(p)}(G):=\max\\{\bm{x}^{T}A(G)\bm{x}:\bm{x}\in\mathbb{R}^{n},\lVert\bm{x}\rVert_{p}=1\\}$.

###  1.7 Spectral problem for intersecting triangles

Let $F_{k}$ denote the $k$-fan graph which is the graph consisting of $k$
triangles that intersect in exactly one common vertex. Note that $F_{k}$ has
$2k+1$ vertices. This notation is slightly different from that in Section 1.5.
This graph is known as the friendship graph because it is the only extremal
graph in the well-known Friendship Theorem [3, Chapter 43]. Since
$\chi(F_{k})=3$, the Erdős–Stone–Simonovits Theorem 1.28 implies that
$\mathrm{ex}(n,F_{k})=n^{2}/4+o(n^{2})$. In 1995, Erdős, Füredi, Gould and
Gunderson [64] proved the following exact result.

######  Theorem 1.74 (Erdős et al. [64]).

For every $k\geq 1$ and $n\geq 50k^{2}$, we have

$\mathrm{ex}(n,F_{k})=\left\lfloor\frac{n^{2}}{4}\right\rfloor+\left\\{\begin{array}[]{ll}k^{2}-k,\quad~{}~{}\mbox{if
$k$ is odd,}\\\ k^{2}-\frac{3}{2}k,\quad\mbox{if $k$ is
even}.\end{array}\right.$

The extremal graphs of Theorem 1.74 are as follows. For odd $k$ (where $n\geq
4k-1$), the extremal graphs are constructed by taking $T_{2}(n)$, the balanced
complete bipartite graph, and embedding two vertex disjoint copies of $K_{k}$
in one side. For even $k$ (where now $n\geq 4k-3$), the extremal graphs are
constructed by taking $T_{2}(n)$ and embedding a graph with $2k-1$ vertices,
$k^{2}-\frac{3}{2}k$ edges with maximum degree $k-1$ in one side.

The $(k,r)$-fan is the graph consisting of $k$ copies of the clique $K_{r}$
which intersect on a single vertex, and is denoted by $F_{k,r}$. Note that
$\chi(F_{k,r})=r$. Similarly, the Erdős–Stone–Simonovits theorem also implies
that
$\mathrm{ex}(n,F_{k,r})=(1-\frac{1}{r-1})\frac{n^{2}}{2}+o(n^{2})=t_{r-1}(n)+o(n^{2})$.
In 2003, Chen, Gould, Pfender and Wei [35] proved an exact answer and
generalized Theorem 1.74 as follows.

######  Theorem 1.75 (Chen et al. [35]).

For every $k\geq 1$ and $r\geq 3$, if $n\geq 16k^{3}r^{8}$, then

$\mathrm{ex}(n,F_{k,r})=t_{r-1}(n)+\left\\{\begin{array}[]{ll}k^{2}-k,\quad~{}~{}\mbox{if
$k$ is odd,}\\\ k^{2}-\frac{3}{2}k,\quad\mbox{if $k$ is
even}.\end{array}\right.$

The extremal graphs of Theorem 1.75 are constructed by taking the
$(r-1)$-partite Turán graph $T_{r-1}(n)$ and embedding a graph $G_{0}$ in one
vertex part, denoted by $G_{n,k,r}$. If $k$ is odd, $G_{0}$ is isomorphic to
two vertex disjoint copies of $K_{k}$. If $k$ is even, $G_{0}$ is isomorphic
to the graph with $2k-1$ vertices, $k^{2}-\frac{3}{2}k$ edges with maximum
degree $k-1$.

Let $C_{k,q}$ be the graph consisting of $k$ cycles of length $q$ which
intersect exactly in one common vertex. Clearly, when we set $q=3$, then
$C_{k,3}$ is just the $k$-fan graph; see Theorem 1.74. When $q$ is an odd
integer, we can see that $\chi(C_{k,q})=3$, the Erdős–Stone–Simonovits theorem
also implies that $\mathrm{ex}(n,C_{k,q})=n^{2}/4+o(n^{2})$. In 2016, Hou, Qiu
and Liu [93] determined exactly the extremal number for $C_{k,q}$ with $k\geq
1$ and odd integer $q\geq 5$.

######  Theorem 1.76 (Hou–Qiu–Liu [93]).

For an integer $k\geq 1$ and an odd integer $q\geq 5$, there exists
$n_{0}(k,q)$ such that for all $n\geq n_{0}(k,q)$, we have

$\mathrm{ex}(n,C_{k,q})=\left\lfloor\frac{n^{2}}{4}\right\rfloor+(k-1)^{2}.$

The extremal graphs are a Turán graph $T_{2}(n)$ with a $K_{k-1,k-1}$
embedding into one class.

We remark here that when $q$ is even, then $C_{k,q}$ is a bipartite graph
where every vertex in one of its parts has degree at most $2$. For such a
sparse bipartite graph, a classical result of Füredi [75] or Alon, Krivelevich
and Sudakov [6] implies that $\mathrm{ex}(n,C_{k,q})=O(n^{3/2})$. Recently, a
breakthrough result of Conlon, Lee and Janzer [48, 49] shows that for even
$q\geq 6$ and $k\geq 1$, we have $\mathrm{ex}(n,C_{k,q})=O(n^{3/2-\delta})$
for some $\delta=\delta(k,q)>0$. It is a challenging problem to determine the
value $\delta(k,q)$. For instance, the special case $k=1$, this problem
reduces to determine the extremal number for even cycle.

Next, we introduce a unified extension of both Theorems 1.74 and 1.76. Let $s$
be a positive integer and $t_{1},\ldots,t_{k}\geq 5$ be odd integers. We write
$H_{s,t_{1},\ldots,t_{k}}$ for the graph consisting of $s$ triangles and $k$
odd cycles of lengths $t_{1},\ldots,t_{k}$ in which these triangles and cycles
intersect in exactly one common vertex. The graph $H_{s,t_{1},\ldots,t_{k}}$
is also known as the flower graph with $s+k$ petals. We remark that the $k$
odd cycles can have different lengths. Clearly, when $t_{1}=\cdots=t_{k}=0$,
then $H_{s,0,\ldots,0}=F_{s}$, the $s$-fan graph; see Theorem 1.74. In
addition, when $s=0$ and $t_{1}=\cdots=t_{k}=q$, then
$H_{0,q,\ldots,q}=C_{k,q}$; see Theorem 1.76.

In 2018, Hou, Qiu and Liu [94] and Yuan [181] independently determined the
extremal number of $H_{s,k}$ for $s\geq 0$ and $k\geq 1$. Let
$\mathcal{F}_{n,s,k}$ be the family of graphs with each member being a Turán
graph $T_{2}(n)$ with a graph $H$ embedded in one partite set, where

$H=\begin{cases}K_{s+k-1,s+k-1},&\text{if $(s,k)\neq(3,1)$,}\\\
K_{3,3}~{}\text{or}~{}3K_{3},&\text{if $(s,k)=(3,1)$,}\end{cases}$

where $3K_{3}$ is the union of three disjoint triangles.

######  Theorem 1.77 (Hou–Qiu–Liu [94]; Yuan [181]).

For every graph $H_{s,t_{1},\ldots,t_{k}}$ with $s\geq 0$ and $k\geq 1$, there
exists $n_{0}$ such that for all $n\geq n_{0}$, we have

$\mathrm{ex}(n,H_{s,t_{1},\ldots,t_{k}})=\left\lfloor\frac{n^{2}}{4}\right\rfloor+(s+k-1)^{2}.$

Moreover, the only extremal graphs for $H_{s,t_{1},\ldots,t_{k}}$ are members
of $\mathcal{F}_{n,s,k}$.

Another interesting problem on this topic is to determine the Turán number of
$C_{k,q}$ for even $q$. More general, it is challenging to determine the Turán
number of $H_{s,k}$ where the cycles have even lengths.

Recall that $\mathrm{Ex}(n,F)$ denotes the set of graphs that contain no copy
of $F$ and have maximum number of edges. For example, the Turán theorem gives
$\mathrm{Ex}(n,K_{r+1})=\\{T_{r}(n)\\}$ for every $r\geq 2$, and the
Simonovits theorem yields that for every fixed color-critical graph $F$ with
$\chi(F)=r+1\geq 3$, we have $\mathrm{Ex}(n,F)=\\{T_{r}(n)\\}$ for
sufficiently large $n$. In 2020, Cioabă, Feng, Tait and Zhang [42] proved the
spectral version of Theorem 1.74.

######  Theorem 1.78 (Cioabă et al. [42]).

Let $k\geq 2$ and $G$ be a graph of order $n$ that does not contain a copy of
$F_{k}$. For sufficiently large $n$, if $G$ has the maximal spectral radius,
then

$G\in\mathrm{Ex}(n,F_{k}).$

In 2021, it was proved by Li and Peng in [115] that the spectral version of
intersecting odd cycles is also similar. Soon after, Desai, Kang, Li, Ni, Tait
and Wang [50] proved the analogous result for intersecting cliques.

######  Theorem 1.79 (Li–Peng [115]).

Let $G$ be a graph of order $n$ that does not contain a copy of
$H_{s,t_{1},\ldots,t_{k}}$, where $s\geq 0$ and $k\geq 1$. For sufficiently
large $n$, if $G$ has the maximal spectral radius, then

$G\in\mathrm{Ex}(n,H_{s,t_{1},\ldots,t_{k}}).$

######  Theorem 1.80 (Desai et al. [50]).

Let $G$ be a graph of order $n$ that does not contain a copy of $F_{k,r}$,
where $k\geq 1$ and $r\geq 2$. For sufficiently large $n$, if $G$ has the
maximal spectral radius, then

$G\in\mathrm{Ex}(n,F_{k,r}).$

Recently, Cioabă, Desai and Tait [43] investigated the largest spectral radius
of an $n$-vertex graph that does not contain the odd-wheel graph $W_{2k+1}$,
which is the graph obtained by joining a vertex to a cycle of length $2k$.
Moreover, they raised the following more general conjecture.

######  Conjecture 1.81.

Let $F$ be any graph such that the graphs in $\mathrm{Ex}(n,F)$ are Turán
graphs plus $O(1)$ edges. Then for sufficiently large $n$, a graph attaining
the maximum spectral radius among all $F$-free graphs is a member of
$\mathrm{Ex}(n,F)$.

Recall that $F$ is called edge-color-critical if there exists an edge $e$ of
$F$ such that $\chi(F-e)<\chi(F)$. Let $F$ be an edge-color-critical graph
with $\chi(F)=r+1$. By a result of Simonovits [159] and a result of Nikiforov
[144] or Keevash et al. [99], we know that
$\mathrm{Ex}(n,F)=\mathrm{Ex}_{\lambda}(n,F)=\\{T_{r}(n)\\}$ for sufficiently
large $n$, this shows that Conjecture 1.81 is true for all edge-color-critical
graphs. As we mentioned before, Theorems 1.78, 1.80 and 1.79 say that
Conjecture 1.81 holds for the $k$-fan graph $F_{k}$, the $(k,r)$-fan graph
$F_{k,r}$ and the intersecting odd cycle $H_{s,t_{1},\ldots,t_{k}}$. Note that
these graphs $F_{k},F_{k,r}$ and $H_{s,t_{1},\ldots,t_{k}}$ are not edge-
color-critical.

Recall that $S_{n,k}=K_{k}\vee I_{n-k}$. Clearly, we can see that $S_{n,k}$
does not contain $F_{k}$ as a subgraph. Recently, Zhao, Huang and Guo [194]
proved that $S_{n,k}$ is the unique graph attaining the maximum signless
Laplacian spectral radius among all graphs of large order $n$ containing no
copy of $F_{k}$.

######  Theorem 1.82 (Zhao–Huang–Guo [194]).

Let $k\geq 2$ and $n\geq 3k^{2}-k-2$. If $G$ is an $n$-vertex graph that does
not contain a copy of $F_{k}$, then $q(G)\leq q(S_{n,k})$, with equality
holding if and only if $G=S_{n,k}$.

It is worth mentioning that the extremal graphs in Theorem 1.82 are not the
same as those of Theorem 1.78. In addition, for $k=1$, i.e., $G$ is triangle-
free, from Theorem 1.24 we know that $q(G)\leq n$, equality holds if and only
if $G$ is a complete bipartite graph.

It is a natural question to consider the maximum signless Laplacian spectral
radius among all graphs containing no copy of $C_{k,q}$ or
$H_{s,t_{1},\ldots,t_{k}}$

When the paper [115] was announced (arXiv:2106.00587), Chen, Liu and Zhang
[38] proved quickly the signless Laplacian spectral version for $C_{k,q}$.
More generally, they showed the result for graph $H_{s,t_{1},\ldots,t_{k}}$
for odd integers $t_{1},\ldots,t_{k}$.

######  Theorem 1.83 (Chen–Liu–Zhang [38]).

For integers $k\geq 2,t\geq 1$ and $q=2t+1$, there exists an integer $n_{0}$
such that if $n\geq n_{0}$ and $G$ is a $C_{k,q}$-free graph on $n$ vertices,
then

$q(G)\leq q(S_{n,kt}),$

equality holds if and only if $G=S_{n,kt}$.

It is natural to ask the following problem, which is the signless Laplacian
spectral version of the extremal problem for intersecting cliques. Clearly,
when $r=3$, our conjecture reduces to the result of Zhao et al. [194].

######  Conjecture 1.84.

For integers $k\geq 1$ and $r\geq 3$, there exists an integer $n_{0}(k,r)$
such that if $n\geq n_{0}(k,r)$ and $G$ is a $F_{k,r}$-free graph on $n$
vertices, then

$q(G)\leq q(S_{n,k(r-2)}),$

equality holds if and only if $G=S_{n,k(r-2)}$.

##  2 Spectral problem for Hamiltonianity

A cycle passing through all vertices of a graph is called a Hamilton cycle. A
graph containing a Hamilton cycle is called a Hamiltonian graph. A path
passing through all vertices of a graph is called a Hamilton path and a graph
containing a Hamilton path is said to be traceable.

Every complete graph on at least three vertices is evidently Hamiltonian.
Indeed, the vertices of a Hamilton cycle can be selected one by one in an
arbitrary order. But suppose that our graph has considerably fewer edges. In
particular, we may ask how large the minimum degree must be in order to
guarantee the existence of a Hamilton cycle. The celebrated Dirac theorem [53]
answers this question. It states that every graph with $n\geq 3$ vertices and
minimum degree at least $n/2$ has a Hamilton cycle. The condition is sharp
when we consider the complete bipartite graph with the parts of sizes
$\lfloor\frac{n-1}{2}\rfloor$ and $\lfloor\frac{n+1}{2}\rfloor$.

The closure operation introduced by Bondy and Chvátal [23] is a powerful tool
for the problems of Hamiltonicity of graphs. Let $G$ be a graph of order $n$.
The $s$-closure of $G$, denoted by $\mathrm{cl}_{s}(G)$, is the graph obtained
from $G$ by recursively joining pairs of non-adjacent vertices whose degree
sum is at least $s$ until no such pair remains. It is not hard to prove that
the $s$-closure of $G$ is uniquely determined; see, e.g., [23]. Clearly, if
$G$ contains a Hamilton cycle, then so does $\mathrm{cl}_{s}(G)$ for every $s$
since $G$ is a subgraph of $\mathrm{cl}_{s}(G)$. Surprisingly, Ore [155]
proved that both $\mathrm{cl}_{n}(G)$ and $G$ keep in line with the existence
of Hamilton cycle.

######  Theorem 2.1 (Ore [155]).

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

The proof is simple and similar with that of the Dirac theorem, so we here
conclude the proof briefly. Without loss of generality, we only consider the
case $\mathrm{cl}_{n}(G)=G+uv$, where $d_{G}(u)+d_{G}(v)\geq n$. If $G+uv$ is
Hamiltonian, then $G$ has a Hamiltonian path $u=u_{1},u_{2},\ldots,u_{n}=v$.
We denote by $S=\\{i:uu_{i+1}\in E(G)\\}$ and $T=\\{i:u_{i}v\in E(G)\\}$.
Clearly, we have $|S|=d_{G}(u)$ and $|T|=d_{G}(v)$. Note that $u_{n}\notin
S\cup T$, which implies that $|S\cup T|\leq n-1$. Since $d_{G}(u)+d_{G}(v)\geq
n$, we can get $|S\cap T|=|S|+|T|-|S\cup T|\geq d_{G}(u)+d_{G}(v)-(n-1)\geq
1$. Thus there must be some $i$ such that $u$ is adjacent to $u_{i+1}$ and $v$
is adjacent to $u_{i}$, which implies that $G$ has the Hamilton cycle
$u_{1}u_{i+1}u_{i+2}\cdots u_{n}u_{i}u_{i-1}\cdots u_{1}$.

In 1972, Chvátal [40] proved the following theorem, which characterizes the
degree sequence of Hamiltonian graph. Theorem 2.2 becomes a classic conclusion
in many comprehensive textbooks; see [25, pp. 485–488] or [174, pp. 288–290]
or [52, pp. 308–312] for more details.

######  Theorem 2.2 (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$ is not Hamiltonian, then there exists an
integer $i<{n}/{2}$ such that $d_{i}\leq i$ and $d_{n-i}\leq n-i-1$.

The following result is due to Ore [155] and Bondy [22] independently. It is a
direct consequence of the Chvátal theorem; see [24, p. 60] for more details.

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

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

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

then $G$ has a Hamilton cycle unless $G=K_{1}\vee(K_{1}\cup K_{n-2})$ or $n=5$
and $G=K_{2}\vee I_{3}$.

In 1962, Erdős improved the above result for graphs with given minimum degree.

######  Theorem 2.4 (Erdős [58]).

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

$e(G)>\max\left\\{{n-\delta\choose
2}+\delta^{2},{n-\lfloor\\!\frac{n-1}{2}\\!\rfloor\choose
2}+\left\lfloor\\!\frac{n-1}{2}\\!\right\rfloor^{2}\right\\},$

then $G$ has a Hamilton cycle.

When $n\geq 6\delta$, we have $e(H_{n,\delta})\geq
e(H_{n,\lfloor{(n-1)}/{2}\rfloor})$. Thus, we get the following corollary.

######  Corollary 2.5 (Erdős).

Let $k\geq 1$ and $n\geq 6\delta$. If $G$ is an $n$-vertex graph with
$\delta(G)\geq\delta$ and $e(G)\geq e(H_{n,\delta})$, then either $G$ has a
Hamilton cycle or $G=H_{n,\delta}$.

We mention here that $f(\delta)={n-\delta\choose 2}+\delta^{2}$ is decreasing
with respect to $\delta$ for fixed $n\geq 6\delta$. It is sufficient to prove
the theorem under the condition $\delta(G)=\delta$. Indeed, if $G$ satisfies
$\delta(G)=t>\delta$ and $e(G)>f(\delta)$, then we have $e(G)>f(t)$. The
special case $\delta(G)=t$ can deduce the general case $\delta(G)>\delta$.
Hence, the condition can be reduced to $\delta(G)=\delta$.

To see the sharpness of the bound in Theorem 2.4, we consider the graph
$H_{n,\delta}$ obtained from a copy of $K_{n-\delta}$ by adding an independent
set of $\delta$ vertices with degree $\delta$ each of which is adjacent to the
same $\delta$ vertices in $K_{n-\delta}$. In the language of graph join and
union, that is,

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

Clearly, we can verify that $\delta(H_{n,\delta})=\delta$ and $H_{n,\delta}$
does not contain Hamilton cycle. Moreover, we have
$e(H_{n,\delta})={n-\delta\choose 2}+\delta^{2}$ and
$\lambda(H_{n,\delta})>\lambda(K_{n-\delta})=n-\delta-1$ since $K_{n-\delta}$
is a proper subgraph of $H_{n,\delta}$.

###  2.1 Spectral results for Hamilton cycle

In 2010, Fiedler and Nikiforov proved a spectral version of Theorem 2.3.

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

If $G$ is a graph on $n\geq 3$ vertices and

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

then either $G$ has a Hamilton cycle or $G=K_{1}\vee(K_{1}\cup K_{n-2})$.

This spectral result can easily be deduced from Theorem 2.3.

###### Proof.

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

In 2013, Yu and Fan [177] gave the corresponding spectral version for the
signless Laplacian radius. Recall that $q(G)$ stands for the signless
Laplacian spectral radius, i.e., the largest eigenvalue of the signless
Laplacian matrix $Q(G)=D(G)+A(G)$, where
$D(G)=\mathrm{diag}(d_{1},\ldots,d_{n})$ is the degree diagonal matrix and
$A(G)$ is the adjacency matrix.

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

If $G$ is a graph on $n\geq 3$ vertices and

$q(G)>2(n-2),$

then $G$ has a Hamilton cycle or $G=K_{1}\vee(K_{1}\cup K_{n-2})$, or $n=5$
and $G=K_{2}\vee I_{3}$.

In [177], the counterexample of $n=5,G=K_{2}\vee I_{3}$ is missed. This tiny
flaw has already been pointed out by Liu et al. [129] and by Li and Ning [111]
as well.

###### Proof.

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

Observing that a graph $G$ with minimum degree $\delta(G)=1$ does not contain
Hamilton cycle. Thus $\delta(G)\geq 2$ is a trivial necessary condition for
$G$ to be Hamiltonian. In 2015, Ning and Ge [150] refined the extremal result
of Ore and the spectral result of Fiedler and Nikiforov for graphs with
minimum degree at least two.

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

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

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

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

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

Let $n\geq 14$ be an integer. If $G$ is a graph on $n$ vertices with minimum
degree $\delta(G)\geq 2$ and

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

then either $G$ has a Hamilton cycle or $G=K_{2}\vee(K_{n-4}\cup I_{2})$.

Upon some computations, we can find the following exceptions: when $n=7$,
$K_{3}\vee I_{4}$ is an exception that contains no Hamilton cycle since
$\lambda(K_{3}\vee I_{4})=1+\sqrt{13}\approx 4.605>\lambda(K_{2}\vee(K_{3}\cup
I_{2}))\approx 4.404$; when $n=9$, $K_{4}\vee I_{5}$ contains no Hamilton
cycle and $\lambda(K_{4}\vee I_{5})=\frac{3+\sqrt{89}}{2}\approx
6.217>\lambda(K_{2}\vee(K_{5}\cup I_{2}))\approx 6.197$. Moreover, Ning and Ge
[150] conjecture that the bound $n\geq 14$ in Theorem 2.9 can be sharpened to
$n\geq 10$. Soon after, Chen, Hou and Qian [36, Theorem 1.6] proved that
Theorem 2.9 holds for every integer $n\geq 10$.

In addition, Chen et al. [36] also proved the version for the signless
Laplacian radius.

######  Theorem 2.10 (Chen–Hou–Qian [36]).

Let $n\geq 11$ be an integer. If $G$ is a graph on $n$ vertices with minimum
degree $\delta(G)\geq 2$ and

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

then $G$ has a Hamilton cycle unless $G=K_{2}\vee(K_{n-4}\cup I_{2})$.

In 2016, Benediktovich [10] improved slightly the result of Ning and Ge.

######  Theorem 2.11 (Benediktovich [10]).

Let $G$ be a graph on $n\geq 8$ vertices with $\delta\geq 2$. If

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

then $G$ has a Hamilton cycle unless $G=K_{2}\vee(K_{n-4}\cup I_{2})$ or
$G=K_{1}\vee(K_{n-3}\cup K_{2})$, or $n=9$, there are two more exceptions
$G\in\\{I_{5}\vee K_{4},K_{3}\vee(K_{1,4}\cup K_{1})\\}$.

By an easy computation, we know that $\lambda(I_{5}\vee
K_{4})=\frac{3+\sqrt{89}}{2}\approx 6.217$ and $\lambda(K_{3}\vee(K_{1,4}\cup
K_{1}))\approx 6.032$. These two graphs do not contain Hamilton cycle.

By introducing the minimum degree of a graph as a new parameter, Li and Ning
[111, Theorems 1.5, 1.8] obtained the spectral analogue of the result of Erdős
(Corollary 2.5).

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

Suppose $\delta\geq 1$ and
$n\geq\max\\{6\delta+5,(\delta^{2}+6\delta+4)/2\\}$. If $G$ is an $n$-vertex
graph with $\delta(G)\geq\delta$ and

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

then either $G$ has a Hamilton cycle or $G=H_{n,\delta}$.

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

Suppose $\delta\geq 1$ and
$n\geq\max\\{6\delta+5,(3\delta^{2}+5\delta+4)/2\\}$. If $G$ is an $n$-vertex
graph with $\delta(G)\geq\delta$ and

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

then either $G$ has a Hamilton cycle or $G=H_{n,\delta}$.

Clearly, Theorem 2.12 and Theorem 2.13 extended Theorem 2.9 and Theorem 2.10
for sufficiently large $n$, respectively. Although Theorem 2.12 and Theorem
2.13 are algebraic, their proofs need some detailed graph structural analysis.
The key part of the proof of these theorems attributes to the stability result
for Hamilton cycle.

Soon after, Nikiforov [149, Theorem 1.4] further proved the following result,
which improved Theorem 2.12. Recall that
$H_{n,\delta}=K_{\delta}\vee(K_{n-2\delta}\cup I_{\delta})$ is not Hamiltonian
and $\delta(H_{n,\delta})=\delta$. For notational convenience, we need to
introduce a new graph. We denote

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

Trivially, the case $\delta=1$ yields $H_{n,1}=L_{n,1}=K_{1}\vee(K_{n-2}\cup
K_{1})$. We can observe that $L_{n,\delta}$ does not contain Hamilton cycles
and $\delta(L_{n,\delta})=\delta$. Moreover, we have
$e(L_{n,\delta})={n-\delta\choose 2}+{\delta+1\choose 2}$ and
$\lambda(L_{n,\delta})>\lambda(K_{n-\delta})=n-\delta-1$.

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

Suppose that $\delta\geq 1$ and $n\geq\delta^{3}+\delta+4$. If $G$ is an
$n$-vertex graph with $\delta(G)\geq\delta$ and

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

then $G$ has a Hamilton cycle, or $G=H_{n,\delta}$, or $G=L_{n,\delta}$.

Note that $\lambda(H_{n,\delta})>\lambda(K_{n-\delta})=n-\delta-1$, so the
condition in Theorem 2.14 is weaker and succincter than that in Theorem 2.12.
Moreover, we can show that $e(H_{n,\delta})>e(L_{n,\delta})$ and
$\lambda(H_{n,\delta})>\lambda(L_{n,\delta})$. Theorem 2.14 is a unified
improvement on Theorem 2.11) as well as Theorem 2.12. Indeed, we can easily
see that $\lambda(H_{n,\delta})>n-\delta-1$. Furthermore, by applying the
Kelmans operation, we get $\lambda(H_{n,\delta})>\lambda(L_{n,\delta})$; see
[111, Lemma 6] for more details.

Although Theorem 2.14 is indeed a generalization of Theorem 2.12.
Unfortunately, one dissatisfaction in Theorem 2.14 is that the requirement of
the order of graph is stricter than that in Theorem 2.12. One open problem is
to relax this requirement. In fact, by a tiny modification of the proof of
Theorem 2.12 in [111], we can prove that if $G$ is non-Hamiltonian and
$\lambda(G)\geq n-\delta-1$, then $e(G)>e(H_{n,\delta+1})$. The stability
result (see [111, Lemma 2]) implies that $G$ is a subgraph of $H_{n,\delta}$
and $L_{n,\delta}$. As pointed out by Nikiforov [149], the crucial point of
the argument of Theorem 2.14 is based on proving that for large
$n\geq\delta^{3}+\delta+4$, if $G$ is a subgraph of $H_{n,\delta}$ with
$\delta(G)\geq\delta$, i.e., $G$ is obtained from $H_{n,\delta}$ by deleting
edges from the clique $K_{n-\delta}$, then one can show that
$\lambda(G)<n-\delta-1$, unless $G=H_{n,\delta}$. The same argument holds for
the subgraph of $L_{n,\delta}$. Generally speaking, for sufficiently large $n$
with respect to $\delta$, both $H_{n,\delta}$ and $L_{n,\delta}$ consist of a
large clique $K_{n-\delta}$ together with a few number of outgrowth edges. We
know that $\lambda(H_{n,\delta})$ and $\lambda(L_{n,\delta})$ are very close
to $\lambda(K_{n-\delta})=n-\delta-1$. The key idea of Nikiforov exploits the
fact that if $G$ is a subgraph of $H_{n,\delta}$ or $L_{n,\delta}$ with
$\delta(G)\geq\delta$, then all the outgrowth edges contribute to $\lambda(G)$
much less than a single edge within the dense clique $K_{n-\delta}$, thus
$\lambda(G)<\lambda(K_{n-\delta})=n-\delta-1$; see [149, Theorem 1.6] for more
details.

On the other hand, a natural question is that whether the value bound
$q(G)\geq 2(n-\delta-1)$ corresponding to Theorem 2.13 holds or not. The
similar problems under the condition of signless Laplacian spectral radius of
graph seems much more complicated. In 2018, Li, Liu and Peng [114] solved this
problem completely. They gave the corresponding improvement on the result of
the signless Laplacian spectral radius in Theorem 2.13. Interestingly, the
extremal graphs in their theorems are quite different from those in Theorems
2.13.

Recall that $H_{n,\delta}=K_{\delta}\vee(K_{n-2\delta}\cup I_{\delta})$, we
denote $X=\\{v\in V(H_{n,\delta}):d(v)=\delta\\},Y=\\{v\in
V(H_{n,\delta}):d(v)=n-1\\}$ and $Z=\\{v\in
V(H_{n,\delta}):d(v)=n-\delta-1\\}$. Let $E_{1}(H_{n,\delta})$ be the set of
those edges of $H_{n,\delta}$ whose both endpoints are from $Y\cup Z$. We
define

$\mathcal{H}_{n,\delta}^{(1)}=\left\\{H_{n,\delta}\setminus
E^{\prime}:E^{\prime}\subseteq
E_{1}(H_{n,\delta})~{}\text{with}~{}|E^{\prime}|\leq\lfloor{\delta^{2}}/{4}\rfloor\right\\}.$

Here, we denote by $H_{n,\delta}\setminus E^{\prime}$ the graph obtained from
$H_{n,\delta}$ by deleting all edges of the edge set $E^{\prime}$. Similarly,
for the graph $L_{n,\delta}$, we denote $X=\\{v\in
V(L_{n,\delta}):d(v)=\delta\\},Y=\\{v\in V(L_{n,\delta}):d(v)=n-1\\}$ and
$Z=\\{v\in V(L_{n,\delta}):d(v)=n-\delta-1\\}$. The notation is clear although
we used the same alphabets to denote the sets of vertices. It is easy to see
that $Y$ contains only one vertex. We use $E_{1}(L_{n,\delta})$ to denote the
set of edges of $L_{n,\delta}$ whose both endpoints are from $Y\cup Z$. We
define

$\mathcal{L}_{n,\delta}^{(1)}=\Bigl{\\{}L_{n,\delta}\setminus
E^{\prime}:E^{\prime}\subseteq
E_{1}(L_{n,\delta})~{}\text{with}~{}|E^{\prime}|\leq\lfloor{\delta}/{4}\rfloor\Bigr{\\}}.$

First of all, we can show that if
$G\in\mathcal{H}_{n,\delta}^{(1)}\cup\mathcal{L}_{n,\delta}^{(1)}$, then $G$
contains no Hamilton cycle and $q(G)\geq 2(n-\delta-1)$. Indeed, recall the
subsets $X,Y$ and $Z$ defined as above. For each case, we define a vector
$\bm{h}$ such that $h_{v}=1$ for every $v\in Y\cup Z$ and $h_{v}=0$ for every
$v\in X$. Note that $q(K_{n-\delta}\cup
I_{\delta})=q(K_{n-\delta})=2(n-\delta-1)$ and $\bm{h}$ is a corresponding
eigenvector. If $G\in\mathcal{H}_{n,\delta}^{(1)}$, then we get

$\bm{h}^{T}Q(G)\bm{h}-\bm{h}^{T}Q({K_{n-\delta}\cup
I_{\delta}})\bm{h}=\delta^{2}-4|E^{\prime}|\geq 0.$

By the Rayleigh Formula, we have

$q(G)\geq\frac{\bm{h}^{T}Q(G)\bm{h}}{\bm{h}^{T}\bm{h}}\geq\frac{\bm{h}^{T}Q({K_{n-\delta}\cup
I_{\delta}})\bm{h}}{\bm{h}^{T}\bm{h}}=2(n-\delta-1).$

Similarly, we can show that $q(G)\geq 2(n-\delta-1)$ for every
$G\in\mathcal{L}_{n,\delta}^{(1)}$.

######  Theorem 2.15 (Li–Liu–Peng [114]).

Assume that $\delta\geq 1$ and
$n\geq\delta^{4}+\delta^{3}+4\delta^{2}+\delta+6$. Let $G$ be a connected
graph with $n$ vertices and minimum degree $\delta(G)\geq\delta$. If

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

then $G$ has a Hamilton cycle unless $G\in\mathcal{H}_{n,\delta}^{(1)}$ or
$G\in\mathcal{L}_{n,\delta}^{(1)}$.

In 2021, Zhou, Broersma, Wang and Lu [201] proved a slight improvement on
Theorem 2.15. Their proofs are based on the Bondy–Chvátal closure, a degree
sequence condition, and the Kelmans transformation.

###  2.2 Hamilton cycle in balanced bipartite graph

Let $G$ be a bipartite graph with vertex sets $X$ and $Y$. The bipartite graph
$G$ is called balanced if $|X|=|Y|$. We remark here that if a bipartite graph
has Hamilton cycle, then it must be balanced. So we consider the existence of
Hamilton cycle only in balanced bipartite graph.

######  Lemma 2.16 (See [25, p. 490]).

Let $G$ be a balanced bipartite graph on $2n$ vertices with degree sequence
$d_{1}\leq d_{2}\leq\cdots\leq d_{2n}$. If $G$ is not Hamiltonian, then there
exists an integer $i\leq\frac{n}{2}$ such that $d_{i}\leq i$ and $d_{n}\leq
n-i$.

Motivated by the work of Erdős [58] in Theorem 2.4, Moon and Moser [134]
provided a corresponding result for the balanced bipartite graphs.

######  Theorem 2.17 (Moon–Moser [134]).

Let $G$ be a balanced bipartite graph on $2n$ vertices. If the minimum degree
$\delta(G)\geq\delta$ for some $1\leq\delta\leq n/2$ and

$e(G)>n(n-\delta)+\delta^{2},$

then $G$ has a Hamilton cycle.

The condition $\delta\leq{n}/{2}$ is well comprehensible since Moon and Moser
[134] also pointed out that if $G$ is a balanced bipartite on $2n$ vertices
with $\delta(G)>{n}/{2}$, then $G$ must be Hamiltonian. This is a bipartite
version of the Dirac theorem.

Let $B_{n,\delta}$ be the bipartite graph obtained from the complete bipartite
graph $K_{n,n}$ by deleting all edges in its one subgraph
$K_{\delta,n-\delta}$. More precisely, the two vertex parts of $B_{n,\delta}$
are $V=V_{1}\cup V_{2}$ and $U=U_{1}\cup U_{2}$ where $|V_{1}|=|U_{1}|=\delta$
and $|V_{2}|=|U_{2}|=n-\delta$, we join all edges between $V_{1}$ and $U_{1}$,
and all edges between $V_{2}$ and $U$. We denote

$\boxed{B_{n,\delta}:=K_{n,n}\setminus K_{\delta,n-\delta}.}$

It is easy to see that $e(B_{n,\delta})=n(n-\delta)+\delta^{2}$ and
$B_{n,\delta}$ contains no Hamilton cycle. This implies that the condition in
Moon–Moser’s theorem is best possible.

For a bipartite graph, Lu, Liu and Tian [130] gave a sufficient condition for
a balanced bipartite graph being Hamiltonian in terms of the number of edges
and the spectral radius of its quasi-complement. Let $K_{n,n-1}+e$ be the
bipartite graph obtained from $K_{n,n-1}$ by adding a pendent edge to one of
vertices in the part of size $n$.

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

Let $G$ be a balanced bipartite graph on $2n\geq 4$ vertices. If the minimum
degree $\delta(G)\geq 1$ and

$e(G)\geq n(n-1)+1,$

then $G$ is Hamiltonian unless $G=K_{n,n-1}+e$.

Liu, Shiu and Xue [129] gave sufficient conditions on the spectral radius for
a bipartite graph being Hamiltonian. Their results extended Theorem 3.7.
Moreover, they also provided tight sufficient conditions on the signless
Laplacian spectral radius for a graph to be Hamiltonian and traceable, which
improve the results of Yu and Fan [177]. Let $K_{n,n-2}+4e$ be a bipartite
graph obtained from $K_{n,n-2}$ by adding two vertices which are adjacent to
two common vertices with degree $n-2$ in $K_{n,n-2}$.

######  Theorem 2.19 (Liu–Shiu–Xue [129]).

Let $G$ be a balanced bipartite graph on $2n\geq 8$ vertices. If
$\delta(G)\geq 2$ and

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

then $G$ is Hamiltonian unless $G=K_{n,n-2}+4e$.

For the Hamiltonicity of balanced bipartite graphs, Li and Ning [111, Theorem
1.10] also proved the spectral version of the Moon–Moser Theorem 2.17.

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

Suppose that $\delta\geq 1$ and $n\geq(\delta+1)^{2}$. Let $G$ be a
$2n$-vertex balanced bipartite graph. If the minimum degree
$\delta(G)\geq\delta$ and

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

then either $G$ has a Hamilton cycle or $G=B_{n,\delta}$.

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

Suppose that $\delta\geq 1$ and $n\geq(\delta+1)^{2}$. Let $G$ be a
$2n$-vertex balanced bipartite graph. If the minimum degree
$\delta(G)\geq\delta$ and

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

then either $G$ has a Hamilton cycle or $G=B_{n,\delta}$.

Recall that Theorem 2.14 extended slightly Theorem 2.12. For the case of
bipartite graphs, we can see that
$\lambda(B_{n,\delta})>\lambda(K_{n,n-\delta})=\sqrt{n(n-\delta)}$ since
$K_{n,n-\delta}$ is a proper subgraph of $B_{n,\delta}$. Motivated by this
observation, Ge and Ning [83, Theorem 1.4] proved the following improvement on
Theorem 2.20.

######  Theorem 2.22 (Ge–Ning [83]).

Suppose that $\delta\geq 1$ and $n\geq\delta^{3}+2\delta+4$. Let $G$ be a
balanced bipartite graph on $2n$ vertices. If the minimum degree
$\delta(G)\geq\delta$ and

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

then either $G$ has a Hamilton cycle or $G=B_{n,\delta}$.

We remark here that Jiang, Yu and Fang [95, Theorem 1.2] proved independently
the result in Theorem 2.22 under a weak condition
$n\geq\max\\{\frac{\delta^{3}}{2}+\frac{\delta^{2}}{2}+\delta+3,(\delta+2)^{2}\\}$
with the same method only by some careful calculations. In 2020, Liu, Wu and
Lai [128] unified these several former spectral Hamiltonian results on
balanced bipartite graphs and complementary graphs. In addition, Lu [131]
extended some spectral conditions for the Hamiltonicity of balanced bipartite
graphs.

Correspondingly, Li, Liu and Peng [114, Theorem 4] also gave an improvement on
Theorem 2.21 by observing that
$q(B_{n,{\delta}})>q(K_{n,n-\delta})=2n-\delta$. For the graph
$B_{n,{\delta}}$, let $S$ and $T$ be the vertex sets such that the degree of
vertices from $T$ is either $n$ or $n-{\delta}$. Let $X=\\{v\in
S:d(v)={\delta}\\},Y=\\{v\in T:d(v)=n\\},W=\\{v\in T:d(v)=n-{\delta}\\}$ and
$Z=\\{v\in S:d(v)=n\\}$. We can see from the definition that $S=X\cup Z$ and
$T=Y\cup W$. We denote $E_{1}(B_{n,{\delta}})$ by those edges of
$B_{n,{\delta}}$ whose both endpoints are from $Y\cup W\cup Z$. Let

$\mathcal{B}_{n,{\delta}}^{(1)}=\left\\{B_{n,{\delta}}\setminus
E^{\prime}:E^{\prime}\subseteq
E_{1}(B_{n,{\delta}})~{}\text{with}~{}|E^{\prime}|\leq\lfloor{{\delta}^{2}}/{4}\rfloor\right\\}.$

Similarly we can show that $q(G)\geq q(K_{n,n-{\delta}}\cup
I_{\delta})=2n-{\delta}$ for every $G\in\mathcal{B}_{n,{\delta}}^{(1)}$.
Indeed, let $\bm{f}$ be an eigenvector of $K_{n,n-{\delta}}\cup I_{\delta}$
corresponding to $2n-{\delta}$. We can define the vector $\bm{f}$ as $f_{u}=1$
for vertex $u$ with $d(u)=n$, and $f_{u}=1-\frac{\delta}{n}$ for vertex $u$
with $d(u)=n-{\delta}$. Then

$\bm{f}^{T}Q(G)\bm{f}-\bm{f}^{T}Q(K_{n,n-{\delta}}\cup
I_{\delta})\bm{f}=\delta^{2}-4|E^{\prime}|\geq 0.$

The Rayleigh Formula gives

$q(G)\geq\frac{\bm{f}^{T}Q(G)\bm{f}}{\bm{f}^{T}\bm{f}}\geq\frac{\bm{f}^{T}Q({K_{n,n-\delta}\cup
I_{\delta}})\bm{f}}{\bm{f}^{T}\bm{f}}=2n-\delta.$

######  Theorem 2.23 (Li–Liu–Peng [114]).

Assume that $\delta\geq 1$ and
$n\geq\delta^{4}+3\delta^{3}+5\delta^{2}+5\delta+4$. Let $G$ be a connected
graph with $n$ vertices and minimum degree $\delta(G)\geq\delta$. If

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

then $G$ has a Hamilton cycle unless $G\in\mathcal{B}_{n,\delta}^{(1)}$.

###  2.3 Problem for $k$-Hamiltonicity

A graph $G=(V,E)$ is _$k$ -Hamiltonian_ if for all $X\subset V$ with $|X|\leq
k$, the subgraph induced by $V\setminus X$ is Hamiltonian. Thus
$0$-Hamiltonian graph is the same as the general Hamiltonian graph. Similarly,
a graph $G$ is $k$-edge-Hamiltonian if any collection of vertex-disjoint paths
with at most $k$ edges altogether belong to a Hamiltonian cycle in $G$. In
[34], it is obtained that for a graph $G$, if $\delta(G)\geq\frac{n+k}{2},$
then $G$ is $k$-Hamiltonian. Clearly, when $k=0$, it reduces to the Dirac
theorem.

######  Theorem 2.24 (Chartrand et al. [34], Bondy–Chvátal [23]).

A graph $G$ is $k$-Hamiltonian if and only if the closure graph
$\mathrm{cl}_{n+k}(G)$ is $k$-Hamiltonian. 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$-Hamiltonian.

In 1972, Chvátal [40] proved the following theorem, which characterizes the
sufficient condition of degree sequence of $k$-Hamiltonian graphs.

######  Theorem 2.25 (Chvátal [40]).

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

In [70], Feng et al. obtained sufficient conditions for a graph to be
$k$-Hamiltonian.

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

Let $k\geq 1$, and let $G$ be a graph of order $n\geq k+6$. If
$e(G)\geq{n-1\choose 2}+k+1$, then either $G$ is $k$-Hamiltonian or
$G=K_{k+1}\vee(K_{1}\cup K_{n-k-2})$.

In this survey, we shall provide an extension by giving minimum degree. When
$\delta=k+1$, the following theorem reduces to Theorem 2.26. For convenience,
we denote by

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

and

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

It is easy to see that both $H_{n,k,\delta}$ and $L_{n,k,\delta}$ are not
$k$-Hamiltonian and has minimum degree
$\delta(H_{n,k,\delta})=\delta(L_{n,k,\delta})=\delta$. In particular, when
$k=0$, we can see that $H_{n,0,\delta}$ is the same as $H_{n,\delta}$, and
$L_{n,0,\delta}$ is the same as $L_{n,\delta}$, which are defined in equations
(LABEL:eqhnd) and (LABEL:eqlnd).

######  Theorem 2.27.

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

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

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

###### Proof.

Suppose that $G$ is not $k$-Hamiltonian. According to Theorem 2.24, we know
that the closure graph $H:=\mathrm{cl}_{n+k}(G)$ is also not $k$-Hamiltonian.
Let $d_{1}\leq d_{2}\leq\cdots\leq d_{n}$ be the degree sequence of $H$. By
Theorem 2.25, there exists an integer $1\leq m\leq\frac{n-k-1}{2}$ such that
$d_{m}\leq m+k$ and $d_{n-m-k}\leq n-m-1$. Hence, we have

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

First of all, we denote $f(m)=3m^{2}-(2n-2k-1)m$. Since
$\delta\leq\delta(G)\leq\delta(H)\leq m+k$, we can see that $\delta-k\leq
m\leq\frac{n-k-1}{2}$. The quadratic function $f(m)$ is minimized at
$m_{0}=\frac{2n-2k-1}{6}$. Note that $n\geq 6\delta-5k$ implies
$m_{0}-(\delta-k)>\frac{n-k-1}{2}-m_{0}$. Therefore, we have $f(m)$ is
maximized at $m=\delta-k$. Then

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

By the condition, we get $e(G)=e(K_{\delta}\vee(K_{n-2\delta+k}\cup
I_{\delta-k}))$. All the inequalities above become equalities, that is
$m=\delta-k$ and $G=\mathrm{cl}_{n+k}(G)$, moreover 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})$.

Recall that $d_{1},d_{2},\ldots,d_{n}$ are the degrees of $G$, and the
corresponding vertices are $v_{1},v_{2},\ldots,v_{n}$. We next denote by
$X=\\{v_{1},v_{2},\ldots,v_{\delta-k}\\}$ and
$Y=\\{v_{\delta-k+1},\ldots,v_{n}\\}$. We next show that the induced subgraph
$G[Y]=K_{n-\delta+k}$. Otherwise, we choose two non-adjacent vertices
$v_{r},v_{s}\in Y$. By noting that $G=\mathrm{cl}_{n+k}(G)$, then the non-
adjacency of $v_{r}$ and $v_{s}$ implies that $d_{r}+d_{s}<n+k.$ On the other
hand, we know from the definition of $Y$ that $d_{r}+d_{s}\geq
2(n-\delta+k-1)>n+k$, a contradiction. Thus we get $G[Y]=K_{n-\delta+k}$.

The previous result on degree sequence implies that there are $\delta$
vertices in $Y$ with degree $n-1$, we now denote these vertices by
$F=\\{v_{n-\delta+1},\ldots,v_{n}\\}$. Let $G[X,F]$ be the induced bipartite
subgraph in $G$ between vertex sets $X$ and $F$. Finally, we shall show that
$G[X,F]=K_{\delta-k,\delta}$. Note that $G=\mathrm{cl}_{n+k}(G)$, which
implies that every two vertices with the degree sum at least $n+k$ are
adjacent. Thus, every vertex in $X$ is adjacent to every vertex in $F$. So we
can see that $G[X,F]=K_{\delta-k,\delta}$, and then $X$ is an independent set
in $G$. Hence we get $G=K_{\delta}\vee(K_{n-2\delta+k}\cup I_{\delta-k})$. ∎

Recently, by utilizing the degree sequences and the closure concept, Liu et
al. [125] generalized Theorem 2.14 to $k$-Hamiltonian graphs. Their results
can be considered as the spectral counterpart for the above Dirac-type
condition. We mention here that there is a tiny typo at the end of the proof
in [125, Theorem 4] since the extremal graph is not the only one. Clearly, the
graph $H_{n,k,\delta}=K_{\delta}\vee(K_{n-2\delta+k}\cup I_{\delta-k})$ is not
$k$-Hamiltonian and $\lambda(H_{n,k,\delta})>n-\delta+k-1$. By a careful
modification, the correct result should be the following.

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

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

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

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

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

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

Since $\lambda(H_{n,k,\delta})$ contains $K_{n-\delta+k}$ as a subgraph, we
have $\lambda(H_{n,k,\delta})\geq n-\delta+k-1$. Note that
$\lambda(H_{n,k,\delta})>\lambda(L_{n,k,\delta})$. So we can immediately get
the spectral version of Theorem 2.27 for graphs with sufficient large order.

######  Corollary 2.29.

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

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

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

Recall that $H_{n,k,\delta}=K_{\delta}\vee(K_{n-2\delta+k}\cup I_{\delta-k})$.
Let $X$ be the set of $\delta-k$ vertices forming by the independent set
$I_{\delta-k}$, $Y$ be the set of $\delta$ vertices corresponding to the
clique $K_{\delta}$ and $Z$ be the set of the remaining $n-2\delta+k$ vertices
consisting of the clique $K_{n-2\delta+k}$. This notation is clear although it
is not standard. We write $E_{1}(H_{n,k,\delta})$ for the set of edges of
$H_{n,k,\delta}$ whose both endpoints are from $Y\cup Z$. Furthermore, we
define the family $\mathcal{H}_{n,k,\delta}^{(1)}$ of graphs as below.

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

Here, we write $H_{n,k,\delta}\setminus E^{\prime}$ for the graph obtained
from $H_{n,k,\delta}$ by deleting all edges of the edge set $E^{\prime}$.
Similarly, for the graph $L_{n,k,\delta}=K_{k+1}\vee(K_{n-\delta-1}\cup
K_{\delta-k})$, we denote $X$ by the set of vertices corresponding to the
clique $K_{\delta-k}$, $Y$ by the set of vertices corresponding to the clique
$K_{k+1}$, and $Z$ by the set of the remaining $n-\delta-1$ vertices. We write
$E_{1}(L_{n,k,\delta})$ for the set of edges of $L_{n,k,\delta}$ whose both
endpoints are from $Y\cup Z$. Moreover, we define the family
$\mathcal{L}_{n,k,\delta}^{(1)}$ of graphs as follows.

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

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

######  Theorem 2.30 (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$-Hamiltonian unless $G\in\mathcal{H}_{n,k,\delta}^{(1)}$ or
$G\in\mathcal{L}_{n,k,\delta}^{(1)}$.

######  Corollary 2.31.

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$-Hamiltonian unless $G=H_{n,k,\delta}$.

###  2.4 Problem for $k$-edge-Hamiltonicity

Recall that a graph $G$ is $k$-edge-Hamiltonian if any collection of vertex-
disjoint paths with at most $k$ edges altogether belong to a Hamiltonian cycle
in $G$.

######  Theorem 2.32 (Kronk [106], Bondy–Chvátal [23]).

A graph $G$ is $k$-edge-Hamiltonian if and only if the closure graph
$\mathrm{cl}_{n+k}(G)$ is $k$-edge-Hamiltonian. 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$-edge-Hamiltonian.

######  Lemma 2.33 (Kronk [107]).

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

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

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

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

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

To avoid unnecessary calculations, we do not attempt to get the best bound on
the order of graphs in the proof.

######  Theorem 2.35 (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

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

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

Since $\lambda(H_{n,k,\delta})$ contains $K_{n-\delta+k}$ as a proper
subgraph, we have $\lambda(H_{n,k,\delta})>n-\delta+k-1$. Moreover, applying
the Kelmans operations on $L_{n,k,\delta}$, we can get a proper subgraph of