pith. sign in

arxiv: 1406.1142 · v1 · pith:AIMYIJHFnew · submitted 2014-06-04 · 🧮 math.CO · math.PR

Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

classification 🧮 math.CO math.PR
keywords covertimedegreerandomasymptoticgraphmathbfsequence
0
0 comments X
read the original abstract

We study the cover time of a random graph chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $\mathbf{d}=(d_i)_{i=1}^n$. In a previous work, the asymptotic cover time was obtained under a number of assumptions on $\mathbf{d}$, the most significant being that $d_i\geq 3$ for all $i$. Here we replace this assumption by $d_i\geq 2$. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of $\mathcal{G}(n,p)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.