Asymptotic Analysis of Generating Functions Arising from Dynamic Graphs

Abstract

We study generating functions arising from sequentially growing labeled graphs where at each step either a new vertex is created or a new edge between two existing vertices is added. We provide explicit representations of the generating functions and derive asymptotic formulas for their coefficients using Laplace's method and Bessel function approximations in the undirected model, and Hayman admissibility combined with the saddle point method in the directed model. Finally, we study a natural parameter of each model and indicate further parameter studies.