Seven criteria for integer sequences being graphic
✍ Scribed by Gerard Sierksma; Han Hoogeveen
- Publisher
- John Wiley and Sons
- Year
- 1991
- Tongue
- English
- Weight
- 312 KB
- Volume
- 15
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Seven criteria for integer sequences being graphic are listed. Being graphic means that there is a simple graph with the given integer sequence as d e gree sequence. One of the criteria leads to a new and constructive proof of the well-known criterion of Erdos-Gallai.
1. Introduction
Let (dl, . . . , d.) be a nonincreasing sequence of positive integers with even sum. The sequence (dl,. . . , d.) is called graphic iff there is a simple graph (without loops and multiple edges) that has (dl,. . . d,) as degree sequence.
In this paper seven criteria for such an integer sequence being graphic are listed; one of these is well known and due to Erdos and Gallai [5]. Proofs of the Erdos-Gallai Criterion can be found in Berge [l] and in Harary [lo].
Harary's proof is rather lengthy and Berge's proof uses flows in networks. Recently, Choudum [4] has given a different proof which, in our opinion, is not very appealing either. Using the rqently discovered Hisselbarth Criterion we are able to give a new and elegant proof.
2. THE SEVEN CRITERIA
In Theorem 1 it will be shown that the following conditions (A)-(G) are all equivalent to "(dl, . . . d.) is graphic.