Extremal problems for the p-spectral radius of graphs

zbMATH Open1300.05161arXiv1402.3239MaRDI QIDQ405309FDOQ405309

Authors: Vladimir Nikiforov, Liying Kang 

Publication date: 4 September 2014

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

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

Full work available at URL: https://arxiv.org/abs/1402.3239

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

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

zbMATH Keywords

extremal problemsclique number[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Tur%EF%BF%BD%EF%BF%BDn+problems&go=Go Tur��n problems]\(p\)-spectral radiussaturation 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)

Cites Work

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

Cited In (12)

• Some extremal problems for hereditary properties of graphs
• Refinement on Spectral Turán’s Theorem
• Spectral extrema for graphs: the Zarankiewicz problem
• 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)