Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2009.10294 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915008797999104 |
|---|---|
| author | Moondra, Jai Sahdev, Aditya Tripathi, Amitabha |
| author_facet | Moondra, Jai Sahdev, Aditya Tripathi, Amitabha |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2009_10294 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | On the least size of a graph with a given degree set -- II Moondra, Jai Sahdev, Aditya Tripathi, Amitabha Combinatorics 05C07 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$. |
| title | On the least size of a graph with a given degree set -- II |
| topic | Combinatorics 05C07 |
| url | https://arxiv.org/abs/2009.10294 |