A remark on degree sequences of multigraphs

Dirk Meierling () and Lutz Volkmann ()

Mathematical Methods of Operations Research, 2009, vol. 69, issue 2, 369-374

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. Copyright Springer-Verlag 2009

Keywords: Multigraph; Degree sequence (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-008-0265-2 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:69:y:2009:i:2:p:369-374

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-008-0265-2

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().