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 . In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially, one vertex of a graph G=(V,E) owns a piece of information which is spread iteratively to all other vertices: in each timestep t=1,2,… every informed vertex chooses a neighbor uniformly at random and informs it. The question is how many time steps are required until all vertices become informed (with high probability). For various graph classes, involved methods have been developed in order to show an upper bound of @math on the runtime of the push-algorithm, where N is the number of vertices and @math denotes the diameter of G. However, no asymptotically tight bound on the runtime based on the mixing time of random walks has been established. In this work we fill this gap by deriving an upper bound of @math , where @math denotes the mixing time of a certain random walk on G. After that we prove upper bounds that are based on certain edge expansion properties of G. However, for hypercubes neither the bound based on the mixing time nor the bounds based on edge expansion properties are tight. That is why we develop a general way to combine these two approaches by which we can deduce that the runtime of the push-algorithm is Θ(log N) on every Hamming graph.