City Research Online

Abstract

This paper will consider a group of individuals who each have a target number of contacts they would like to have with other group members. We are interested in how close this can be to being realized. Considering the group’s long-term outcome under reasonable dynamics on the number of contacts. We formulate this as a graph realization problem for undirected graphs, with the individuals as vertices and the number of desired contacts as the vertex degree. It is well known that not all degree sequences can be realized as undirected graphs, and the Havel-Hakimi algorithm characterizes those that can. When we ask how close the degree sequences can be to realization, we ask for graphs that minimize the total deviation between what is desired and possible. The set of all such graphs and all such associated sequences are termed the minimal sets. Broom and Cannings have previously considered this problem in many papers, and it is hard to tackle for general target sequences. This paper revisited the minimal set in general, investigating two particular classes of sequence in particular. We considered the n-element arithmetic sequence (n-1, n-2, . . . 1,0) for general n, including obtaining a formula that generates the size of the minimal set for a given arithmetic sequence, and the all or nothing sequences, where targets are either 0 or n-1, where a recurrence relation for such a formula was found. Further, we consider the question of the size of the minimal set of sequences in general. We consider a strategic version of the model where the individuals are involved in a multiplayer game, each trying to achieve their target, and show that optimal play can lead to the minimal set being left, thus answering an open question from earlier work.

Publication Type:	Article
Additional Information:	This is a pre-copy-editing, author-produced PDF of an article accepted for publication in Discrete and Continuous Dynamical Systems - Series B following peer review. The definitive publisher-authenticated version Aizouk, R. & Broom, M. (2022). Modelling conflicting individual preference: Target sequences and graph realization. Discrete and Continuous Dynamical Systems - Series B is available online at: http://dx.doi.org/10.3934/dcdsb.2022001
Subjects:	Q Science > QA Mathematics
Departments:	School of Science & Technology > Mathematics
SWORD Depositor:	Symplectic Administrator

Export

Downloads