The reviewed record of science sign in
Pith

arxiv: 2009.10294 · v1 · pith:TDP2SKXX · submitted 2020-09-22 · math.CO

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

Reviewed by Pithpith:TDP2SKXXopen to challenge →

classification math.CO
keywords mathscrdegreesizegraphleastgivengraphsaddition
0
0 comments X
read the original 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.