Amanatidis, Georgios and Green, Bradley and Mihail, Milena (2018) Connected realizations of joint-degree matrices. Discrete Applied Mathematics, 250. pp. 65-74. DOI https://doi.org/10.1016/j.dam.2018.04.010
Amanatidis, Georgios and Green, Bradley and Mihail, Milena (2018) Connected realizations of joint-degree matrices. Discrete Applied Mathematics, 250. pp. 65-74. DOI https://doi.org/10.1016/j.dam.2018.04.010
Amanatidis, Georgios and Green, Bradley and Mihail, Milena (2018) Connected realizations of joint-degree matrices. Discrete Applied Mathematics, 250. pp. 65-74. DOI https://doi.org/10.1016/j.dam.2018.04.010
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 Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 07 Apr 2020 12:39 |
Last Modified: | 30 Oct 2024 16:16 |
URI: | http://repository.essex.ac.uk/id/eprint/27277 |