Component structure of the vacant set induced by a random walk on a random graph

DOI10.1002/rsa.20402zbMath1259.05155arXiv1005.1564WikidataQ57401429 ScholiaQ57401429MaRDI QIDQ4909198

Colin Cooper, Alan M. Frieze

Publication date: 12 March 2013

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1005.1564

zbMATH Keywords

random walk; random graph; vacant set; cover time

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C81: Random walks on graphs

Related Items

Unnamed Item, Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk, Giant component for the supercritical level‐set percolation of the Gaussian free field on regular expander graphs, Level-set percolation of the Gaussian free field on regular graphs II: finite expanders, Phase transition for the vacant set left by random walk on the giant component of a random graph, On the fragmentation of a torus by random walk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stationary distribution and cover time of random walks on random digraphs
• Logarithmic components of the vacant set for random walk on a discrete torus
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Random minimum length spanning trees in regular graphs
• Giant vacant component left by a random walk in a random \(d\)-regular graph
• Giant component and vacant set for random walk on a discrete torus
• The transitive closure of a random digraph
• The cover time of the giant component of a random graph
• A proof of Alon’s second eigenvalue conjecture and related problems
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• A critical point for random graphs with a given degree sequence
• The Cover Time of Random Regular Graphs