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.

Item Type: | Article |
---|---|

Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány Q Science / természettudomány > QA Mathematics / matematika > QA76 Computer software / programozás Q Science / természettudomány > QH Natural history / természetrajz > QH301 Biology / biológia > QH3011 Biochemistry / biokémia |

SWORD Depositor: | MTMT SWORD |

Depositing User: | MTMT SWORD |

Date Deposited: | 06 Feb 2014 09:09 |

Last Modified: | 06 Feb 2014 09:09 |

URI: | http://real.mtak.hu/id/eprint/9913 |

### Actions (login required)

Edit Item |