Research Repository

Connected realizations of joint-degree matrices

Amanatidis, Georgios and Green, Bradley and Mihail, Milena (2018) 'Connected realizations of joint-degree matrices.' Discrete Applied Mathematics, 250. pp. 65-74. ISSN 0166-218X

Full text not available from this repository. (Request a copy)


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 di and vertices of degree dj. 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.

Item Type: Article
Uncontrolled Keywords: Joint-degree matrix; Graphic realizations
Divisions: Faculty of Science and Health
Faculty of Science and Health > Mathematical Sciences, Department of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 07 Apr 2020 12:39
Last Modified: 06 Jan 2022 14:12

Actions (login required)

View Item View Item