For a simple (unbiased) random walk on a connected graph with @math vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most @math . We consider locally biased random walks, in which the probability of traversing an edge depends on the degrees of its endpoints. We confirm a conjecture of Abdullah, Cooper and Draief [2015] that the min-degree local bias rule ensures a cover time of @math . For this we formulate and prove the following lemma about spanning trees. Let @math denote for edge @math the minimum degree among its two endpoints. We say that a weight function @math for the edges is feasible if it is nonnegative, dominated by @math (for every edge @math ) and the sum over all edges of the ratios @math equals @math . For example, in trees @math , and in regular graphs the sum of edge weights is @math . Lemma: for every feasible @math , the minimum weight spanning tree has total weight @math . For regular graphs, a similar lemma was proved by Kahn, Linial, Nisan and Saks [1989].
For simple random walks, the range of possible values of the cover time is well understood. Aleliunas al @cite_0 showed that for any connected graph, @math . That work also introduced the spanning tree argument that is used also in establishing other upper bounds cited below, and in fact provides upper bounds on @math and not just on @math . For regular graphs the upper bound can be improved to @math , as shown by Kahn al in @cite_10 . A more refined connection between regularity and cyclic cover time was provided by Coppersmith al @cite_8 who proved that for any connected graph @math ,
@cite_0 @cite_10 @cite_8
2156184725 2084768526 2091147489
For an undirected graph and an optimal cyclic list of all its vertices, the cyclic cover time is the expected time it takes a simple random walk to travel from vertex to vertex along the list until it completes a full cycle. The main result of this paper is a characterization of the cyclic cover time in terms of simple and easy-to-compute graph properties. Namely, for any connected graph, the cyclic cover time is @math , where @math is the number of vertices in the graph, @math is the average degree of its vertices, and @math is the average of the inverse of the degree of its vertices. Other results obtained in the processes of proving the main theorem are a similar characterization of minimum resistance spanning trees of graphs, improved bounds on the cover time of graphs, and a simplified proof that the maximum commute time in any connected graph is at most @math . This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight. For the set of graphs with a given degree sequence, consisting of any number of @math and @math , and its subset of bipartite graphs, we characterize the optimal graphs who maximize and minimize the number of @math -matchings. We find the expected value of the number of @math -matchings of @math -regular bipartite graphs on @math vertices with respect to the two standard measures. We state and discuss the conjectured upper and lower bounds for @math -matchings in @math -regular bipartite graphs on @math vertices, and their asymptotic versions for infinite @math -regular bipartite graphs. We prove these conjectures for @math -regular bipartite graphs and for @math -matchings with @math .