Degree-preserving network growth

Real-world networks evolve over time via additions or removals of vertices and edges. In network evolution models, vertex degree may vary arbitrarily as the network grows. However, in real-world networks where maintaining connections has some local non-negligible cost, vertex degrees are bounded by intrinsic properties of the underlying node (e.g., the number of friends in social networks, or the number of physical connections of nodes in infrastructure networks). The degrees of vertices can even be constants over time in some networks (e.g., the valency of an atom in a molecule). The recently introduced degree-preserving network growth (DPG) family of models preserves the vertex degree throughout the growth process. Following up on the lecture by Zoltán Toroczkai on DPG models from a physicist's point of view (held in the previous semester), in this talk we will explore the connections of DPG to matchings, Pósa's theorem, Kundu's theorem, scale free networks, and prime numbers.