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. 65 - 74. ISSN 0166-218X

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

Abstract

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 > Mathematical Sciences, Department of
Depositing User: Elements
Date Deposited: 07 Apr 2020 12:39
Last Modified: 21 Apr 2020 12:15
URI: http://repository.essex.ac.uk/id/eprint/27277

Actions (login required)

View Item View Item