# On a generalization of the spectral Mantel’s theorem

Chunmeng Liu<EMAIL_ADDRESS>Changjiang Bu<EMAIL_ADDRESS>College of Mathematical Sciences, Harbin Engineering University, Harbin
150001, PR China

###### Abstract

Mantel’s theorem is a classical result in extremal graph theory which implies
that the maximum number of edges of a triangle-free graph of order $n$. In
1970, E. Nosal obtained a spectral version of Mantel’s theorem which gave the
maximum spectral radius of a triangle-free graph of order $n$. In this paper,
we consider the generalized spectral extremal problems. The clique tensor of a
graph $G$ is proposed and the spectral Mantel’s theorem is extended via the
clique tensor. Furthermore, a sharp upper bound of the number of cliques in
$G$ via the spectral radius of the clique tensor is obtained. And we show that
the results of this paper implies that a result of Erdős [Magyar Tud. Akad.
Mat. Kutató Int. Közl. 7 (1962)] under certain conditions.

###### keywords:

Mantel’s theorem, Spectral radius, Cliques, Tensor
_AMS classification (2020):_ 05C35, 05C50

††journal:

##  1 Introduction

The graphs in this paper are undirected and simple. Let $G$ be a graph with
the set of vertices $V(G)=\\{1,2,\ldots,n\\}$ and the set of edges
$E(G)=\\{e_{1},...,e_{m}\\}$, the number of edges of $G$ is denoted by $e(G)$.
For a vertex $i\in V(G)$, the neighborhood of $i$ is the set of all vertices
adjacent to $i$, denoted by $N(i)$. A clique is a subset of vertices of a
graph such that its induced subgraph is complete, and a clique of size $t$ is
called a $t$-clique, denoted by $c_{t}$. The set of all $t$-cliques in $G$ is
denoted by $C_{t}(G)$ and the number of $t$-cliques of $G$ is denoted by
$c_{t}(G)$. Let $T_{r}(n)$ be the complete $r$-partite graph with partitions
of sizes $n_{1}\leq n_{2}\leq\cdots\leq n_{r}$ and $n_{r}-n_{1}\leq 1$, the
graph $T_{r}(n)$ is called _$r$ -partite Turán graph_.

Mantel’s theorem, established by Willem Mantel [1] in 1907, is one of the
early results in extremal graph theory and states that if $G$ is a triangle-
free graph of order $n$, then $e(G)\leq e(T_{2}(n))$, equality holds if and
only if $G=T_{2}(n)$. In 1941, P. Turán [2] extended the Mantel’s theorem and
obtained the well-known Turán theorem. From then on, Turán type extremal
problems have attracted extensive attention [3].

Let $\rho(G)$ be the spectral radius of the adjacency matrix of a graph $G$.
The spectral extremal problem is an important topic in the extremal graph
theory. Up to now, there have been many results on the spectral extremal graph
theory [4, 5]. In 1970, E. Nosal [6] obtained the maximum spectral radius of a
triangle-free graph $G$ of order $n$ and the conclusion is called the spectral
form of Mantel’s theorem.

######  Theorem 1.1.

(Spectral Mantel’s theorem [6]) Suppose that $G$ is a triangle-free graph of
order $n$, then

$\displaystyle\rho(G)\leq\rho(T_{2}(n)),$

equality holds if and only if $G=T_{2}(n)$.

######  Remark 1.

V. Nikiforov [7] proved that the relationship between Theorem 1.1 and Mantel’s
theorem. Through the inequality $\frac{2e(G)}{n}\leq\rho(G)$ and Theorem 1.1,
for an $n$ vertices triangle-free graph $G$, then

$\displaystyle
e(G)\leq\left\lfloor\frac{n}{2}\rho(G)\right\rfloor\leq\left\lfloor\frac{n}{2}\rho(T_{2}(n))\right\rfloor=\left\lfloor\frac{n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil=e(T_{2}(n)).$

It shows that Theorem 1.1 implies Mantel’s theorem.

V. Nikiforov [8] generalized Theorem 1.1 to $K_{r+1}$-free graphs and gave the
spectral Turán’s theorem.

######  Theorem 1.2.

[8] If $G$ is a $K_{r+1}$-free graph of order $n$, then

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

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

In addition, Theorem 1.1 is improved in terms of the number of edges of a
graph in [9]. For further results, see [10, 11, 12].

In this paper, the clique tensor of a graph is proposed and Theorem 1.1 is
extended via the clique tensor. Let $\mathbb{C}^{n}$ be the set of
$n$-dimensional vectors over complex number field $\mathbb{C}$. An order $m$
dimension $n$ complex tensor $\mathcal{A}=(a_{i_{1}i_{2}\cdots i_{m}})$ is a
multidimensional array with $n^{m}$ entries, where $i_{j}=1,2,\ldots,n$,
$j=1,2,\ldots,m$. For vectors $x=(x_{1},\ldots,x_{n})^{T}\in\mathbb{C}^{n}$,
the $\mathcal{A}x^{m-1}$ is a vector in $\mathbb{C}^{n}$ whose $i$-th
component is $\sum_{i_{2},\ldots,i_{m}=1}^{n}a_{ii_{2}\cdots
i_{m}}x_{i_{2}}\cdots x_{i_{m}}$ [13]. In 2005, Qi [13] and Lim [14] posed the
eigenvalues of tensors, respectively. If there exist $\lambda\in\mathbb{C}$
and nonzero vector $x=(x_{1},\ldots,x_{n})^{T}\in\mathbb{C}^{n}$ satisfy

$\displaystyle\mathcal{A}x^{m-1}=\lambda x^{[m-1]},$ (1)

then $\lambda$ is called an _eigenvalue_ of $\mathcal{A}$ and $x$ an
_eigenvector_ of $\mathcal{A}$ corresponding to $\lambda$, where
$x^{[m-1]}=(x_{1}^{m-1},\ldots,x_{n}^{m-1})^{T}$. The maximal modulus of all
eigenvalues of $\mathcal{A}$ is called the spectral radius of $\mathcal{A}$,
denoted by $\rho(\mathcal{A})$. The tensor and its eigenvalues have been
applied to many fields, such as signal processing [15], automatica [16],
polynomial optimization [17], network analysis [18], solving multilinear
systems [19, 20], spectral hypergraph theory [21, 22, 23, 24, 25], etc. The
authors [26] improved the upper bound of Wilf’s chromatic number in terms of
the spectral radius of tensors and obtained a formula of the number of cliques
of fixed size which involve the spectrum of tensors.

The _$t$ -clique tensor_ of a graph $G$ is defined as follows.

######  Definition 1.3.

Let $G$ be a graph with $n$ vertices. An order $t$ and dimension $n$ tensor
$\mathcal{A}(G)=(a_{i_{1}i_{2}\cdots i_{t}})$ is called the $t$-clique tensor
of $G$, if

$\displaystyle a_{i_{1}i_{2}\cdots
i_{t}}=\begin{cases}\frac{1}{(t-1)!},&\\{i_{1},\ldots,i_{t}\\}\in C_{t}(G).\\\
0,&\textup{otherwise}.\end{cases}$

The eigenvalue of $\mathcal{A}(G)$ is called the _$t$ -clique eigenvalue_ of
$G$. The spectral radius of $\mathcal{A}(G)$ is called the _$t$ -clique
spectral radius_ of $G$, denoted by $\rho_{t}(G)$. When $t=2$, the $2$-clique
tensor $\mathcal{A}(G)$ is the adjacency matrix of $G$ and $\rho_{2}(G)$ is
the spectral radius of the adjacency matrix of $G$.

In this paper, Theorem 1.1 is generalized.

######  Theorem 1.4.

Let $G$ be a graph on $n$ vertices. If $G$ is $K_{r+1}$-free, then

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

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

Obviously, Theorem 1.4 is the spectral Mantel’s theorem in the case when
$r=2$. Similar to Remark 1, a natural question is that does Theorem 1.4 imply
the maximum number of $r$-cliques in $K_{r+1}$-free graphs of order $n$?
Therefore, we study the maximum number of cliques of fixed size in graphs in
terms of spectral radius of tensors and obtain a following sharp upper bound
of $c_{r}(G)$ in terms of $\rho_{r}(G)$.

######  Theorem 1.5.

For the $r$-clique spectral radius $\rho_{r}(G)$ of a graph $G$ on $n$
vertices, then

$\displaystyle c_{r}(G)\leq\frac{n}{r}\rho_{r}(G).$ (2)

Furthermore, if the number of $r$-cliques containing $i$ is equal for all
$i\in V(G)$, then equality holds in (2).

For a $K_{r+1}$-free graph $G$ of order $n$, P. Erdős [27] proved that

$\displaystyle c_{r}(G)\leq c_{r}(T_{r}(n))$ (3)

with equality holds if and only if $G$ is the $r$-partite Turán graph
$T_{r}(n)$, and [28, 29] gave the same conclusion through different methods.
In Section 3, we will show that Theorem 1.4 implies (3) in the case when
$r\mid n$. The remainder of the paper is organized as follows. In Section 2,
we introduce some of the definitions and lemmas required for proofs. In
Section 3, we give the proofs of Theorem 1.4 and Theorem 1.5.

##  2 Preliminaries

The tensor $\mathcal{A}$ is called symmetric if its entries are invariant
under any permutation of their indices. If all elements of a tensor
$\mathcal{A}$ are nonnegative, then $\mathcal{A}$ is called the nonnegative
tensor. For the symmetric nonnegative tensor, Qi [30] gave the following
conclusion.

######  Lemma 2.6.

[30] Suppose that $\mathcal{A}$ is an order $m$ dimension $n$ symmetric
nonnegative tensor, with $m\geq 2$. Then

$\displaystyle\rho(\mathcal{A})=\max\left\\{x^{T}\mathcal{A}x^{m-1}:\sum_{i=1}^{n}x_{i}^{m}=1,x=(x_{1},\ldots,x_{n})^{T}\in\mathbb{R}_{+}^{n}\right\\},$

where $\mathbb{R}_{+}^{n}$ is the set of $n$-dimensional nonnegative real
vectors.

The upper and lower bounds of spectral radius of nonnegative tensors are
obtained in [31].

######  Lemma 2.7.

[31] Let $\mathcal{A}=(a_{i_{1}i_{2}\cdots i_{m}})$ be an order $m$ dimension
$n$ nonnegative tensor. Then

$\displaystyle\min_{1\leq i\leq
n}\sum_{i_{2},\ldots,i_{m}=1}^{n}a_{ii_{2}\cdots
i_{m}}\leq\rho(\mathcal{A})\leq\max_{1\leq i\leq
n}\sum_{i_{2},\ldots,i_{m}=1}^{n}a_{ii_{2}\cdots i_{m}}.$

For an order $m$ dimension $n$ nonnegative tensor
$\mathcal{A}=(a_{i_{1}i_{2}\cdots i_{m}})$, let
$G_{\mathcal{A}}=(V(G_{\mathcal{A}}),E(G_{\mathcal{A}}))$ be the digraph of
the tensor $\mathcal{A}$ with vertex set
$V(G_{\mathcal{A}})=\\{1,2,\ldots,n\\}$ and arc set
$E(G_{\mathcal{A}})=\\{(i,j)|a_{ii_{2}\cdots i_{m}}\neq
0,j\in\\{i_{2},\ldots,i_{m}\\}\\}$. The nonnegative tensor $\mathcal{A}$ is
weakly irreducible if the corresponding directed graph $G_{\mathcal{A}}$ is
strongly connected. Otherwise, the tensor $\mathcal{A}$ is weakly reducible
(see [32]). The Perron-Frobenius theorem for weakly irreducible nonnegative
tensors is given in [32].

######  Lemma 2.8.

[32] If a nonnegative tensor $\mathcal{A}$ is weakly irreducible, then
$\rho(\mathcal{A})$ is the unique positive eigenvalue of $\mathcal{A}$, with
the unique positive eigenvector $x$, up to a positive scaling coefficient.

Let $\mathcal{A}$ and $\mathcal{B}$ be two order $m$ dimension $n$ nonnegative
tensors. If $\mathcal{B}-\mathcal{A}$ is nonnegative, we write
$\mathcal{A}\leq\mathcal{B}$.

######  Lemma 2.9.

[33] Suppose $0\leq\mathcal{A}\leq\mathcal{B}$, then
$\rho(\mathcal{A})\leq\rho(\mathcal{B})$. Furthermore, if $\mathcal{B}$ is
weakly irreducible and $\mathcal{A}\neq\mathcal{B}$, then
$\rho(\mathcal{A})<\rho(\mathcal{B})$.

Shao et al [34] obtained the following result on the “weakly reducible
canonical form” which is a generalization of the corresponding “reducible
canonical form” theorem for matrices.

######  Lemma 2.10.

[34] Let $\mathcal{A}$ be an order $m$ dimension $n$ tensor. Then there exists
positive integers $r\geq 1$ and $n_{1},\ldots,n_{r}$ with
$n_{1}+\cdots+n_{r}=n$ such that $\mathcal{A}$ is permutational similar to
some $(n_{1},\ldots,n_{r})$-lower triangular block tensor, where all the
diagonal blocks $\mathcal{A}_{1},\ldots,\mathcal{A}_{r}$ are weakly
irreducible. Furthermore, we have
$\rho(\mathcal{A})=\max\\{\rho(\mathcal{A}_{1}),\ldots,\rho(\mathcal{A}_{r})\\}$.

##  3 Proofs of Theorems

A walk is a sequence of edges $e_{1},e_{2},\ldots,e_{m}$ in which $e_{i}$ and
$e_{i+1}$ are incident with a common vertex for $i=1,\ldots,m-1$, and a graph
is connected if any two of its vertices are joined by a walk. The adjacency
matrix of a graph $G$ is irreducible if and only if $G$ is connected (see
[35]). A _$t$ -clique walk_ of a graph $G$ is proposed to determine the
$t$-clique tensor of $G$ is weakly irreducible, that is, a sequence of
$t$-cliques $c_{t}^{1},c_{t}^{2},\ldots,c_{t}^{m}$ in which $c_{t}^{i}$ and
$c_{t}^{i+1}$ have at least one vertex in common for $i=1,\ldots,m-1$. A graph
$G$ is called _$t$ -clique connected_ if any two of its vertices are joined by
a $t$-clique walk. For the $t$-clique tensor of a graph $G$, we have the
following conclusion.

######  Lemma 3.11.

The $t$-clique tensor of a graph $G$ is weakly irreducible if and only if $G$
is $t$-clique connected.

###### Proof.

Let $\mathcal{A}(G)=(a_{i_{1}i_{2}\cdots i_{t}})$ be the $t$-clique tensor of
$G$. Firstly, we prove that $\mathcal{A}(G)$ is weakly irreducible if $G$ is
$t$-clique connected.

Let $i_{1},i_{2},\ldots,i_{t}$ be the $t$ vertices of $G$. Suppose that
vertices $i_{1},i_{2},\ldots,i_{t}$ compose a $t$-clique in $G$, we obtain
$a_{i_{1}i_{2}\cdots i_{t}}=a_{\sigma(i_{1}i_{2}\cdots
i_{t})}=\frac{1}{(t-1)!}$ by Definition 1.3, where $\sigma$ denotes a
permutation of $\\{i_{1},i_{2},\ldots,i_{t}\\}$. By the definition of the
digraph $G_{\mathcal{A}(G)}$ of $\mathcal{A}(G)$, vertices
$i_{1},i_{2},\ldots,i_{t}$ form a complete digraph of $t$ vertices in
$G_{\mathcal{A}(G)}$. Since $G$ is $t$-clique connected, any two of its
vertices are joined by a $t$-clique walk. Thus, we obtain $G_{\mathcal{A}(G)}$
is strongly connected imply that the $t$-clique tensor $\mathcal{A}(G)$ of $G$
is weakly irreducible.

Next, we prove that $\mathcal{A}(G)$ is weakly reducible if $G$ is not
$t$-clique connected.

Since $G$ is not $t$-clique connected, there exist two vertices $i$ and $j$
can not join by any $t$-clique walks. Therefore, vertices $i$ and $j$ can not
join by any walks in the digraph $G_{\mathcal{A}(G)}$ of $\mathcal{A}(G)$,
implying that $G_{\mathcal{A}(G)}$ is not strongly connected. That is, the
$t$-clique tensor $\mathcal{A}(G)$ is weakly reducible. ∎

The proof of Theorem 1.4 is divided into three parts. Let $G^{\prime}$ be a
$K_{r+1}$-free graph on $n$ vertices with the largest $r$-clique spectral
radius. Firstly, we show that $G^{\prime}$ is $r$-clique connected. Secondly,
we prove that $G^{\prime}$ is a complete $r$-partite graph. Lastly, for all
the complete $r$-partite graphs on $n$ vertices, we show that the graph with
the maximum $r$-clique spectral radius is the $r$-partite Turán graph
$T_{r}(n)$.

######  Lemma 3.12.

The graph $G^{\prime}$ is $r$-clique connected.

###### Proof.

Let $\mathcal{A}(G^{\prime})$ be the $r$-clique tensor of $G^{\prime}$.
Suppose to the contrary that $G^{\prime}$ is not $r$-clique connected, then
$\mathcal{A}(G^{\prime})$ is weakly reducible by Lemma 3.11. Since
$\mathcal{A}(G^{\prime})$ is weakly reducible, there exists a subgraph $H$ of
$G^{\prime}$ such that $H$ is an $r$-clique component (an $r$-clique connected
subgraph that is not part of any larger $r$-clique connected subgraph)
attaining the $r$-clique spectral radius of $G^{\prime}$ by Lemma 2.10, that
is $\rho_{r}(G^{\prime})=\rho_{r}(H)$. The graph $G^{\prime}$ is not
$r$-clique connected also implies that there exist two vertices $i$ and $j$
can not join by any $r$-clique walks. For the vertex $i$, we discuss it in two
cases.

Case 1: The vertex $i\in V(H)$. Then the vertex $j\notin V(H)$, that is, the
vertex $j$ does not form an $r$-clique with vertices in $H$. Therefore, the
vertex $j$ is adjacent to at most $r-2$ vertices of any $r$-clique in $H$.
Take an $r$-clique $c^{\prime}_{r}=\\{v_{1},\ldots,v_{r}\\}$ of $H$ with the
most vertices adjacent to $j$. Suppose that vertices $v_{1},\ldots,v_{s}$ are
adjacent to $j$, we have $s\leq r-2$. Let $H^{\prime}$ be the graph with
$V(H^{\prime})=V(H)\cup\\{j\\}$ and obtained by adding edges between the
vertices $v_{s+1},\ldots,v_{r-1}$ and $j$. Thus, the vertices
$v_{1},\ldots,v_{r-1},j$ form an $r$-clique in $H^{\prime}$. Since
$G^{\prime}$ is $K_{r+1}$-free, the graph $H$ is $K_{r+1}$-free implies that
$H^{\prime}$ is also $K_{r+1}$-free. Otherwise, there exists a vertex $k$ such
that $v_{1},\ldots,v_{r-1},j,k$ form an $(r+1)$-clique in $H^{\prime}$. That
is, the vertices $v_{1},\ldots,v_{r-1},k$ form an $r$-clique in $H$ and $j$ is
adjacent to $v_{1},\ldots,v_{s},k$. This contradicts the choice of
$c^{\prime}_{r}$. The graph $H^{\prime}$ is $r$-clique connected and $H$ is an
$r$-clique connected subgraph of $H^{\prime}$ with $|V(H)|<|V(H^{\prime})|$.
Add an isolated vertex to $H$ such that the resulting graph $\hat{H}$ has the
same number of vertices as $H^{\prime}$, and we have
$\rho_{r}(H)=\rho_{r}(\hat{H})$. Since $H^{\prime}$ is $r$-clique connected,
the $r$-clique tensor $\mathcal{A}(H^{\prime})$ of $H^{\prime}$ is weakly
irreducible by Lemma 3.11. The $r$-clique tensor
$\mathcal{A}(\hat{H})<\mathcal{A}(H^{\prime})$ implies that
$\rho_{r}(H)=\rho_{r}(\hat{H})<\rho_{r}(H^{\prime})$ by Lemma 2.9. Thus
$\rho_{r}(G^{\prime})=\rho_{r}(H)<\rho_{r}(H^{\prime})$, this contradicts the
choice of $G^{\prime}$.

Case 2: The vertex $i\notin V(H)$. Similar to Case 1, we can construct a
$K_{r+1}$-free graph $H^{\prime\prime}$ through the vertex $i$ and $H$ such
that $\rho_{r}(G^{\prime})=\rho_{r}(H)<\rho_{r}(H^{\prime\prime})$. It is also
contradictory. ∎

######  Lemma 3.13.

The graph $G^{\prime}$ is a complete $r$-partite graph.

###### Proof.

Let $\mathcal{A}(G^{\prime})$ be the $r$-clique tensor of $G^{\prime}$. From
Lemma 3.12, the graph $G^{\prime}$ is $r$-clique connected. Thus, the
$r$-clique tensor $\mathcal{A}(G^{\prime})$ is weakly irreducible by Lemma
3.11. By Lemma 2.8, the $r$-clique spectral radius $\rho_{r}(G^{\prime})$ is
the unique positive eigenvalue of $\mathcal{A}(G^{\prime})$, with the unique
positive eigenvector $x=(x_{1},\ldots,x_{n})^{T}$. For the $r$-clique spectral
radius $\rho_{r}(G^{\prime})$, we have

$\displaystyle\rho_{r}(G^{\prime})=x^{T}\mathcal{A}(G^{\prime})x^{r-1}=r\sum_{\\{i_{1},\ldots,i_{r}\\}\in
C_{t}(G^{\prime})}x_{i_{1}}\cdots x_{i_{r}}.$

In order to prove that $G^{\prime}$ is a complete $r$-partite graph, suppose
to the contrary that $G^{\prime}$ is not a complete $r$-partite graph which
implies that $G^{\prime}$ is a complete $s$-partite graph for $s<r$ or there
exist two non adjacent vertices $i,j\in V(G^{\prime})$ such that $N(i)\neq
N(j)$. We discuss it in the following two cases.

Case 1. The graph $G^{\prime}$ is a complete $s$-partite graph for $s<r$, then
the $r$-clique does not exist in $G^{\prime}$. This contradicts that
$G^{\prime}$ is $r$-clique connected.

Case 2. There exist two non adjacent vertices $i,j\in V(G^{\prime})$ such that
$N(i)\neq N(j)$, suppose that there exists a vertex $k\in V(G^{\prime})$
adjacent to $i$ and not adjacent to $j$. For vertex $v\in V(G^{\prime})$ and
the eigenvector $x=(x_{1},\ldots,x_{n})^{T}$ corresponding to
$\rho_{r}(G^{\prime})$, we obtain

$\displaystyle\rho_{r}(G^{\prime})x_{v}^{r-1}=\sum_{\\{v,i_{2},\ldots,i_{r}\\}\in
C_{t}(G^{\prime})}x_{i_{2}}\cdots x_{i_{r}}.$

Let $WS_{G^{\prime}}(v,x)=\sum_{\\{v,i_{2},\ldots,i_{r}\\}\in
C_{t}(G^{\prime})}x_{i_{2}}\cdots x_{i_{r}}$. For $WS_{G^{\prime}}(i,x)$,
$WS_{G^{\prime}}(j,x)$ and $WS_{G^{\prime}}(k,x)$, it will be discussed on two
cases.

Case i. $WS_{G^{\prime}}(j,x)<WS_{G^{\prime}}(i,x)$ or
$WS_{G^{\prime}}(j,x)<WS_{G^{\prime}}(k,x)$.

If $WS_{G^{\prime}}(j,x)<WS_{G^{\prime}}(i,x)$, we delete all edges incident
to $j$ and connect $j$ to all vertices in $N(i)$. After such a graph
operation, we get a new graph $G^{\prime\prime}$, and $G^{\prime\prime}$ is
still $K_{r+1}$-free. For the graph $G^{\prime\prime}$ and the positive
eigenvector $x=(x_{1},\ldots,x_{n})^{T}$ corresponding to
$\rho_{r}(G^{\prime})$, by Lemma 2.6, we have

$\displaystyle\rho_{r}(G^{\prime\prime})$ $\displaystyle\geq
r\sum_{\\{i_{1},\ldots,i_{r}\\}\in C_{t}(G^{\prime\prime})}x_{i_{1}}\cdots
x_{i_{r}}$ $\displaystyle=r\sum_{\\{i_{1},\ldots,i_{r}\\}\in
C_{t}(G^{\prime})}x_{i_{1}}\cdots
x_{i_{r}}-rx_{j}WS_{G^{\prime}}(j,x)+rx_{j}WS_{G^{\prime}}(i,x)$
$\displaystyle>r\sum_{\\{i_{1},\ldots,i_{r}\\}\in
C_{t}(G^{\prime})}x_{i_{1}}\cdots x_{i_{r}}=\rho_{r}(G^{\prime}).$

This contradicts the choice of $G^{\prime}$. When
$WS_{G^{\prime}}(j,x)<WS_{G^{\prime}}(k,x)$, the proof is similar.

Case ii. $WS_{G^{\prime}}(j,x)\geq WS_{G^{\prime}}(i,x)$ and
$WS_{G^{\prime}}(j,x)\geq WS_{G^{\prime}}(k,x)$.

In this case, we delete all edges incident to $i$ and connect $i$ to all
vertices in $N(j)$. Delete all edges incident to $k$ and connect $k$ to all
vertices in $N(j)$. Then we get a graph $G^{\prime\prime\prime}$ and
$G^{\prime\prime\prime}$ is also a $K_{r+1}$-graph. Similar to Case i, we have

$\displaystyle\rho_{r}(G^{\prime\prime\prime})$ $\displaystyle\geq
r\sum_{\\{i_{1},\ldots,i_{r}\\}\in
C_{t}(G^{\prime\prime\prime})}x_{i_{1}}\cdots x_{i_{r}}$
$\displaystyle=r\sum_{\\{i_{1},\ldots,i_{r}\\}\in
C_{t}(G^{\prime})}x_{i_{1}}\cdots
x_{i_{r}}-rx_{i}WS_{G^{\prime}}(i,x)-rx_{k}WS_{G^{\prime}}(k,x)$
$\displaystyle+rx_{i}WS_{G^{\prime}}(j,x)+rx_{k}WS_{G^{\prime}}(j,x)+r\sum_{\\{i,k,i_{3},\ldots,i_{r}\\}\in
C_{t}(G^{\prime})}x_{i}x_{k}x_{i_{3}}\cdots x_{i_{r}}.$

Since $i$ and $k$ are adjacency in $G^{\prime}$ and each edge of $G^{\prime}$
is contained in an $r$-clique, we obtain

$\displaystyle r\sum_{\\{i,k,i_{3},\ldots,i_{r}\\}\in
C_{t}(G^{\prime})}x_{i}x_{k}x_{i_{3}}\cdots x_{i_{r}}>0.$

Hence, we have $\rho_{r}(G^{\prime\prime\prime})>\rho_{r}(G^{\prime})$. This
also contradicts the choice of $G^{\prime}$.

To sum up, the graph $G^{\prime}$ is a complete $r$-partite graph. ∎

######  Lemma 3.14.

For the $r$-clique spectral radius of the complete $r$-partite graph on $n$
vertices, we have

$\displaystyle\rho_{r}(T_{r}(n))=\max\\{\rho_{r}(H):\textup{$H$ is a complete
$r$-partite graph on $n$ vertices}\\},$

where $T_{r}(n)$ is the $r$-partite Turán graph.

###### Proof.

Let $H$ be the complete $r$-partite graph on $n$ vertices with partitions of
sizes $n_{1},n_{2},\ldots,n_{r}$. And let $\rho_{r}(H)$ be the $r$-clique
spectral radius of $H$ and $x=(x_{1},\ldots,x_{n})^{T}$ be the eigenvector
corresponding to $\rho_{r}(H)$. Since $H$ is $r$-clique connected, the
$r$-clique tensor $\mathcal{A}(H)$ is weakly irreducible. By Lemma 2.8, we
obtain $\rho_{r}(H)>0$ with the positive eigenvector
$x=(x_{1},\ldots,x_{n})^{T}$. The vertices in each part of $H$ have the same
neighborhood implies that the components of the eigenvectors corresponding to
these vertices are equal. Let components of the eigenvectors corresponding to
the vertices in each part of $H$ be $x_{n_{s}}$, $s=1,2,\ldots,r$. Hence, for
the characteristic equations of $\rho_{r}(H)$, we have

$\displaystyle\left\\{\begin{aligned}
&\rho_{r}(H)x_{n_{1}}^{r-1}=n_{2}n_{3}\cdots n_{r}x_{n_{2}}x_{n_{3}}\cdots
x_{n_{r}}\\\ &\rho_{r}(H)x_{n_{2}}^{r-1}=n_{1}n_{3}\cdots
n_{r}x_{n_{1}}x_{n_{3}}\cdots x_{n_{r}}\\\ &\cdots\\\
&\rho_{r}(H)x_{n_{r}}^{r-1}=n_{1}n_{2}\cdots n_{r-1}x_{n_{1}}x_{n_{2}}\cdots
x_{n_{r-1}}\end{aligned}\right.$ (4)

Multiply $r$ equations in (4), we get

$\displaystyle(\rho_{r}(H))^{r}x_{n_{1}}^{r-1}x_{n_{2}}^{r-1}\cdots
x_{n_{r}}^{r-1}=(n_{1}n_{2}\cdots
n_{r})^{r-1}x_{n_{1}}^{r-1}x_{n_{2}}^{r-1}\cdots x_{n_{r}}^{r-1}.$

Since $x_{n_{1}},x_{n_{2}},\ldots,x_{n_{r}}$ are all positive, the $r$-clique
spectral radius $\rho_{r}(H)=(n_{1}n_{2}\cdots n_{r})^{\frac{r-1}{r}}$. Thus,
the $r$-clique spectral radius $\rho_{r}(H)$ is maximal if and only if the
$n_{1},n_{2},\ldots,n_{r}$ are as equal as possible, that is $H\simeq
T_{r}(n)$. ∎

Next, we give the proof of Theorem 1.5 in the following.

###### Proof of Theorem 1.5.

By the definition of symmetric tensor, the entries of the $r$-clique tensor
$\mathcal{A}(G)$ of $G$ are invariant under any permutation of their indices,
thus $\mathcal{A}(G)$ is a symmetric tensor. For the $r$-clique tensor
$\mathcal{A}(G)=(a_{i_{1}i_{2}\cdots i_{r}})$, we have

$\displaystyle\sum_{i_{2},\ldots,i_{r}=1}^{n}a_{ii_{2}\cdots i_{r}}\
\textup{equals the number of $r$-cliques containing $i$}\ (i=1,\ldots,n).$ (5)

Let $\rho_{r}(G)$ be the spectral radius of the $r$-clique tensor
$\mathcal{A}(G)$. Since $\mathcal{A}(G)$ is a symmetric nonnegative tensor,
and by Lemma 2.6, we obtain

$\displaystyle\rho_{r}(G)=\max\left\\{x^{T}\mathcal{A}x^{r-1}:\sum_{i=1}^{n}x_{i}^{r}=1,x=(x_{1},\ldots,x_{n})^{T}\in\mathbb{R}_{+}^{n}\right\\}.$
(6)

Let $x_{i}=n^{-\frac{1}{r}}\ (i=1,\ldots,n)$ in (6). Then

$\displaystyle\rho_{r}(G)$ $\displaystyle\geq
x^{T}\mathcal{A}(G)x^{r-1}=\sum_{i_{1},\ldots,i_{r}}^{n}a_{i_{1}\cdots
i_{r}}x_{i_{1}}\cdots x_{i_{r}}$
$\displaystyle=\frac{\sum_{i=1}^{n}\sum_{i_{2},\ldots,i_{r}=1}^{n}a_{ii_{2}\cdots
i_{r}}}{n}$ $\displaystyle=\frac{r\cdot c_{r}(G)}{n}.$

Therefore, the inequality (2) is obtained.

If the number of $r$-cliques containing $i$ is equal for all $i\in V(G)$, and
by (5), then

$\displaystyle\sum_{i_{2},\ldots,i_{r}=1}^{n}a_{ii_{2}\cdots
i_{r}}=\frac{r\cdot c_{r}(G)}{n}\ (i=1,\ldots,n).$

For the spectral radius $\rho_{r}(G)$, by Lemma 2.7, we have

$\displaystyle\rho_{r}(G)=\frac{r\cdot c_{r}(G)}{n}.$

∎

Next, we show that the relation between Theorem 1.4 and inequality (3).
Through Theorem 1.4 and Theorem 1.5, for an $n$ vertices $K_{r+1}$-free graph
$G$, we obtain

$\displaystyle
c_{r}(G)\leq\left\lfloor\frac{n}{r}\rho_{r}(G)\right\rfloor\leq\left\lfloor\frac{n}{r}\rho_{r}(T_{r}(n))\right\rfloor=\left\lfloor\frac{n}{r}\left(\prod_{s=0}^{r-1}\left\lfloor\frac{n+s}{r}\right\rfloor\right)^{\frac{r-1}{r}}\right\rfloor.$

When $r\mid n$, we have
$\left\lfloor\frac{n}{r}\left(\prod_{s=0}^{r-1}\left\lfloor\frac{n+s}{r}\right\rfloor\right)^{\frac{r-1}{r}}\right\rfloor=\left(\frac{n}{r}\right)^{r}=c_{r}(T_{r}(n))$.
Thus, Theorem 1.4 implies (3) in the case when $r\mid n$. When $r\nmid n$, the
following example is considered. For $3$-partite Turán graph with 28 vertices,
the number of triangles in $T_{3}(28)$ is $c_{3}(T_{3}(28))=9\times 9\times
10=810<\left\lfloor\frac{28}{3}\left(\prod_{s=0}^{2}\left\lfloor\frac{28+s}{3}\right\rfloor\right)^{\frac{2}{3}}\right\rfloor=811$.

## Acknowledgement

This work is supported by the National Natural Science Foundation of China
(No. 11801115, No. 12071097 and No. 12042103), the Natural Science Foundation
of the Heilongjiang Province (No. QC2018002) and the Fundamental Research
Funds for the Central Universities.

References

## References

  * [1] W. Mantel. Problem 28, Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff. Wiskundige Opgaven 10 (1907) 60-61.
  * [2] P. Turán. On an extremal problem in graph theory. Mat. Fiz. Lapok 48 (1941) 436-452.
  * [3] Z. Füedi, M. Simonovits. The history of degenerate (bipartite) extremal graph problems, in: The Erdős Centennial, in: Bolyai Soc. Studies 25 (2013) 167-262.
  * [4] V. Nikiforov. Some new results in extremal graph theory: In surveys in Combinatorics 2011. London Math. Society Lecture Note Ser. 392 (2011) 141-181.
  * [5] Y.T. Li, W.J. Liu, L.H. Feng. A survey on spectral conditions for some extremal graph problems. Adv. Math. 51 (2) (2022) 193-258.
  * [6] E. Nosal. Eigenvalues of Graphs. Master’s thesis, University of Calgary, 1970.
  * [7] V. Nikiforov. More spectral bounds on the clique and independence numbers. J. Combin. Theory Ser. B 99 (6) (2009) 819-826.
  * [8] V. Nikiforov. Bounds on graph eigenvalues II. Linear Algebra Appl. 427 (2007) 183-189.
  * [9] V. Nikiforov. Some inequalities for the largest eigenvalue of a graph. Comb. Probab. Comput. 11 (2002) 179-189.
  * [10] H.Q. Lin, B. Ning, B. Wu. Eigenvalues and triangles in graphs. Comb. Probab. Comput. 30 (2021) 258-270.
  * [11] M.Q. Zhai, J.L. Shu. A spectral version of Mantel’s theorem. Discrete Math. 345 (2022) 112630.
  * [12] Y.T. Li, Y.J. Peng. Refinement on spectral Turán’s theorem. (2022) arXiv: 2204.09194v3.
  * [13] L. Qi. Eigenvalues of a real supersymmetric tensor. Journal of symbolic computation 40 (2005) 1302-1324.
  * [14] L. Lim. Singular values and eigenvalues of tensors: a variational approach. IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005, 129-132.
  * [15] S.D. Yang. Description of second-order three-dimensional magnetic neutral points. Phys. Plasmas 24 (1) (2017) 012903.
  * [16] K. Batselier, Z. Chen, N. Wong. Tensor network alternating linear scheme for MIMO volterra system identification. Automatica 84 (2017) 26-35.
  * [17] B. Chen, S. He, Z. Li, S. Zhang. On new classes of nonnegative symmetric tensors. SIAM J. Optim. 27 (1) (2017) 292-318.
  * [18] A.R. Benson, D.F. Gleich, L.H. Lim. The spacey random walk: a stochastic process for higher-order data. SIAM Rev. 59 (2) (2017) 321-345.
  * [19] M. Brazell, N. Li, C. Navasca, C. Tamon. Solving multilinear systems via tensor inversion. SIAM J. Matrix Anal. Appl. 34 (2013) 542-570.
  * [20] L. Sun, B. Zheng, C. Bu, Y. Wei. Moore-Penrose inverse of tensors via Einstein product. Linear and Multilinear Algebra 64 (4) (2016) 686-698.
  * [21] J. Cooper, A. Dutle. Spectra of uniform hypergraphs. Linear Algebra Appl. 436 (9) (2012) 3268-3292.
  * [22] Y. Chen, L. Qi, X. Zhang. The Fiedler vector of a Laplacian tensor for hypergraph partitioning. SIAM J. Sci. Comput. 39 (2017) A2508-A2537.
  * [23] H. Li, B. Mohar. On the first and second eigenvalue of finite and infinite uniform hypergraphs. Proc Amer Math Soc. 147 (3) (2019) 933-946.
  * [24] Y. Fan, T. Huang, Y. Bao, C. Zhuan-Sun, Y. Li. The spectral symmetry of weakly irreducible nonnegative tensors and connected hypergraphs. Trans Amer Math Soc. 372 (3) (2019) 2213-2233.
  * [25] J. Clark, J. Cooper. A Harary-Sachs theorem for hypergraphs. J. Combin. Theory Ser B. 149 (2021) 1-15.
  * [26] C. Liu, J. Zhou, C. Bu. The high order spectrum of a graph and its applications in graph colouring and clique counting. Linear and Multilinear Algebra (2022) DOI: 10.1080/03081087.2022.2103490.
  * [27] P. Erdős. On the number of complete subgraphs contained in certain graphs. (Russian summary) Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962) 459-464.
  * [28] A.A. Zykov. On some properties of linear complexes. Mat. Sbornik N.S. 24 (66) (1949) 163-188.
  * [29] E. Györi, J. Pach, M. Simonovits. On the maximal number of certain subgraphs in $K_{r}$-free graphs. Graphs Combin. 7 (1991) 31-37.
  * [30] L. Qi. Symmetric nonnegative tensors and copositive tensors. Linear Algebra Appl. 439 (2013) 228-238.
  * [31] Y. Yang, Q. Yang. Further results for Perron-Frobenius theorem for nonegative tensors. SIAM J. Matrix Anal. Appl. 31 (2010) 2517-2530.
  * [32] S. Friedland, S. Gaubert, L. Han. Perron-Frobenius theorem for nonnegative multilinear forms and extensions. Linear Algebra Appl. 438 (2013) 738-749.
  * [33] M.I. Khan, Y.Z. Fan. On the spectral radius of a class of non-odd-bipartite even uniform hypergraphs. Linear Algebra Appl. 480 (2015) 93-106.
  * [34] J.Y. Shao, H.Y. Shan, L. Zhang. On some properties of the determinants of tensors. Linear Algebra Appl. 439 (2013) 3057-3069.
  * [35] D. Cvetković, M. Doob, H. Sachs. Spectra of Graphs. Theory and Applications. New York (NY): Academic Press; 1980.