Extremal Problems for the $p$-Spectral Radius of Graphs

Abstract

The $p$-spectral radius of a graph $G\ $of order $n$ is defined for any real number $p\geq1$ as

$$\lambda^{(p)}(G) =\max\{ 2\sum_{\{i,j\}\in E(G)} x_ix_j:x_1,\ldots,x_n\in\mathbb{R}\text{ and }\vert x_{1}\vert ^{p}+\cdots+\vert x_n\vert^{p}=1\} .$$

The most remarkable feature of $\lambda^{(p)}$ is that it seamlessly joins several other graph parameters, e.g., $\lambda^{(1)}$ is the Lagrangian, $\lambda^{(2)  }$ is the spectral radius and $\lambda^{(\infty)  }/2$ is the number of edges. This paper presents solutions to some extremal problems about $\lambda^{(p)}$, which are common generalizations of corresponding edge and spectral extremal problems.

Let $T_{r}\left(  n\right)  $ be the $r$-partite Turán graph of order $n$. Two of the main results in the paper are:

(I) Let $r\geq2$ and $p>1.$ If $G$ is a $K_{r+1}$-free graph of order $n$, then
$$\lambda^{(p)}(G)  <\lambda^{(p)}(T_{r}(n)),$$ unless $G=T_{r}(n)$.

(II) Let $r\geq2$ and $p>1.$ If $G\ $is a graph of order $n,$ with

$$\lambda^{(p)}(G)>\lambda^{(p)}(  T_{r}(n))  ,$$

then $G$ has an edge contained in at least $cn^{r-1}$ cliques of order $r+1$, where $c$ is a positive number depending only on $p$ and $r.$