Spreads of degrees in graphs
Abstract
For a graph G and a set B⊆ V(G), the spread 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≥0 the parameter sp(G,k) is the largest cardinality of a set B with sp(B)≤ k. Caro, Lauri and Zarb derived a lower bound for sp(G,k) and, among several families of graphs, considered MOP(n,k)=min {sp(G,k):G is a maximal outerplanar graph of order n} and determined MOP(n,k) up to an additive constant for every knot =2, leaving the case k=2 open, with the bounds 4n/9≤ MOP(n,2)≤ (5n+19)/11. We first prove a lower bound on sp(G,k) for an arbitrary graph G in terms of its order n, its number of edges m and its minimum degree δ. 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δ+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≥ n0(δ,k,d). We then apply the bound to maximal outerplanar graphs: adjusting the count to this class we prove MOP(n,2)≥ ⌈ (4n+10)/9⌉ for every n≥ 14, with equality for n≡ 2 (mod 18), and MOP(n,2)=4n/9+O(1) for every n.
Related
- Spreads of degrees in maximal planar graphs -- an exposition
- Edge universality of random regular graphs of growing degrees
- Short Paper No. 1: Relation between integer sequence A319433 and the maximum degrees of finite linear Jaco graphs
- Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
- Uniform duplication-divergence random graphs I: Degrees and Local Limits
BibTeX
@misc{caro2026spreads,
title = {{Spreads of degrees in graphs}},
author = {Yair Caro and Riste Škrekovski and Christina Zarb},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19762},
eprint = {2609.19762},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19762},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Spreads of degrees in graphs
AU - Yair Caro
AU - Riste Škrekovski
AU - Christina Zarb
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.19762
UR - https://arxiv.org/abs/2609.19762
AB - For a graph G and a set B⊆ V(G), the spread 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≥0 the parameter sp(G,k) is the largest cardinality of a set B with sp(B)≤ k. Caro, Lauri and Zarb derived a lower bound for sp(G,k) and, among several families of graphs, considered MOP(n,k)=min {sp(G,k):G is a maximal outerplanar graph of order n} and determined MOP(n,k) up to an additive constant for every knot =2, leaving the case k=2 open, with the bounds 4n/9≤ MOP(n,2)≤ (5n+19)/11. We first prove a lower bound on sp(G,k) for an arbitrary graph G in terms of its order n, its number of edges m and its minimum degree δ. 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δ+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≥ n_0(δ,k,d). We then apply the bound to maximal outerplanar graphs: adjusting the count to this class we prove MOP(n,2)≥ ⌈ (4n+10)/9⌉ for every n≥ 14, with equality for n≡ 2 (mod 18), and MOP(n,2)=4n/9+O(1) for every n.
ER -