×

zbMATH — the first resource for mathematics

Seven criteria for integer sequences being graphic. (English) Zbl 0752.05052
A nonincreasing sequence of positive integers with even sum is called graphic when they represent the vertex-degrees of some simple graph. This paper lists seven criteria for such sequences to be graphic, and gives a relatively short proof of their equivalence. The criteria are those due to Ryser, Berge, Erdős-Gallai, Fulkerson-Hoffman-McAndrew, Bollobás, Grünbaum and a simple reformulation of the recent Hässelbarth criterion.

MSC:
05C99 Graph theory
11B83 Special sequences and polynomials
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Graphs and Hypergraphs. North Holland, Amsterdam, and American Elsevier, New York (1973).
[2] Extremal Graph Theory. Academic Press, New York (1978).
[3] and , Graph Theory with Applications. American Elsevier, New York (1976). · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[4] Choudum, Bull. Austr. Math. Soc. 33 pp 67– (1986)
[5] Erdós, Mat. Lapok 11 pp 264– (1960)
[6] Fulkerson, Can. J. Math. 17 pp 166– (1965) · Zbl 0132.21002 · doi:10.4153/CJM-1965-016-2
[7] Graphs and complexes. Report of the University of Washington, Seattle, Math., 572B, 1969 (private communication).
[8] Hakimi, J. Soc. Indust. Appl. Math. 10 pp 496– (1962)
[9] Hakimi, J. Soc. Indust. Appl. Math. 11 pp 135– (1963)
[10] Graph Theory. Addison-Wesley, Reading, MA (1969).
[11] Hässelbarth, Match. 16 pp 3– (1984)
[12] Ryser, Can. J. Math. 9 pp 371– (1957) · Zbl 0079.01102 · doi:10.4153/CJM-1957-044-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.