A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs

zbMATH Open1215.05035arXiv0905.4913MaRDI QIDQ976717FDOQ976717

Authors: Péter L. Erdős, István Miklós, Z. Toroczkai 

Publication date: 16 June 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0905.4913

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Directed random graphs with given degree distributions
• scientific article; zbMATH DE number 970793
• Constructing and sampling directed graphs with given degree sequences
• A simple criterion on degree sequences of graphs
• Dag realizations of directed degree sequences

zbMATH Keywords

greedy algorithmdirected graphsnetwork modelingdegree sequences

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10) Vertex degrees (05C07)

Cited In (23)

• On degree sequences of undirected, directed, and bidirected graphs
• A Gale-Ryser type characterization of potentially \(K_{s,t}\)-bigraphic pairs
• Sufficient conditions for graphicality of bidegree sequences
• Rejection sampling of bipartite graphs with given degree sequence
• Methods for the graph realization problem
• Relaxed and approximate graph realizations
• A survey of discrete methods in (algebraic) statistics for networks
• New classes of degree sequences with fast mixing swap Markov chain sampling
• Mathematical tools for the future: graph theory and graphicable algebras
• Graphic deviation
• Graph realizations: maximum degree in vertex neighborhoods
• Exact sampling of graphs with prescribed degree correlations
• Directed random graphs with given degree distributions
• A constructive proof of the Fulkerson-Ryser characterization of digraphic sequences
• Asymptotics in directed exponential random graph models with an increasing bi-degree sequence
• Constructing and sampling directed graphs with given degree sequences
• Algebraic operations on graphs preserving the degree sequence
• Directed Networks with a Differentially Private Bi-degree Sequence
• A polynomial time algorithm to find the star chromatic index of trees
• Sampling contingency tables
• Uniform sampling of digraphs with a fixed degree sequence
• On the swap-distances of different realizations of a graphical degree sequence
• Split digraphs

This page was built for publication: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976717)