Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2011-06-21
Phys. Rev. E 84, 022103 (2011)
Physics
Condensed Matter
Statistical Mechanics
Typeset in RevTEX 4.1, 4 pages, 3 figures
Scientific paper
10.1103/PhysRevE.84.022103
We investigate a conjecture on the cover times of planar graphs by means of large Monte Carlo simulations. The conjecture states that the cover time $\tau(G_{N})$ of a planar graph $G_{N}$ of $N$ vertices and maximal degree $d$ is lower bounded by $\tau(G_{N}) \geq C_{d} N(\ln N)^2$ with $C_{d} = (d/4\pi) \tan (\pi/d)$, with equality holding for some geometries. We tested this conjecture on the regular honeycomb ($d=3$), regular square ($d=4$), regular elongated triangular ($d=5$), and regular triangular ($d=6$) lattices, as well as on the nonregular Union Jack lattice ($d_{\rm min}=4$, $d_{\rm max}=8$). Indeed, the Monte Carlo data suggest that the rigorous lower bound may hold as an equality for most of these lattices, with an interesting issue in the case of the Union Jack lattice. The data for the honeycomb lattice, however, violates the bound with the conjectured constant. The empirical probability distribution function of the cover time for the square lattice is also briefly presented, since very little is known about cover time probability distribution functions in general.
No associations
LandOfFree
Numerical evidence against a conjecture on the cover time of planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Numerical evidence against a conjecture on the cover time of planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Numerical evidence against a conjecture on the cover time of planar graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-178977