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

MaRDI QIDQ976717zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/0905.4913, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r66.html

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

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)

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.

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

Cited in

(24)

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

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)