REVIEW
On the least size of a graph with a given degree set -- II
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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 $\mathscr D$ is $1+\max \mathscr D$. Tripathi & Vijay considered the analogous problem concerning the least size of graphs with degree set $\mathscr D$. We expand on their results, and determine the least size of graphs with degree set $\mathscr D$ when (i) $\min \mathscr D \mid d$ for each $d \in \mathscr D$; (ii) $\min \mathscr D=2$; (iii) $\mathscr D=\{m,m+1,\ldots,n\}$. In addition, given any $\mathscr D$, we produce a graph $G$ whose size is within $\min \mathscr D$ of the optimal size, giving a $\big(1+\frac{2}{d_1+1})$-approximation, where $d_1=\max \mathscr D$.
Discussion (0). Continue with ORCID to comment.