Exact and Approximate Results on the Least Size of a Graph with a Given Degree Set

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 $D$ is $1+\max D$. Tripathi & Vijay considered the analogous problem concerning the least size of graphs with degree set $D$. We expand on their results, and determine the least size of graphs with degree set $D$ when (i) $\min D \mid d$ for each $d \in D$; (ii) $\min D=2$; (iii) $D={m,m+1,…,n}$. In addition, given any D, we produce a graph $G$ whose size is within $\min D$ of the optimal size, giving a $(1+2 d_1+1)$-approximation, where $d_1 = \max D$.

arXiv