Graphic Sequence

A graphic sequence is a sequence of numbers which can be the degree sequence of some graph. A sequence can be checked to determine if it is graphic using GraphicQ[g] in the Wolfram Language package Combinatorica` .

Erdős and Gallai (1960) proved that a degree sequence  is graphic iff the sum of vertex degrees is even and the sequence obeys the property

for each integer  (Skiena 1990, p. 157), and this condition also generalizes to directed graphs. Tripathi and Vijay (2003) showed that this inequality need be checked only for as many  as there are distinct terms in the sequence, not for all .

Havel (1955) and Hakimi (1962) proved another characterization of graphic sequences, namely that a degree sequence with  and  is graphical iff the sequence  is graphical. In addition, Havel (1955) and Hakimi (1962) showed that if a degree sequence is graphic, then there exists a graph  such that the node of highest degree is adjacent to the  next highest degree vertices of , where  is the maximum vertex degree of .

No degree sequence can be graphic if all the degrees occur with multiplicity 1 (Behzad and Chartrand 1967, p. 158; Skiena 1990, p. 158). Any degree sequence whose sum is even can be realized by a multigraph having loops (Hakimi 1962; Skiena 1990, p. 158).

REFERENCES

Behzad, M. and Chartrand, G. "No Graph is Perfect." Amer. Math. Monthly 74, 962-963, 1967.

Eggleton, R. B. "Graphic Sequences and Graphic Polynomials." In Infinite and Finite Sets (Ed. A. Hajnal). Amsterdam, Netherlands: North-Holland, pp. 385-293, 1975.

Erdős, P. and Gallai, T. "Graphs with Prescribed Degrees of Vertices" [Hungarian]. Mat. Lapok. 11, 264-274, 1960.

Fulkerson, D. R. "Upsets in Round Robin Tournaments." Canad. J. Math. 17, 957-969, 1965.

Fulkerson, D. R.; Hoffman, A. J.; and McAndrew, M. H. "Some Properties of Graphs with Multiple Edges." Canad. J. Math. 17, 166-177, 1965.

Hakimi, S. "On the Realizability of a Set of Integers as Degrees of the Vertices of a Graph." SIAM J. Appl. Math. 10, 496-506, 1962.

Havel, V. "A Remark on the Existence of Finite Graphs" [Czech]. Časopis Pest. Mat. 80, 477-480, 1955.

Ryser, H. J. "Combinatorial Properties of Matrices of Zeros and Ones." Canad. J. Math. 9, 371-377, 1957.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 157, 1990.

Tripathi, A. and Vijay, S. "A Note on a Theorem of Erdős & Gallai." Discr. Math. 265, 417-420, 2003.