论文标题
在具有给定度的图表的最小尺寸上-II
On the least size of a graph with a given degree set -- II
论文作者
论文摘要
有限简单的图表$ g $的学位集是$ g $的一组不同程度的顶点。 Kapoor，Polimeni＆Wall的定理断言，具有给定学位$ \ Mathscr d $的图表的最小顺序是$ 1+\ max \ max \ mathscr d $。 Tripathi＆Vijay考虑了与学位设置$ \ Mathscr d $的图形最小尺寸的类似问题。我们扩展了他们的结果，并确定（i）$ \ min \ mathscr d \ mathscr d \ mid d $ in \ in \ mathscr d $; （ii）$ \ min \ mathscr d = 2 $; （iii）$ \ mathscr d = \ {m，m+1，\ ldots，n \} $。此外，考虑到任何$ \ mathscr d $，我们产生了一个图形$ g $，其大小在$ \ min \ mathscr d $的最佳尺寸之内，提供了$ \ big（1+ \ frac {2} {2} {d_1+1}）$ - 近似值，其中$ d_1 = \ d_1 = \ max \ mathscr d $。
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$.
