Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.11587 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913202962432000 |
|---|---|
| author | Gerbner, Dániel |
| author_facet | Gerbner, Dániel |
| contents | Given a graph $G$ with degree sequence $d_1,\dots, d_n$ and a positive integer $r$, let $e_r(G)=\sum_{i=1}^n d_i^r$. We denote by $\mathrm{ex}_r(n,F)$ the largest value of $e_r(G)$ among $n$-vertex $F$-free graphs $G$, and by $\mathrm{ex}(n,S_r,G)$ the largest number of stars $S_r$ in $n$-vertex $F$-free graphs. The \textit{broom} $B(\ell,s)$ is the graph obtained from an $\ell$-vertex path by adding $s$ new leaves connected to a penultimate vertex $v$ of the path.
We determine $\mathrm{ex}_r(n,B(\ell,s))$ for $r\ge 2$, any $\ell,s$ and sufficiently large $n$, proving a conjecture of Lan, Liu, Qin and Shi. We also determine $\mathrm{ex}(n,S_r,B(\ell,s))$ for $r\ge 2$, any $\ell,s$ and sufficiently large $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11587 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Degree powers and number of stars in graphs with a forbidden broom Gerbner, Dániel Combinatorics Given a graph $G$ with degree sequence $d_1,\dots, d_n$ and a positive integer $r$, let $e_r(G)=\sum_{i=1}^n d_i^r$. We denote by $\mathrm{ex}_r(n,F)$ the largest value of $e_r(G)$ among $n$-vertex $F$-free graphs $G$, and by $\mathrm{ex}(n,S_r,G)$ the largest number of stars $S_r$ in $n$-vertex $F$-free graphs. The \textit{broom} $B(\ell,s)$ is the graph obtained from an $\ell$-vertex path by adding $s$ new leaves connected to a penultimate vertex $v$ of the path. We determine $\mathrm{ex}_r(n,B(\ell,s))$ for $r\ge 2$, any $\ell,s$ and sufficiently large $n$, proving a conjecture of Lan, Liu, Qin and Shi. We also determine $\mathrm{ex}(n,S_r,B(\ell,s))$ for $r\ge 2$, any $\ell,s$ and sufficiently large $n$. |
| title | Degree powers and number of stars in graphs with a forbidden broom |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.11587 |