Extremal problems for the p-spectral radius of graphs

MaRDI QIDQ405309zbMATH OpenFDO

Authors Vladimir Nikiforov, Liying Kang

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3239, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p21

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal problemsclique number\(p\)-spectral radiussaturation problemsTurán problems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The $p$-spectral radius of a graph $G$of order $n$ is defined for any real number $pgeq1$ as [ lambda^{left( p ight) }left( G ight) =maxleft{ 2sum_{{i,j}in Eleft( G ight) }x_{i}x_{j}:x_{1},ldots,x_{n}inmathbb{R} ext{ and }leftvert x_{1} ightvert ^{p}+cdots+leftvert x_{n} ightvert ^{p}=1 ight} . ] The most remarkable feature of $lambd{a}^{left(pight)}$ is that it seamlessly joins several other graph parameters, e.g., $lambd{a}^{left(1ight)}$ is the Lagrangian, $lambd{a}^{left(2ight)}$ is the spectral radius and $lambd{a}^{left(inftyight)}/2$ is the number of edges. This paper presents solutions to some extremal problems about $lambd{a}^{left(pight)}$, which are common generalizations of corresponding edge and spectral extremal problems. Let $T_{r}left(night)$ be the $r$-partite Tur'{a}n graph of order $n.$ Two of the main results in the paper are: (I) Let $rgeq2$ and $p>1.$ If $G$ is a $K_{r+1}$-free graph of order $n,$ then [ lambda^{left( p ight) }left( G ight) <lambda^{left( p ight) }left( T_{r}left( n ight) ight) , ] unless $G=T_{r}left(night).$ (II) Let $rgeq2$ and $p>1.$ If $G$is a graph of order $n,$ with [ lambda^{left( p ight) }left( G ight) >lambda^{left( p ight) }left( T_{r}left( n ight) ight) , ] 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.$

Recommendations

• An extremal problem for the spectral radius of a graph
• Extremal problems for the \(p\)-spectral radius of Berge hypergraphs
• Extremal problems on distance spectra of graphs
• An extremal problem on Q-spectral radii of graphs with given size and matching number
• Extremal results on distance Laplacian spectral radius of graphs
• Some new results and problems in spectral extremal graph theory
• The extremal \(p\)-spectral radius of Berge hypergraphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Extremal graph characterization from the bounds of the spectral radius of weighted graphs
• Spectral extremal problems for hypergraphs

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A spectral condition for odd cycles in graphs
• Analytic methods for uniform hypergraphs
• Bounds on graph eigenvalues. II
• Joints in graphs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On a valence problem in extremal graph theory
• On the number of complete subgraphs and circuits contained in graphs
• On the structure of linear graphs
• Sharp bounds for the signless Laplacian spectral radius in terms of clique number
• Some Inequalities for the Largest Eigenvalue of a Graph
• Some extremal problems for hereditary properties of graphs
• Some new results in extremal graph theory
• Spectral bounds for the clique and independence numbers of graphs
• Spectral extremal problems for hypergraphs
• Spectral saturation: inverting the spectral Turán theorem
• The \(p\)-spectral radius of \(k\)-partite and \(k\)-chromatic uniform hypergraphs
• Turán's theorem inverted

Cited in

(12)

• Some extremal problems for hereditary properties of graphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Refinement on Spectral Turán’s Theorem
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• Extremal problems for the \(p\)-spectral radius of Berge hypergraphs
• Proof of a conjecture on extremal spectral radii of blow-up graphs
• The extremal \(p\)-spectral radius of Berge hypergraphs
• The \(p\)-spectral radius of \(k\)-partite and \(k\)-chromatic uniform hypergraphs
• Spectral extremal graphs for the bowtie
• The α-normal labelling method for computing the p-spectral radii of uniform hypergraphs
• The \(p\)-spectral radius of the Laplacian matrix
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles

This page was built for publication: Extremal problems for the \(p\)-spectral radius of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405309)