Degree powers in graphs with forbidden subgraphs (Q1883656): Difference between revisions
From MaRDI portal
Set profile property. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: math/0405001 / rank | |||
Normal rank |
Latest revision as of 23:38, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Degree powers in graphs with forbidden subgraphs |
scientific article |
Statements
Degree powers in graphs with forbidden subgraphs (English)
0 references
13 October 2004
0 references
Summary: For every real \(p>0\) and simple graph \(G\), set \[ f(p,G) =\sum_{u\in V(G)}d^p(u), \] and let \(\varphi(r,p,n)\) be the maximum of \(f(p,G)\) taken over all \(K_{r+1}\)-free graphs \(G\) of order \(n\). We prove that, if \(0<p<r\), then \[ \varphi(r,p,n)=f\bigl(p,T_r(n)\bigr), \] where \(T_r(n)\) is the \(r\)-partite Turán graph of order \(n\). For every \(p\geq r+\lceil\sqrt{2r}\rceil\) and \(n\) large, we show that \[ \varphi(p,n, r)>(1+\varepsilon)f\bigl(p,T_r(n)\bigr) \] for some \(\varepsilon= \varepsilon(r)>0\). Our results settle two conjectures of \textit{Y. Caro} and \textit{Y. Yuster} [Electron. J. Comb. 7, Research paper R47 (2000; Zbl 0986.05059)].
0 references
Turán graph
0 references