数理解析研究所講究録
第 1744 巻 2011 年 151-158

151

Degree sequences related to degree set(extended abstract)
Shingo Osawa

Yukio Shibata**

Department of Computer Science, Gunma University,
1-5-1 Tenjin-cho, Kiryu, Gunma, 376-8515 Japan

1

Introduction

A sequenceof nonnegative integers is called graphical if there exists
with vertices
such thathas degree
for each. Certainly the conditions $d_{k}\leq n-1$ for all andbeing even arenecessary for a sequence to be graphical, but these conditions are not sufficient.
A neccessary and sufficient conditon for a sequence to be graphical was foundby Havel [4] and later rediscoverd by Hakimi [3]. Another characterizationthat determines which sequences are graphical is due to Erd\"os and Gallai [1].
Recently, Ttipathi and Vijay [8] improved the result of Erd\"os and Gallai.
The degree set of a graph is the set $D$ consisting of the distinct degrees
of vertices in . The question which sets of positive integers are the degree
sets of graphs has been investigated. Kapoor, Polimeni and Wall [7] completely
answered that question, and Thripathi and Vijay [10] have given a short proof
for the theorem of them. Recently, Tripathi and Vijay [9] have given the new
result on the graph with the least order and the least size among graphs withthe given degree set.
We propose a basic ploblem. If a degree sequence is given, we immediately
obtain a unique degree set. Conversely, if a degree set is given, we wonder
whether there is a procedure to obtain graphical degree sequences with thegiven degree set. In general, there are infinitely many graphs with the given
degree set. Even if the order is restricted to the least one, we might find several
graphs with the given degree set.
Here, we are in the state to propose the following problem.
Problem For a given degree set, how many degree sequences with the leastorder are there?
$d_{1},$

a simple graph$d_{2},$$\ldots,$$d_{n}$$G$$v_{1},$ $v_{2},$$k$$\ldots,$$v_{n}$$v_{k}$$k$$d_{k}$$\sum_{k=1}^{n}d_{k}$

$G$

$G$

2
Let

Degree 2-set
$p$

and

$q$

be the number of vertices and the number of edges of the graph, respectively. Let $\mathcal{D}=\{a, b\}$ be a degree set, where $a,$ $b>0$ , and $a>b$ .
We shall employ the notation $(c)_{m}$ to denote $m$ occurrence of the integer inthe degree sequence. We may denote a degree sequence by $s=(a)_{x}(b)_{y}$ , where$a>b$ , and $x,$ $y>0$ with $x+y=p$ .
$G$

$c$

*This work is partially supported by Grants-in-Aid for Scientific Research (C) from Japan
Society for the Promotion of Science, KAKENHI 21500003.

152
Then we obtain the following equation;$\{\begin{array}{l}ax+by=2q,x+y=p,x, y>0.\end{array}$

Since
tions

$x$

and

$y$

(1)

are positive integer solutions, we obtain next necessay condi-$\{\begin{array}{l}(a-b)|(2q-bp),(a-b)|(ap-2q),2q-bp>0,ap-2q>0.\end{array}$(2)

Under the conditions (2), we have the solution for the equation (1) as follows,$\{\begin{array}{l}x=_{a-b}^{\underline{2}_{L^{-}A}}b,y=_{a-b}^{a}-L^{-}2\Delta.\end{array}$(3)

Because of a condition for graphs, $p\geq a+1$ . Then we consider a graph withorder $p=a+1$ . We set $p=a+1$ for the conditions (2) and obtain the following
conditions;$\{\begin{array}{l}(a-b)|2q-b(a+1),(a-b)|a(a+1)-2q,2q-b(a+1)>0,a(a+1)-2q>0.\end{array}$(4)

From the third and the fourth inequalities of the equation in (4), we secure.
the bound for , that is
We have the solution under the conditions (4),$q$$\frac{b(a+1)}{2}<q<\frac{a(a+1)}{2}$$\{x=\frac{2q-b(a+1)}{a(a+1)-2qa-b}y=\frac{}{a-b},$(5)

For convenience, we may write $a=k+l$ and $b=k$ , and we have$\{\frac{y--x=k(k+l}{2}\frac{-2q(k+l)(k+l+1)}{2}\frac{\frac{2q-k(k+l+1)}{(k+\iota)(\iota_{+l+1)}}}{+1)<q<l},$(6)

Lemma 2.1 The number of vertices with the maximum degree $k+l$ is less thanor equal to the minimum degree , that is $x\leq k$ .
$k$Lemma 2.2 The number of edges
that is $q\leq k(k+2l+1)/2$ .

$q$

is less than or equal to $k(k+2l+1)/2$ ,By Lemma 2.2, we rewrite the equation (6) as follows;$\{\frac{x=y--k(k+l+}{2}\frac{-2qk(k+2l+1)}{2}\frac{\frac{2q-k(k+l+1)}{(k+l)(k+l+1)l}}{1)<q\leq l},$

(7)

153
Theorem 2.1 Let $\mathcal{D}=\{k+l, k\}$ be a degree set, where $k>0$ and $l>0$ . Then,
we have the following properties:
1.

$k$

and

$l$

are even.

There exist degree sequences $s=(k+l)_{x}(l)_{y}$ for each $(x, y)=(1, k+l)$ ,$(k, l+1)$ . Moreover if $(x, y)=(1, k+l)$ , a number of$(2, k+l-1),$
edges $q= \frac{(k+1)(k+l)}{2}$ is minimum, and if $(x, y)=(k, l+1),$ $q= \frac{k(k+2l+1)}{2}$is the maximum.
$k$$\ldots,$2.

$k$

is even and$l$is odd.

degree sequences $s=(k+l)_{x}(l)_{y}$ for each $(x, y)=(2, k+l-1)$ ,$(k, l+1)$ . Moreover if $(x, y)=(2, k+l-1)$ , a number of$q=\frac{k(k+l+1)}{2}+l$edges
is minimum, and if $(x, y)=(k, l+1),$ $q= \frac{k(k+2l+1)}{2}$There exist$\frac{k}{2}$$(4, k+l-3),$$\ldots,$

is maximum.

3.

is odd and is even.
There exist degree sequences $s=(k+l)_{x}(l)_{y}$ for each $(x, y)=(1, k+l)$ ,$(k, l+1)$ . Moreover if $(x, y)=(1, k+l)$ , a number of$(2, k+l-1),$$q=\frac{(k+1)(k+l)}{2}$edges
is minimum, and if $(x, y)=(k, l+1),$ $q= \frac{k(k+2l+1)}{2}$is maximum.

$k$

$l$

$k$

$\ldots,$

4.

$k$

and

$l$

are odd.

degree sequences $s=(k+l)_{x}(l)_{y}$ for each $(x, y)=(1, k+l)$ ,There exist$(k, l+1)$ . Moreover if $(x, y)=(1, k+l)$ , the number$(3, k+l-2),$
is minimum, and if $(x, y)=(k, l+1),$ $q=$of edgesis maximum.
$r\frac{k}{2}\rceil$$\ldots,$$q= \frac{k(k+l+1)}{2}+\frac{l}{2}$$\frac{k(k+l+1)}{2}+\frac{k}{2}l$If $\prime D=\{k+l, k\}$ , then KPW algorithm produces a graph, whileTV algorithm generates a graph. These graphs are isomorphic andhave $k(k+2l+1)/2$ edges, and the number of edges is maximum.
$K_{k}+\overline{K_{l+1}}$$K_{l+1}\cup\overline{K_{k}}$Cororally 2.1 Let $\mathcal{D}=\{k, 1\}$ be a degree set, where $k\geq 2$ . Then the gmph
with the degree set CD is unique.

Cororally 2.2 Let $D=\{2k+1,2\}$ be a degree set, where $k\geq 1$ . Then thegmph with the degree set $D$ is unique.
Therefore, the graph generated by KPW algorithm and TV algorithm is theabove one.

Cororally 2.3 Let $\mathcal{D}=\{2k, 2\}$ be a degree set, where $k\geq 2$ . There exist twographs with the degree set D.
The graph generated by KPW algorithm and TV algorithm has the degree
sequence $s=(2k)_{2}(2)_{2k-1}$ , and the number of edges $q=4k-1$ is maximum.

2.1

ExampleLet $D=\{9,4\}$ be a degree set. We have $k=4$ and $l=5$ . By Theorem 2.1, we
obtain two degree sequences, (9) (4) and (9) (4) . The sequence (9) (4) has
unique graph, while another has three nonisomorphic graphs $K_{2}+C_{8},$ $K_{2}+2C_{4}$and $K_{2}+(C_{3}\cup C_{5})$ .

154
Degree n-set

3

Let and be the number of vertices and the number of edges of the graphbe a degree set, where $d_{1}>d_{2}>$, respectively. Let. $..>d_{n}>0$ . We shall employ the notation
occurrence ofto denotethe integer in the degree sequence. We may denote a degree sequence by, where $d_{1}>d_{2}>\cdots>d_{n}>0$ and $m_{i}>0$ ,$1\leq i\leq n$ , with $m_{1}+m_{2}+\cdots+m_{n}=p$ .
Then we obtain the following equation;
$p$

$q$

$G$

$\mathcal{D}=\{d_{1}, d_{2}, \ldots, d_{n}\}$$(c)_{m}$

$m$

$c$

$s=(d_{1})_{m_{1}}(d_{2})_{m_{2}},$$\ldots,$$(d_{n})_{m_{n}}$(8)$\{\begin{array}{l}d_{1}m_{1}+d_{2}m_{2}+\cdots+d_{n}m_{n}=2q,m_{1}+m_{2}+\cdots+m_{n}=p=d_{1}+1,m_{i}>0, i=1,2, \ldots,n.\end{array}$$i=1,2,$and which satisfy the DioIf we have positive integers
phantine equation (8), candidates for the number of edges and degree sequences
could be found.
with a given degree set, we introduce indefinite equations and we$i=1,2,$In order to find, respectively.
$m_{i},i=1,2,$$i=1,2,$in the equation (8) byreplaoe$\ldots,n$$m_{i},$$q$$\mathcal{D}$$m_{i},$$\ldots,$$n$$\ldots,n$$\ldots,n$$x_{i},$(9)$\{\begin{array}{l}d_{1}x_{1}+d_{2}x_{2}+\cdots+d_{n}x_{n}=2q,x_{1}+x_{2}+\cdots+x_{n}=p=d_{1}+1.\end{array}$

Substituting from$x_{n}=d_{1}+1-x_{1}-x_{2}-\cdots-x_{n-1}$

to the first equation in (13), we obtain the following equation:$(d_{1}-d_{n})x_{1}+(d_{2}-d_{n})\mathfrak{X}_{2}+\cdots+(d_{n-1}-d_{n})x_{n-1}$$=$$2q-d_{n}(d_{1}+1)$

.

(10)

Let $g=gcd((d_{1}-d_{n}), (d_{2}-d_{n}), \cdots, (d_{n-1}-d_{n}))$ . By the chinese remainder$n-1$ , which satisfy equation (10)$i=1,2,$
theorem, there exist integers
if and only if $g|2q-d_{n}(d_{1}+1)$ .
satisfy
Therefore, candidates for the number of edges with the degree set
the condition $2q-d_{n}(d_{1}+1)=kg$ for some integer and are obtained as follows;$x_{i},$$\ldots,$$\mathcal{D}$$k$$q= \frac{kg+d_{n}(d_{1}+1)}{2}$

.

(11)

Let $g*a_{i}=d_{i}-d_{n},i=1,2,$ $\ldots,n-1$ , and we use $kg=2q-d_{n}(d_{1}+1)$ ,then the equation (10) is expressed by.

$g*a_{1}x_{1}+g*a_{2}x_{2}+\cdots+g*a_{n-1}x_{n-1}=kg$

Hence, if we find integer solutions$x_{i},$$i=1,2,$$\ldots,$$n-1$ of$a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n-1}x_{n-1}=k$

,

(12)

then we secure candidates for a multiple number of each degree. Since $m_{i}>0$ ,$i=1,2,$ $\ldots,n$ , only positive solutions are the candidates for degree sequence.
Equivalently,$\{\begin{array}{l}a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n-1}x_{n-1}=k,x_{j}>0,i=1,2, \ldots,n-1.\end{array}$(13)

This is an integer knapsack problem which is known NP-complete. However,this problem is solvable in pseudo-polynomial time by dynamic programming([2],[6]).

155
4Bounds for$k$First, we evaluate a lower bound for$k$.

Lemma 4.1$\frac{1}{g}\sum_{i=1}^{n-1}(d_{i}-d_{n})\leq k$.

We show the next lemma.

Lemma 4.2 The number of vertices with the maximum degree
or equal to the minimum degree , that is.
$d_{n}$$d_{1}$is less than$m_{1}\leq d_{n}$Next, we wonder how large the parameter$k$is, and try to evaluate it.

Lemma 4.3
$k \leq\frac{1}{g}\{\sum_{i=1}^{n}d_{i}+(d_{2}-1)d_{1}-\{d_{n}+(n-2)\}d_{2}-d_{n}\}$.

From Lemma 4.1 and Lemma 4.3, we obtain the bounds for ;$k$

Theorem 4.1$\frac{1}{g}\sum_{i=1}^{n-1}(d_{i}-d_{n})\leq k\leq\frac{1}{g}\{\sum_{i=1}^{n}d_{i}+(d_{2}-1)d_{1}-\{d_{n}+(n-2)\}d_{2}-d_{n}\}$

4.1.

ExampleWe consider degree sequences for a degree set $D=\{8,6,4,2\}$ .
We substitute the degree set $D=\{8,6,4,2\}$ and $gcd(8-2,6-2,4-2)=2$
to the equation (13), then we have the equation$6x_{1}+4x_{2}+2x_{3}=2k$ ,

where

$k$

is a parameter. This equation is reduced to$3x_{1}+2x_{2}+x_{3}=k$

.

(14)

We solve the equation (14).
We substitute a degree set $\prime D=\{8,6,4,2\}$ and $gcd(8-2,6-2,4-2)=2$
to Theorem 4.1, then$k \leq\frac{1}{2}\{8+6+4+2+(6-1)*8-(2+4-2)*6-2\}=17$ ,and$\frac{1}{2}\{(8-2)+(6-2)+(4-2)\}=6\leq k$ .

Therefore, it is enough to solve the equation (14) for $6\leq k\leq 17$ .
If $k=6$ , then we obtain a unique positive solution $x_{1}=1,$ $x_{2}=1,$ $x_{3}=1$ ,and $x_{4}=6$ . Next we check whether the obtained candidate 8, 6, 4, 2, 2, 2, 2, 2, 2
is graphical, and it is true.
If $k=17$ , we obtain a positive solution $x_{1}=2,$ $x_{2}=5,$ $x_{3}=1,$ $x_{4}=1$ , thenwe have the candidate 8, 8, 6, 6, 6, 6, 6, 4, 2, and it is graphical.
Our bounds are sharp.

156

Enumeration of candidates for degree sequence

5

To solve all solutions for the equation (13), we introduce a candidate tree.
Each vertex in the candidate tree is an n-tuple, and each n-tuple corresponds
to a solution for the equation (13). If is the lower bound for Theorem
4.1, then the equation (13) has a solution $(1,1, \ldots, 1, d_{1}-n+2)$ . We set
a root to $(1, 1, \ldots, 1, d_{1}-n+2)$ , and the root has $n-1$ children whose$(1,$$1,2,$ $d_{1}-$tuple are $(2, 1, \ldots, 1, d_{1}-n+1),$ $(1,2,1, \ldots, 1, d_{1}-n+1),$$(1,1,\ldots,1,\alpha,\beta_{1},\ldots,\beta_{m},d_{1}-n+2-k)$
has $n-m-$$n+1)$ . The vertex
children whose n-tuple are $(2,1, \ldots, 1, \alpha, \beta_{1}, \ldots, \beta_{m}, d_{1}-n+2-k-1)$ ,$k$$narrow$$\ldots,$$\ldots,$$1$$(1, 2, \ldots, 1, \alpha,\beta_{1}, \ldots, \beta_{m}, d_{1}-n+2-k-1),$ $\ldots(1,1,$ $\ldots,$ $1,$ $\alpha+1,$$\beta_{m},$$\beta_{1},$$\ldots,$$d_{1}-$

is an integer, $1\leq i\leq m<n$ , and$n+2-k-1)$ , whereis an integer,$k<d_{1}-n+2$ is some positive integer. Moreover, the vertices
is an integer, $2\leq i<n$ .
is an integer andhave no child, whereis an integer
have no child, where
And the vertices$x_{1}>d_{n}$,for the equation
4.2,
issolution
if
there
no
,
$i<n$ because by Lemma$(1,
1,\ldots,1,\alpha,\beta_{1},\ldots,\beta_{m},d_{1}-n+2-k)$(13). In other words, the parent of vertex$\alpha>1$
is an integer,is $(1, 1, \ldots, 1, \alpha-1, \beta_{1}, \ldots, \beta_{m}, d_{1}-n+2-k+1)$ , whereis an integer, $1\leq i\leq m<n$ , and $k<d_{1}-n+2$ is some positive
integer. So, we may uniquely determine the parent. We obtain the candidate
tree, whose height is $d_{1}-n+1$ . The solution $(d_{n}, d_{1}-(n-2), 1, \ldots, 1)$ for theequation (14), which satisfy the upper bound of Theorem 4.3, appears at depth$d_{1}-n+1$ in the candidate tree.
Let $NV_{i}(k)$ denotes the number of vertices whose coordinate in the n-tuple
precisely increases by one at depth in the tree, where $1\leq i\leq n-1$ and$\alpha>1$$\beta_{i}>0$$(\delta_{1}, \ldots, \delta_{n-1},1)$$\delta_{i}>0$$\delta_{i}\leq d_{n}$$1\leq$$\gamma_{i}>0$$(d_{n}, \gamma_{1}, \ldots, \gamma_{n-1})$$\beta_{i}>0$

$i$

$k$

$0\leq k\leq d_{1}-n+1$.

Then we obtain next reccurence,

Notioe that

$NV_{0}(0)$

$=$

1,

$NV_{1}(1)$$=$$NV_{2}(1)=\cdots=NV_{n-1}(1)=1$ ,$NV_{1}(k)$$=$$\sum_{j=1}^{n-1}NV_{j}(k-1)-NV_{1}(k-d_{n}+1)$$NV_{i}(k)$$=$$\sum_{j=i}^{n-1}NV_{j}(k-1)$$\sum_{i=1}^{n-1}NV_{i}(k)$, where$i,$,$k>1$ .

denotes the number of vertices at depth

tree. Therefore, the total number of vertices in the tree is

(15)

$k$

in the$\sum_{k=0}^{d_{1}-n+1}\sum_{i=1}^{n-1}NV_{i}(k)$Rising factorial powers are defined by the rule$n$factors,$x^{\overline{n}}=\overline{x(x+1)\cdots(x+n-1)}$

where

$x$

and

$n$

are nonnegative integers.

$NV_{n-1}(k)=1,$ $NV_{n-2}(k)=k,$ $NV_{n-3}(k)=\underline{k(k}+1)/2,$ $NV_{n-4}(k)=k(k+$$1)(k+2)/6$ , and so on. We have $NV_{n-j}(k)= \frac{k^{j-1}}{(j-1)!}$ .

Lemma 5.1 Let$x$be a positive integer and $m$ a nonnegative integer. Then,$\sum_{i=0}^{m}\frac{(x-1)^{\overline{i}}}{i!}=\frac{x^{\overline{m}}}{m!}$

.

.

157
Lemma 5.2 Let

$m$

and

$n$

be nonnegative integers. Then,$\sum_{k=0}^{n}k^{\overline{m}}=\frac{n^{\overline{m+1}}}{m+1}$.

Theorem 5.1 The candidate tree has$\frac{(d_{1}-n+2)^{\overline{n-1}}}{(n-1)!}-\frac{(d_{1}-n+1-d_{n}+1)^{\overline{n-1}}}{(n-1)!}$(17)

vertices. That is, the number of candidates for degree sequence is given by theformula in equation (17).
5.1

ExampleWe consider degree sequences for a degree set $\mathcal{D}=\{8,6,4,2\}$ . Then $n=4$ ,$d_{1}-n+1=5$ . We construct the candidate tree for $D=\{8,6,4,2\}$ , and show

it in Figure 1.

Figure 1: Candidate tree for $D=\{8,6,4,2\}$ .
The total number of vertices in the candidate tree is$(d_{1}-n+2)^{\overline{n-1}}$$(d_{1}-n+1-d_{n}+1)^{\overline{n-1}}$$\overline{(n-1)!}\overline{(n-1)!}-$$=$$\frac{6^{\overline{3}}}{3!}-\frac{4^{\overline{3}}}{3!}=\frac{6\cdot 7\cdot 8}{3!}-\frac{4\cdot 5\cdot 6}{3!}=56-20=36$

We exhibit all solutions of the equation (14) in Tabel 1, and check whether
the candidates are graphical.
A symbol in Table 1 denotes the number of edges and is given in theequation (11).
$q$

158
Table 1: Candidates for degree sequences with $D=\{8,6,4,2\}$

6

Conclusion

We propose a basic problem of degree sets. We determine the number of candidates for degree sequences with the least order for a given degree set.

References[1] P. Erd\"os and T. Gallai, Graphs with prescribed degrees of the vertices, Mat.
Lapok, 11 (1960) 264-274.
[2] M.R. Garey and D.S. Johnson, Computers and Intmctability: A Guide to the
Theory of NP-completeness, W.H. Freeman and Company, New York, (1979).
[3] S.L. Hakimi, On the realizability of integers as degrees of the vertices of a graph,
J. SIAM Applied Mathematics, 10 (1962) 496-506.
[4] V. Havel, A remark on the existence of finite graphs, \v{C}asopis P\v{e}st. Mat., 80(1955) 477-480.

[5] D.S. Hirschberg and C.K. Wong, A polynomial-time algorithm for the knapsackproblems with two variables, J. ACM, 23 (1976) 147-154.
[6] R. Kannan, Polynomial-time aggregation of integer programming problems, J.
ACM, 30 (1983) 133-145.
[7] S.F. Kapoor, A.D. Polimeni, and C.E. Wall, Degree sets for graphs, Fundamenta
Mathematicae, 95 (1977) 189-194.
[8] A. Tripathi and S. Vijay, A note on a theorem of Erd\"os and Gallai, Discrete
Mathematics, 65 (2003) 417-420.
[9] A. Ttipathi and S. Vijay, On the least size of a graph with a given degree set,
Discrete Applied Mathematics, 154 (2006) 2530-2536.
[10] A. Tkipathi and S. Vijay, A short proof of a theorem on degree sets of graphs,
Discrete Applied Mathematics, 155 (2007) 670-671.