City Research Online

Abstract

Given a sequence of n nonnegative integers how can we find the graphs which achieve the minimal deviation from that sequence? This extends the classical problem regarding what sequences are "graphic", that is, can be the degrees of a simple graph, to issues regarding arbitrary sequences. In this context, we investigate properties of the "minimal graphs". We shall demonstrate how a variation on the Havel-Hakimi algorithm can supply the value of the minimal possible deviation, and how consideration of the Ruch-Gutman condition and the Ferrer diagram can yield the complete set of graphs achieving this minimum. An application of this analysis is to a population of individuals represented by vertices, interactions between pairs by edges and in which each individual has a preferred range for their number of links to other individuals. Individuals adjust their links according to their preferred range and the graph evolves towards some set of graphs which achieve the minimal possible deviation. This Markov chain is defined but detailed analysis is omitted.

Publication Type:	Article
Additional Information:	NOTICE: this is the author’s version of a work that was accepted for publication in Discrete Mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Mathematics, #338 #5 (2015) 10.1016/j.disc.2014.12.011
Publisher Keywords:	degree-preferences, graphic sequences, Havel-Hakimi, Ruch-Gutman, Ferrer diagram.
Subjects:	H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management
Departments:	School of Science & Technology
SWORD Depositor:	Symplectic Administrator

Export

Downloads