On the least size of a graph with a given degree set -- II

Abstract

The degree set of a finite simple graph $G$ is the set of distinct degrees of vertices of $G$. A theorem of Kapoor, Polimeni & Wall asserts that the least order of a graph with a given degree set $\mathcal{D}$ is $1+\max \mathcal{D}$. Tripathi & Vijay considered the analogous problem concerning the least size of graphs with degree set $\mathcal{D}$. We expand on their results, and determine the least size of graphs with degree set $\mathcal{D}$ when (i) $\min \mathcal{D}\mid d$ for each $d\in \mathcal{D}$; (ii) $\min \mathcal{D}=2$; (iii) $\mathcal{D}=\{m,m+1,\dots ,n\}$. In addition, given any $\mathcal{D}$, we produce a graph $G$ whose size is within $\min \mathcal{D}$ of the optimal size, giving a $(1+\frac{2}{d_1+1})$-approximation, where $d_1=\max \mathcal{D}$.

arXiv comment11 pages