The Cover Time of Cartesian Product Graphs

DOI10.1007/978-3-642-19222-7_37MaRDI QIDQ3000524zbMATH OpenOpenAlexFDO

Authors Colin Cooper, Tomasz Radzik, Mohammed Abdullah

Publication date 19 May 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-19222-7_37

zbMATH Keywords

blanket timeCartesian product graphscover timeeffective resistancerandom walks

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Random walks on graphs (05C81)

Recommendations

• On the well-coveredness of Cartesian products of graphs
• On the cover time of planar graphs
• On the Cartesian product of non well-covered graphs
• On the cover time of dense graphs
• scientific article; zbMATH DE number 68351
• scientific article; zbMATH DE number 3995739
• The Cover Time of Random Digraphs
• The Cover Time of Random Regular Graphs
• On biclique covering number of the Cartesian product of graphs
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs

Cites work

• A tight lower bound on the cover time for random walks on graphs
• A tight upper bound on the cover time for random walks on graphs
• An upper bound on the cover time for powers of graphs
• Cover times for Brownian motion and random walks in two dimensions
• Cover times, blanket times, and majorizing measures
• Covering problems for Brownian motion on spheres
• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Multiple cover time
• Random walks and electrical resistances in products of graphs
• The electrical resistance of a graph captures its commute and cover times

Cited in

(1)

• An upper bound on the cover time for powers of graphs

This page was built for publication: The Cover Time of Cartesian Product Graphs

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