Extremal problems for the \(p\)-spectral radius of graphs

Liying Kang¹ ; Vladimir Nikiforov²

¹Department of Mathematics, Shanghai University, Shanghai, PR China.
²Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA

The electronic journal of combinatorics, Tome 21 (2014) no. 3

Résumé

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

Détail

DOI : 10.37236/4113

Classification : 05C50, 05C35, 05C69
Mots-clés : \(p\)-spectral radius, clique number, extremal problems, Turán problems, saturation problems