On the least size of a graph with a given degree set (Q860412)

The degree set of a simple graph \(G\) is the set \({\mathcal D}(G)\) consisting of the distinct degrees of vertices in \(G.\) A graph \(G\) is called a \((q,{\mathcal D})\)-graph if it has \(q\) edges and degree set \({\mathcal D}.\) For a given finite set of positive integers \({\mathcal D}\) the least \(q\) for which there exists a \((q,{\mathcal D})\)-graph is denoted by \(l_q({\mathcal D}).\) In the paper \(l_q({\mathcal D})\) is determined when (i) \(| {\mathcal D}| \leq 3;\) (ii) \({\mathcal D}=\{1,2,\dots,n\};\) (iii) \(\min{\mathcal D}\geq | {\mathcal D}| .\) In all cases upper and lower bounds for \(l_q({\mathcal D})\) are given.