Spreads of degrees in maximal planar graphs -- an exposition

Abstract

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\ge 0$ the parameter $\mathrm{sp}(G,k)$ is the largest cardinality of a set $B$ with $\mathrm{sp}(B)\le k$. Caro, Lauri and Zarb asked for the minimum of $\mathrm{sp}(G,k)$ over the maximal planar graphs of order $n$; we write $\mathrm{MP}(n,\delta ,k)$ for this minimum over the maximal planar graphs of order $n$ and minimum degree $\delta \in \{3,4,5\}$. This manuscript is intended as an exposition of the subject of spread in the degree sequence of a graph $G$, with emphasis on maximal planar graphs. We apply the general lower bound of the companion paper \cite{P1} to this class, together with further ideas, some based on Caro--West and Caro--Lauri--Zarb and some new. In particular we asymptotically determine the values of $\mathrm{MP}(n,\delta ,k)$ for every pair $(\delta ,k)$ with $\delta \in \{3,4,5\}$ and $k\ge 0$. This solution recovers the case $\mathrm{MP}(n,\delta ,0)$, which is the repetition number $\mathrm{rep}(G)$ introduced by Caro and West.