Degree-based graph construction

Kim, Hyunju and Toroczkai, Zoltán and Erdős, Péter and Miklós, István and Székely, László A. (2009) Degree-based graph construction. JOURNAL OF PHYSICS A: MATHEMATICAL AND THEORETICAL, 42 (39). pp. 1-10. ISSN 1751-8113

Text KTEMS-IOP09.pdf Restricted to Repository staff only Download (229kB) | Request a copy

Abstract

Degree-based graph construction is a ubiquitous problem in network modelling (Newman et al 2006 The Structure and Dynamics of Networks (Princeton Studies in Complexity) (Princeton, NJ: Princeton University Press), Boccaletti et al 2006 Phys. Rep. 424 175), ranging from social sciences to chemical compounds and biochemical reaction networks in the cell. This problem includes existence, enumeration, exhaustive construction and sampling questions with aspects that are still open today. Here we give necessary and sufficient conditions for a sequence of nonnegative integers to be realized as a simple graph’s degree sequence, such that a given (but otherwise arbitrary) set of connections from an arbitrarily given node is avoided. We then use this result to present a swap-free algorithm that builds all simple graphs realizing a given degree sequence. In a wider context, we show that our result provides a greedy construction method to build all the f -factor subgraphs (Tutte 1952 Can. J. Math. 4 314) embedded within Kn\Sk, where Kn is the complete graph and Sk is a star graph centred on one of the nodes.

Actions (login required)

Edit Item