Meierling, Dirk; Volkmann, Lutz A remark on degree sequences of multigraphs. (English) Zbl 1221.05065 Math. Methods Oper. Res. 69, No. 2, 369-374 (2009). Summary: A sequence \(\{d_{1}, d_{2},\dots, d_{n}\}\) of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices \(v_{1}, v_{2},\dots, v_{n}\) such that the degree \(d(v_{i})\) of the vertex \(v_{i}\) equals \(d_{i}\) for each \(i=1,2,\dots,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,V. Havel [“Eine Bemerkung über die Existenz der endlichen Graphen,” Čas. Mat. 80, 477–480 (1955; Zbl 0068.37202)] and S. Hakimi [“On realizability of a set of integers as degrees of the vertices of a linear graph. I,” J. Soc. Ind. Appl. Math. 10, 496–506 (1962; Zbl 0109.16501)] characterized graphic sequences. Results of Hakimi [loc.cit] and F. Boesch and F. Harary [“Line removal algorithms for graphs and their degree lists,” IEEE Trans. Circuits Syst. 23, 778–782 (1976; Zbl 0354.05044)] follow. Cited in 1 Document MSC: 05C07 Vertex degrees Keywords:multigraph; degree sequence Citations:Zbl 0068.37202; Zbl 0109.16501; Zbl 0354.05044 PDFBibTeX XMLCite \textit{D. Meierling} and \textit{L. Volkmann}, Math. Methods Oper. Res. 69, No. 2, 369--374 (2009; Zbl 1221.05065) Full Text: DOI References: [1] Boesch F, Harary F (1976) Line removal algorithms for graphs and their degree lists. IEEE Trans Circuits Syst CAS-23(12):778–782. Special issue on large-scale networks and systems · Zbl 0354.05044 [2] Dankelmann P, Oellermann O (2005) Degree sequences of optimally edge-connected multigraphs. Ars Comb 77: 161–168 · Zbl 1164.05334 [3] Hakimi SL (1962) On realizability of a set of integers as degrees of the vertices of a linear graph I. J Soc Indust Appl Math 10: 496–506 · Zbl 0109.16501 [4] Havel V (1955) Eine Bemerkung über die Existenz der endlichen Graphen (Czech). Časopis Pěst Mat 80: 477–480 · Zbl 0068.37202 [5] Takahashi M, Imai K, Asano T (1994) Graphical degree sequence problems. IEICE Trans Fundam E77-A(3): 546–552 [6] Tyshkevich RI, Chernyak AA, Chernyak Zh A (1987) Graphs and degree sequences I. Kibernetika (Kiev) 6(12–19): 133 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.