A remark on degree sequences of multigraphs |
| |
Authors: | Dirk Meierling Lutz Volkmann |
| |
Institution: | (1) Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Multigraph Degree sequence |
本文献已被 SpringerLink 等数据库收录! |
|