A remark on degree sequences of multigraphs

摘要

A sequence {d 1, d 2, . . . , d n } of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v 1, v 2, . . . , v n such that the degree d(v i ) of the vertex v i equals d i for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize sequences that are multigraphic in a similar way, Havel (?asopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler, Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow.