Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A simple Havel–Hakimi type algorithm to realize graphical degree sequences of directed graphs. | A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs Peter L. Erdos and Istvan Miklós A. Renyi Institute of Mathematics Hungarian Academy of Sciences Budapest PO Box 127 H-1364 Hungary elp miklosi @ Zoltan Toroczkai Interdisciplinary Center for Network Science and Applications and Department of Physics University of Notre Dame Notre Dame IN 46556 USA toro@ Submitted May 29 2009 Accepted Apr 21 2010 Published Apr 30 2010 Mathematics Subject Classification 05C07 05C20 90B10 90C35 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. Keywords. network modeling directed graphs degree sequences greedy algorithm 1 Introduction The systematic study of graphs or more precisely the linear graphs as it was called in that time began sometimes in the late forties through seminal works by P. Erdos P. Turan . Tutte and others. One problem which received considerable attention was PLE was partly supported by OTKA Hungarian NSF under contract Nos. AT048826 and K 68262. IM was supported by a Bolyai postdoctoral stipend and OTKA Hungarian NSF grant F61730. ZT was supported in part by the NSF BCS-0826958 HDTRA 201473-35045 and by Hungarian Bioinformatics MTKD-CT-2006-042794 Marie Curie Host Fellowships for Transfer of Knowledge. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R66 1 the existence of certain subgraphs of a given graph. For example such a subgraph could be a perfect matching in a not necessarily bipartite graph or a Hamiltonian cycle etc. Generally these substructures are called factors. The first couple of important results of .
