Connected realizations of joint-degree matrices

We study a restriction of the classic degree sequence graphic realization problem studied by Erdős, Gallai, Havel, and Hakimi, namely the joint-degree matrix graphic realization problem. Here, in addition to the degree sequence, a joint degree matrix is given, the (i,j)th element of which specifies the exact number of edges between vertices of degree d_i and vertices of degree d_j. The decision and construction versions of the problem have a relatively straightforward solution. In this work, however, we focus on the corresponding connected graphic realization version of the problem. We give a necessary and sufficient condition for a connected graphic realization to exist, as well as a polynomial time construction algorithm that involves a novel recursive search of suitable local graph modifications. As a byproduct, we also suggest an alternative polynomial time algorithm for the joint-degree matrix graphic realization problem that never increases the number of connected components of the graph constructed.