Graphic Realizations of Joint-Degree Matrices
arXiv:1509.07076
Abstract
In this paper we introduce extensions and modifications of the classical degree sequence graphic realization problem studied by Erdős-Gallai and Havel-Hakimi, as well as of the corresponding connected graphic realization version. We define the joint-degree matrix graphic (resp. connected graphic) realization problem, where in addition to the degree sequence, the exact number of desired edges between vertices of different degree classes is also specified. We give necessary and sufficient conditions, and polynomial time decision and construction algorithms for the graphic and connected graphic realization problems. These problems arise naturally in the current topic of graph modeling for complex networks. From the technical point of view, the joint-degree matrix realization algorithm is straightforward. However, the connected joint-degree matrix realization algorithm involves a novel recursive search of suitable local graph modifications. Also, we outline directions for further work of both theoretical and practical interest. In particular, we give a Markov chain which converges to the uniform distribution over all realizations. We show that the underline state space is connected, and we leave the question of the mixing rate open.
arXiv commentUnpublished manuscript of 2009
References in corpus (3)
Cited by in corpus (5)
- On Realizations of a Joint Degree Matrix
- Neighborhood degree lists of graphs
- An algebraic Monte-Carlo algorithm for the Partition Adjacency Matrix realization problem
- Mathematical Models for Predicting and Mitigating the Spread of Chlamydia Sexually Transmitted Infection
- Construction of Directed 2K Graphs