×

A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs. (English) Zbl 1215.05035

Summary: One of the simplest ways to decide whether a given finite sequence of positive integers can arise as the degree sequence of a simple graph is the greedy algorithm of Havel and Hakimi. This note extends their approach to directed graphs. It also studies cases of some simple forbidden edge-sets. Finally, it proves a result which is useful to design an MCMC algorithm to find random realizations of prescribed directed degree sequences.

MSC:

05C07 Vertex degrees
05C20 Directed graphs (digraphs), tournaments
90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: arXiv EMIS