Random Walks on Quasirandom Graphs
Random Walks on Quasirandom Graphs
复制标题
拟随机图上的随机游走
DOI：
--
复制
发表时间：
2012
影响因子：
0.7
通讯作者：
E. Long
中科院分区：
文献类型：
--
作者：
Ben Barber;E. Long
令 $G$ 为 $n$ 个顶点上的拟随机图，并令 $W$ 为长度为 $alpha n^2$ 的 $G$ 上的随机游走。 $W$ 遍历的边集必须形成拟随机图吗？这个问题是由 Bottcher、Hladký、Piguet 和 Taraz 提出的。我们本文的目的是对这个问题给出积极的答案。我们还证明了树的随机嵌入的类似结果。
Let $G$ be a quasirandom graph on $n$ vertices, and let $W$ be a random walk on $G$ of length $alpha n^2$. Must the set of edges traversed by $W$ form a quasirandom graph? This question was asked by Bottcher, Hladký, Piguet and Taraz. Our aim in this paper is to give a positive answer to this question. We also prove a similar result for random embeddings of trees.