Cover time of graphs with bounded genus

MaRDI QIDQ6398526zbMATH OpenFDO

Authors Naoki Matsumoto, Yuuki Takai

Publication date 7 May 2022

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Abstract: The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all vertices of the graph. It is known that the cover time of any finite connected $n$-vertex graph is at least $(1+o(1))nlogn$ and at most $(1+o(1))frac427n^3$. By Jonasson and Schramm, the cover time of any bounded-degree finite connected $n$-vertex planar graph is at least $cn(logn{)}^2$ and at most $6n^2$, where $c$ is a positive constant depending only on the maximal degree of the graph. In particular, the lower bound is established via the use of circle packing of planar graphs on the Riemann sphere. In this paper, we show that the cover time of any finite $n$-vertex graph $G$ with maximum degree $Delta$ on the compact Riemann surface $S$ of given genus $g$ is at least $cn(logn{)}^2/Delta(g+1)$ and at most $(6+o(1))n^2$, where $c$ is an absolute constant, if $n$ is sufficiently large and three sufficient conditions for $S$ and a circle packing of $G$ filling $S$.

This page was built for publication: Cover time of graphs with bounded genus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398526)