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.$