Metraipolis › archive › dc_aa4e8da79831

Spreads of degrees in graphs — arXiv:2609.19762

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.19762
License (as archived): CC0-1.0
Archived: 2026-10-10T04:47:04.970Z
SHA-256 of the archived text: b7aa9122777475f6f7e5881b9693e4cd089938fce0f99e1f0d7b188ff7328d28
Stable URL of this page: https://metraipolis.com/documento/dc_aa4e8da79831

How to cite

Spreads of degrees in graphs — arXiv:2609.19762 — arXiv (en), https://arxiv.org/abs/2609.19762 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_aa4e8da79831 (Metraipolis archive dc_aa4e8da79831, sha256 b7aa9122777475f6f7e5881b9693e4cd089938fce0f99e1f0d7b188ff7328d28)

BibTeX

@misc{dcaa4e8da79831,
  title = {Spreads of degrees in graphs — arXiv:2609.19762},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.19762},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_aa4e8da79831; sha256 b7aa9122777475f6f7e5881b9693e4cd089938fce0f99e1f0d7b188ff7328d28},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19762. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a graph $G$ and a set $B\subseteq V(G)$, the spread $\mathrm{sp}(B)$ of $B$ is the difference between the largest and the smallest degree in $G$ of a vertex of $B$, and for an integer $k\geq0$ the parameter $\mathrm{sp}(G,k)$ is the largest cardinality of a set $B$ with $\mathrm{sp}(B)\leq k$. Caro, Lauri and Zarb derived a lower bound for $\mathrm{sp}(G,k)$ and, among several families of graphs, considered \[ \mathrm{MOP}(n,k)=\min \{\mathrm{sp}(G,k):G\text{ is a maximal outerplanar graph of order }n\} \] and determined $\mathrm{MOP}(n,k)$ up to an additive constant for every $k\not =2,$ leaving the case $k=2$ open, with the bounds $4n/9\leq \mathrm{MOP}(n,2)\leq (5n+19)/11$. We first prove a lower bound on $\mathrm{sp}(G,k)$ for an arbitrary graph $G$ in terms of its order $n$, its number of edges $m$ and its minimum degree $\delta $. This lower bound contains the bounds of Caro, Lauri and Zarb and, for $k=0$, the bound $\mathrm{rep}(G)\geq \left\lceil n/(2d-2\delta +1)\right\rceil $ of Caro and West, where $d=2m/n$. We determine when this lower bound is attained, exhibit explicit graphs attaining it, and show that it is exact for all graphs once $n\geq n_{0}(\delta ,k,d)$. We then apply the bound to maximal outerplanar graphs: adjusting the count to this class we prove \[ \mathrm{MOP}(n,2)\geq \left\lceil \frac{4n+10}{9}\right\rceil \qquad \text{for every }n\geq 14, \] with equality for $n\equiv 2\ (\mathrm{mod}\ 18)$, and $\mathrm{MOP}(n,2)=4n/9+O(1)$ for every $n$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.19762 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T04:15:33.126Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).