The cover time of the preferential attachment graph (Q864904): Difference between revisions

From the authors' introduction: ``Let \(G=(V,E)\) be a connected graph. A random walk \(\mathcal{W}_u\), \(u\in V\) on the undirected graph \(G=(V,E)\) is a Markov chain \(X_0=u, X_1,...,X_t,...\in V\) associated to a particle that moves from vertex to vertex according to the following rule: the probability of a transition from vertex \(i\), of degree \(d(i)\), to vertex \(j\) is \(1/d(i)\) if \(\{i,j\}\in E\), and \(0\) otherwise. For \(u\in V\) let \(C_u\) be the expected time taken for \(\mathcal{W}_u\) to visit every vertex of \(G\). The cover time \(C_G\) of \(G\) is defined as \(C_G=\max_{u\in V}{C_u}\).'' The authors consider preferential attachment graphs, that is random graphs \(G_m(n)\) formed by adding a new vertex at each time step, with \(m\) edges which point to vertices selected at random with probability proportional to their degree. Thus at time \(n\) the graph contains \(n\) vertices and \(mn\) edges. The authors show that if \(m\geq 2\) then with probability tending to \(1\) as \(n\to\infty\) the cover time of a simple random walk on \(G_m(n)\) is asymptotic to \(\frac{2m}{m-1}n\log{n}\).