2009/06/01 by M. Drew LaMar, LaMar, M. Drew · 1 citation
Computer Science · #05C07 #05C20 #05C75 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.0906.0343
openalex publication_date 2009/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Havel-Hakimi algorithm for constructing realizations of degree sequences for undirected graphs has been used extensively in the literature. A result by Kleitman and Wang extends the Havel-Hakimi algorithm to degree sequences for directed graphs. In this paper we go a step further and describe a modification of Kleitman and Wang's algorithm that is a more natural extension of Havel-Hakimi's algorithm, in the sense that our extension can be made equivalent to Havel-Hakimi's algorithm when the degree sequence has equal in and out degrees and an even degree sum. We identify special degree sequences, called directed 3-cycle anchored, that are ill-defined for the algorithm and force a particular local structure on all directed graph realizations. We give structural characterizations of these realizations, as well as characterizations of the ill-defined degree sequences, leading to a well-defined algorithm.