How Many Vertices Does a Random Walk Miss in a Network with a Moderately Increasing Number of Vertices?

Real networks are often dynamic. In response to it, analyses of algorithms on dynamic networks attract more and more attention in network science and engineering. Random walks on dynamic graphs have also been actively investigated for over a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by the setting of random walks on growing networks, this paper introduces a simple model of graphs with an increasing number of vertices and presents an analysis of random walks associated with the cover time on such graphs. In particular, we reveal that a random walk asymptotically covers all but [Formula: see text] vertices if the vertex set grows moderately. Moreover, we apply our model to the growing preferential attachment model that is a prominent random graph model for real networks. Funding: This work is partly supported by the Japan Society for the Promotion of Science KAKENHI [Grants JP17K19982, JP19J12876, JP19K20214, JP21H03396, and JP23K21645].