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\ge 1$ as \[ λ^{\left( p\right) }\left( G\right) =\max\left\{ 2\sum_{\{i,j\}\in E\left( G\right) \ }x_{i}x_{j}:x_{1},\ldots,x_{n}\in\mathbb{R}\text{ and }\left\vert x_{1}\right\vert ^{p}+\cdots+\left\vert x_{n}\right\vert ^{p}=1\right\} . \] The most remarkable feature of ${\lambda }^{\left(p\right)}$ is that it seamlessly joins several other graph parameters, e.g., ${\lambda }^{\left(1\right)}$ is the Lagrangian, ${\lambda }^{\left(2\right)}$ is the spectral radius and ${\lambda }^{\left(\infty \right)}/2$ is the number of edges. This paper presents solutions to some extremal problems about ${\lambda }^{\left(p\right)}$, 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\ge 2$ and $p>1.$ If $G$ is a $K_{r+1}$-free graph of order $n,$ then \[ λ^{\left( p\right) }\left( G\right) <λ^{\left( p\right) }\left( T_{r}\left( n\right) \right) , \] unless $G=T_r\left(n\right).$ (II) Let $r\ge 2$ and $p>1.$ If $G$is a graph of order $n,$ with \[ λ^{\left( p\right) }\left( G\right) >λ^{\left( p\right) }\left( T_{r}\left( n\right) \right) , \] then $G$ has an edge contained in at least $c{n}^{r-1}$ cliques of order $r+1,$ where $c$ is a positive number depending only on $p$ and $r.$

21 pages. Some minor corrections in v2

References in corpus (2)

• An analytic theory of extremal hypergraph problems
• The p-spectral radius of k-partite and k-chromatic uniform hypergraphs