{'fraction_non_alphanumeric': 0.05218695117972497, 'fraction_numerical': 0.012168625354889316, 'mean_word_length': 3.7510058703251765, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Cover Time of Random Walks on Graphs

A simple random walk on a graph is a sequence of movements from one vertex to another where at each step an edge is chosen uniformly at random from the set of edges incident on the current vertex, and then transitioned to next vertex. Central to this thesis is the cover time of the walk, that is, the expectation of the number of steps required to visit every vertex, maximised over all starting vertices. In our first contribution, we establish a relation between the cover times of a pair of graphs, and the cover time of their Cartesian product. This extends previous work on special cases of the Cartesian product, in particular, the square of a graph. We show that when one of the factors is in some sense larger than the other, its cover time dominates, and can become within a logarithmic factor of the cover time of the product as a whole. Our main theorem effectively gives conditions for when this holds. The techniques and lemmas we introduce may be of independent interest. In our second contribution, we determine the precise asymptotic value of the cover time of a random graph with given degree sequence. This is a graph picked uniformly at random from all simple graphs with that degree sequence. We also show that with high probability, a structural property of the graph called conductance, is bounded below by a constant. This is of independent interest. Finally, we explore random walks with weighted random edge choices. We present a weighting scheme that has a smaller worst case cover time than a simple random walk. We give an upper bound for a random graph of given degree sequence weighted according to our scheme. We demonstrate that the speed-up (that is, the ratio of cover times) over a simple random walk can be unbounded

Our main theorem effectively gives conditions for when this holds. The techniques and lemmas we introduce may be of independent interest. In our second contribution, we determine the precise asymptotic value of the cover time of a random graph with given degree sequence. This is a graph picked uniformly at random from all simple graphs with that degree sequence. We also show that with high probability, a structural property of the graph called conductance, is bounded below by a constant. This is of independent interest. Finally, we explore random walks with weighted random edge choices. We present a weighting scheme that has a smaller worst case cover time than a simple random walk. We give an upper bound for a random graph of given degree sequence weighted according to our scheme. We demonstrate that the speed-up (that is, the ratio of cover times) over a simple random walk can be unbounded.

Acknowledgment
I firstly wish to express my deepest gratitude to my supervisor, Colin Cooper, whom I have been very fortunate to have known. It has been a pleasure to work with Colin, both as his student and as a research colleague. His guidance, patience and encouragement have been invaluable, and I am greatly indebted to him for the opportunities he has given me.
I also wish to thank my second supervisor, Tomasz Radzik. More than merely an excellent source of advice, Tomasz has been a colleague with whom I have greatly enjoyed working. Our research meetings have always been inspiring and productive, and a rich source of ideas.
I wish to thank Alan Frieze, a co-author of one of my papers that forms a significant part of this thesis. I am grateful to Alan for his role in directly developing the field to which I have dedicated so much time, and for the opportunity to collaborate with him.
In the final year of my time as a PhD student, I have been fortunate to have met and worked with Moez Draief. Though our work together does not form part of this thesis, it has nevertheless been both highly compelling and enjoyable part of my time as a PhD student. I would like to thank Moez for our research collaboration.
Finally, I would like to thank my parents for innumerable reasons, but in particular for their encouragement and support in all its forms. It is to them that this thesis is dedicated.     . . 69 Chapter 1

Introduction
Let G = (V, E) be a finite, connected, undirected graph. Suppose we start at time step t = 0 on some vertex u ∈ V and choose an edge e uniformly at random (uar) from those incident on u. We then transition e to the vertex that the other end of e is incident on. We repeat this process at the next step, and so on. This is known as a simple random walk (often abbreviated to random walk ) on G. We shall denote it by W u , where the subscript is the starting vertex. We write W u (t) = x if the walk is at vertex x at time step t.
Immediately, a number of questions can be asked about this process. For example, (1) Does W u visit every vertex in G?
(2) If so, how long does it take on average?
(3) On average, how long does it take to visit a particular vertex v?
(4) On average, how long does it take to come back to itself? This thesis addresses all of these questions in one way or another for specific classes of graphs. However, the particular question that is the central motivation for this work is the following: For a random walk W u on a simple, connected, undirected graph G = (V, E), what is the expected number of steps required to visit all the vertices in G, maximised over starting vertices u?
The following quantities, related to the questions above, are formally defined in chapter 2. The expected time it takes W u to visit every vertex of G is the cover time from u, COV u [G], and the cover time COV[G] = max u COV u [G]. The expected time it takes W u to visit some v is the hitting time H [u, v], and when v = u, it is called the first return time.
These questions, much like the process itself, are easy to understand, yet they and many others have been been the focus of a great deal of study in the mathematics and computer science communities. Some questions are easy to answer with basic probability theory, others are more involved and seem to require more sophisticated techniques. The difficulty usually varies according to what kind of answer we are looking for. For example, for the 2-dimensional torus Z 2 n with N = n 2 vertices, COV[Z 2 n ] = O(N log 2 N ) is not too difficult to show with some of the theory and techniques we present in chapters 4 and 5. However, it was not until quite recently that a precise asymptotic result of COV[Z 2 n ] ∼ N π log 2 N was given by [29].
This thesis is concerned primarily with cover time.

Applications
Before we give an outline of the thesis, we mention the applications of random walks and in particular, cover times. Applications are not the focus of this thesis, but it is worth mentioning their role, particularly in algorithmic and networking areas. The classical application of random walks in an algorithmic context is a randomised s − t connectivity algorithm. The problem, known as the s-t connectivity problem, is as follows: Given a graph G = (V, E), with |V | = n and |E| = m, and two vertices s, t ∈ V , if there is a path in G connecting s and t, return "true" otherwise, return "false". This can be done in time O(n + m) with, for example, breadth first search. However, the space requirement is Ω(n) for such an algorithm (or various others, such as depth first search). Take, for example, the case where G is a path of length n and s and t are ends of the path.
With a random-walk based algorithm, we can present a randomized algorithm for the problem that requires O(log n) space. It relies upon the following proposition, proved in chapter 5. See, e.g., [61]. To avoid confusion with the name of the problem, we shall use the variable τ to stand for time in the walk process.
The algorithm is as follows: Start a walk W s on G from vertex s. Assume time τ = 0 at the start of the walk. Stop the walk at time τ if (i)τ = 8nm or (ii) W s (τ ) = t. If W s (τ ) = t, then output "true". Otherwise output "false".
Observe, if the algorithm returns "true", then it is correct, since there must be a path. If it returns "false", then it may be wrong, since it may have simply not visited t even though it could have. The question is, what is the probability that the algorithm returns an incorrect answer given that an s − t path exists? Suppose the random variable X counts the number of steps the random walk 1.2 Overview of the Thesis from s takes before visiting t. By Markov's inequality, The size of the input, that is, the graph, is n vertices and m ≤ n 2 edges. This algorithm needs O(log n) space since it need only store enough bits to keep track of its position and maintain a counter τ .
In fact, a breakthrough 2004 paper [65] showed that the problem can be solved by a deterministic algorithm using O(log n) space. Nevertheless, the randomised algorithm demonstrated here, as well as being very simple, remains a strong example of the role that the theory of random walks plays in applications.

Overview of the Thesis
Roughly speaking, this thesis can be divided into two parts. Aside from this chapter, chapters 2, 3, 4 and 5 are drawn from the established literature. They provide a review of some results and vital theory required for the original contribution. The original contribution can be considered to be in chapters 6, 7 and 8.

Background
In chapter 2, we give definitions and basic lemmas for graphs, random walks and Markov chains. We also give definitions of weighted random walks. These differ from simple random walks in how the next edge to be transitioned is chosen. Rather than choosing edges uar the probabilities are weighted by a weight assigned to the edge. This is more general than simple random walks, which are weighted random walks in which all edge weights are the same. Weighted random walks are the subject of chapter 8. Simple random walks on graphs are special cases of weighted random walks, which are in turn, special cases of Markov chains. Markov chains play a part in a fundamental lemma of chapter 6, and we use theorems from the literature based on Markov chains in chapters 7 and 8. In chapter 3, we give an account of the theory of Markov chains and random walks relevant to our work. Much of the theory presented in the framework of Markov chains is vital to sections of the thesis where only simple random walks are considered, and would have had to be written in a similar form had the more general presentation not been given. This, in conjunction with our use of Markov chains in various parts is why we chose to give a presentation in terms of Markov chains supplemented with explanations of how the general theory specialises for random walks. We also demonstrate a characterisation of Markov chains that are equivalent to weighted random walks.
In chapter 4 we present the electrical network metaphor of random walks on graphs. This is a framework in which a theory has been built up to describe properties and behaviours of random walks in a different way. It provides a means of developing an intuition about random walks, and provides a tool kit of useful lemmas and theorems. Much of chapter 6 is built on the material in chapter 4. In chapter 7, the tools of electrical network theory are exploited in a number of proofs.

Overview of the Thesis
In chapter 5 we present detailed proofs of hitting and cover times for specific, simple graph structures. We then give general techniques for bounding these parameters, including some we use in our proofs. We then give some bounds from the literature.

Original Contribution
In chapter 6 we present the first section of our original contribution. We study random walks on the Cartesian product F of a pair of graphs G and H. We refer the reader to chapter 6 for a definition of the Cartesian product. After giving definitions and context (including related work from the literature), we describe a probabilistic technique which we use to analyse the cover time. We then present a number of lemmas relating to the effective resistance of products of graphs. We apply the above to the problem of the cover time, and develop bounds on the cover time of the product F in terms of properties of the factors G and H. The resulting theorem can be used to demonstrate when the cover time of one of the factors dominates the other, and becomes of the same order or within a logarithmic factor of the cover time of the product as a whole. The probabilistic technique we introduce and the effective resistance lemmas may be of independent interest. This chapter is based on joint work with Colin Cooper and Tomasz Radzik, published in [2].
In chapter 7, we give a precise asymptotic result for the cover time of a random graph with given degree sequence d. That is, if a graph G on n vertices is picked uniformly at random from the set G(d) of all simple graphs with vertices having pre-specified degrees d, then with high probability (whp), the cover time tends to a value τ that we present. The phrase with high probability means with probability tending to 1 as n tends to ∞. After giving an account of the necessary theory, we give a proof that a certain structural property of graphs, known as the conductance, is, whp, bounded below by a constant for a G chosen uar from G(d). This allows us to use some powerful theory from the literature 1.2 Overview of the Thesis to analyse the problem. We continue our analysis with further study of the structural properties of the graphs, and the behavior of random walks on them.
We use these results to show that whp, no vertex is unvisited by time τ + , where is some quantity that tends to 0. For the lower bound, we show that at time τ − , there is at least one unvisited vertex, whp. This chapter is based on joint work with Colin Cooper and Alan Frieze, published in [1].
Finally, in chapter 8, we investigate weighted random walks. Graph edges are given non-negative weights and the probability that an edge e is transitioned from a vertex u is w(e)/w(u), where w(e) is the weight of e and w(u) is the total weight of edges incident on u. We present from the literature a weighting scheme that has a worst case cover time better than a simple random walk. We then present our own weighting scheme, and show that it also has this property. We give an upper bound for the cover time of a weighted random walk on a random graph of given degree sequence weighted according to our scheme. We demonstrate that the speed-up (that is, the ratio of cover times) over a simple random walk can be unbounded. This chapter is based on joint work with Colin Cooper. Chapter 2 Definitions and Notation

Graphs
A graph G is a tuple (V, E), where the vertex set V is a set of objects called vertices and the edge set E is a set of two-element tuples (u, v) or two-element sets {u, v} on members of V . The members of E are called edges. Graphs can be directed or undirected. In a directed graph the tuple (u, v) is considered ordered, so (u, v) and (v, u) are two different edges. In an undirected graph, in line with the conventions of set notation, the edge {u, v} can be written as {v, u}. However, in the standard conventions of the literature, edges of undirected graphs are usually written in tuple form, and tuples are considered unordered. Thus, the edge {u, v} is written (u, v), and is included only once in E. We shall use this convention throughout most of the thesis, and be explicit when departing from it. Furthermore, we may use the notation u ∈ G and e ∈ G to stand for u ∈ V and e ∈ E respectively.
In this thesis, we deal only with finite graphs, that is, both V and E are finite, and we shall sometimes use the notation V (G) and E(G) to denote the vertex and edge set respectively of a graph G.

Graphs
A loop (u, u) is an edge from a vertex u to itself. In a multigraph, a pair of vertices u, v can have more than one edge between them, and each edge is included once in E. In this case, E is a multiset. A graph is simple if it does not contain loops and is not a multigraph.
For a vertex u ∈ V , denote by N (u) ⊆ V the neighbour set of u, Denote by d(u) or d u the degree of u. This is the number of ends of edges incident on u, i.e., The second term in the sum shows that we count loops twice, since a loop has two ends incident on u. When G is simple it is seen that When a graph is directed, there is an in-degree and an out-degree, taking on the obvious definitions.
If |V | = n then G can be represented as a n × n matrix A = [a i,j ], called the adjacency matrix. Without loss of generality, assume that the vertices are labelled 1 to n, then in A, a i,i = 2l where l is the number of loops from i to itself, and for i = j, a i,j is the number of edges between i and j.
A walk in a graph G is a sequence of (not necessarily distinct) vertices in G, A walk is a path if and only if no vertex appears more than once in the sequence. If v 0 = v t and this is the only vertex that repeats then then the walk is a cycle.
is a walk, the length (w) = t, of the walk is one less than the number of elements in the sequence. The distance between u, v is The following simple lemma is very useful and common in the study of graphs. See, e.g., [30].
Lemma 1 (Handshaking Lemma). For an undirected graph G = (V, E), Note, there is no requirement that G be connected or simple.

Weighted Graphs
Graphs may be weighted, where in the context of this thesis, weights are nonnegative real numbers assigned to edges in the graph. They can be represented as G = (V, E, c) where c : E → R + is the weight function. We further define The weight of the graph, w(G), is By the same arguments as the Handshaking Lemma 1, w(G) = c(G)/2.
For convenience, we may also define that is, the total weight of edges between u, v.
Analogous definitions can be given for directed graphs.

Examples
We define some specific classes of graphs which will feature in subsequent chapters. All are simple, connected and undirected. Without loss of generality, we may assume that vertices are labelled [0, n − 1], where n = |V |.

Complete graph
The complete graph on n vertices, denoted by K n is the graph such that
We say a graph G has a cycle if Z r ⊆ G for some r.

Trees
A tree T is a graph satisfying any one of the following equivalent set of conditions (see, e.g., [30]): T is connected and has no cycles; T has no cycles, and a cycle is formed if any edge is added to T ; T is connected, and it is not connected anymore if any edge is removed from T ; Any two vertices in T can be connected by a unique path; T is connected and has n − 1 edges.
If, for a graph G, there is some tree T ⊆ G such that V (T ) = V (G), then T is called a spanning tree of G.

Markov Chains
Let Ω be some finite set. A Markov chain is a sequence X = (X 0 , X 1 , . . .) of random variables with X i ∈ Ω having the Markov property, that is, for all t ≥ 0 If, in addition, we have for all t ≥ 1, then the Markov chain is time-homogeneous. Such Markov chains can be defined in terms of the tuple M = (Ω, P, The first element of the sequence X 0 is drawn from some distribution on Ω, and in many applications this distribution is concentrated entirely on some known 2.2 Markov Chains starting state. Equations (2.8) and (2.9) together express the fact that, given knowledge of X t−1 , we have a probability distribution on X t , and this distribution is independent of the history of the chain before X t−1 . That is, if X t−1 is known, any knowledge of X s for s < t − 1 (should it exist) does not change the distribution on X t . This is called the Markov property or memoryless property.
Without loss of generality, label the n states of the Markov chain [1, n]. Let be the vector representing the distribution on states at time t. The first state X 0 will be drawn from some distribution p(0), possibly concentrated entirely on one state. It is immediate that we have the relation for any state of the Markov chain i. Alternatively, For any s ≥ 1, define the s-step transition probability and let P (s) = [P (s) i,j ] be the corresponding transition matrix. Observe that P (1) = P and that

Thus,
and by induction on s, P (s) = P s .

Random Walks on Graphs
The above is consistent with the idea that P (0) = I, since this merely says that For a Markov chain M with X 0 = i, define h i (j) = min{t ≥ 0 : X t = j} and h + i (j) = min{t ≥ 1 : X t = j}. We define the following First return time to i Commute time between u and v

Random Walks on Graphs
A walk on a graph, as defined in section 2.1, is a sequence of vertices connected by edges (v 0 , v 1 , v 2 , . . .). A random walk is a walk which is the outcome of some random process, and a simple random walk is a random walk in which the next edge transitioned is chosen uniformly at random from the edges incident on a vertex.
Random walks on graphs are a specialisation of Markov chains. For a graph

Random Walks on Graphs
, the state space of the Markov chain is the set of vertices of the graph V , and a transition from a vertex u is made by choosing uniformly at random (uar) from the set of all incident edges and transitioning that edge. For undirected graphs, an edge can be traversed in either direction, and a loop counts twice. In a directed graph, the convention is that an edge is traversed in the direction of the arc, and so, where there is a directed loop, only one end can be transition.
We give formal definitions. Let G = (V, E) be an unweighted, undirected simple graph. The Markov chain More generally, when G = (V, E, c) is weighted, undirected (and not necessarily simple) and Observe, that by the above definitions, and the definition of c(u), a walk on an unweighted graph is the same (meaning, has the same distribution) as a walk on a uniformly weighted graph (that is, all edges have the same weight). Conventionally, when an unweighted graph is treated as a weighted graph, edges are given unit weight.
Analogous definitions can be given for directed graphs.
Some more notation concerning random walks: Let W u denote a random walk started from a vertex u on a graph G = (V, E). Let P (t)

Random Walks on Graphs
For a random walk W u , let c u = max v∈V h u (v) where h u (v) was defined in section 2. 2. In addition to the quantities defined in that section (which are defined also for random walks on graphs, since they are a type of Markov chain), we define the following

Chapter 3
Theory of Markov Chains and Random Walks

Classification of States
The states of a Markov chain exhibit different behaviours in general. It is often the case that some of these properties can be ascertained by visual inspection of the graph of the chain, particularly when the graph is small.
Much of what follows is standard material in an introduction to the topic. Aside from minor modifications, we quote heavily from [61] for many of the following definitions and lemmas.
As before, we shall assume without loss of generality that the states of a chain with n states are labelled [1, n].
i,j > 0 for some integer t ≥ 0. If two states i and j are accessible from each other we say they communicate and we write i ↔ j.

Classification of States
In the graphical representation of a chain i ↔ j if and only if there is a directed path from i to j and there is a directed path from j to i.
For random walks on undirected graphs, this is equivalent to a path existing between i and j. The following lemma is easy to confirm, and we omit the proof.
The communicating relation defines an equivalence relation, that is, it is Note that a self-loop is not required for a state to be reflexive, since P For random walks on undirected graphs, the communicating classes are the connected components of the graph.

Classification of States
Denote by f (t) i,j the probability that, starting at state i, the first time the chain visits state j is t; that is 1. At least one state is recurrent.

All recurrent states are positive recurrent.
The proof is left as an exercise, thus we include our own.

Proof
1. Since there are a finite number of communicating classes, and since once the chain leaves a communicating class it cannot return, it must eventually settle into one communicating class. Thus, at least one state in this class is visited an unbounded number of times after the chain enters it. 2. The communicating class of a recurrent state has no transition outside that class, since otherwise there would be a positive probability of no return. Consider a recurrent state i of an n-state Markov chain. Let C(i) denote the communicating class of i. Let p be the largest transition probability less than 1 from any of the states in C(i). Any walk of the chain of length ≥ n in C(i) that avoids i must include at least one transition with probability at most p. Then for any j ∈ C(i), j = i, The above gives the following We next discuss periodicity of Markov chains. As suggested by the name, periodicity is a notion of regular behaviour of Markov chains.
A discrete time Markov chain is periodic if any state in the chain is periodic. A state or chain that is not periodic is aperiodic.
There is an equivalent definition of an aperiodic state; [64] p. 40, gives the following definition.
This is followed by the following theorem, which establishes an equivalence between the two definitions. i,i > 0} has no common divisor other than 1.
In [64], the proof is left as an exercise to the reader, and so we present a proof below.

Proof
⇒ If S has a common divisor ∆ > 1, then any t ≥ 1 that is not a multiple of ∆ is not in S, and so P (t) i,i = 0 in this case.
⇐ Let t 1 = min S. Since t 1 has a finite number of factors, and since for any S , S ⊆ S we have S ⊆ S ⇒ gcd(S ) ≥ gcd(S ), we deduce that there must be some finite S ⊆ S with t 1 ∈ S such that gcd(S ) = 1. By the extended Euclidean algorithm (see, e.g. [46]) -or, in fact, Bézout's lemma -there must be some a j ∈ Z such that a 1 t 1 + a 2 t 2 + . . . a r t r = 1, where the t j are members of S .

The Stationary Distribution
Now a j = a j (mod t 1 ) for some 0 ≤ a j < t 1 , so substituting a j for a j in equation (3.1) and taking it modulo t 1 we have , then t = mt 1 +s for some non-negative integer m. Since any positive sum of elements in S is an element in S, it follows that P Finally for this section, we define and discuss ergodicity: ). An aperiodic, positive recurrent state is an ergodic state.
A Markov chain is ergodic if all of it's states are ergodic.
As a corollary to the above theorems, we have Corollary 6 ([61]). Any finite, irreducible, and aperiodic Markov chain is an ergodic chain.

Proof
A finite chain has at least one recurrent state by Lemma 3 and if the chain is irreducible, then all of its states are recurrent. In a finite chain, all recurrent states are positive recurrent by Lemma 3 and thus all states of the chain are positive recurrent and aperiodic. The chain is therefore ergodic. 2 The significance of ergodicity is made clear in the following section.

The Stationary Distribution
Recall that the distribution on the states evolves with this relation

The Stationary Distribution
A fundamental question is when, if ever, there exists a distribution that remains invariant under the operation of post-multiplication by the transition matrix.

Definition 8 ([61]).
A stationary distribution (also called an equilibrium distribution) of a Markov chain is a probability distribution π such that π = πP.
A chain in the stationary distribution will continue to be so after subsequent transitions.
We now quote an important theorem from [61], but omit the proof, which although not difficult, is fairly lengthy.

Theorem 7 ([61]
). Any finite, irreducible, and ergodic Markov chain has the following properties: 1. the chain has a unique stationary distribution π = (π 1 , π 2 , . . . π n ); 2. for all i and j, the limit lim t→∞ P (t) i,j exists and is independent of i; There are a number of other proofs of Theorem 7; [64] gives a proof based on coupling; [57] gives a different different proof also based on coupling; [59] gives a treatment specialised for connected undirected graphs using the framework of linear algebra, in particular, the eigenvalues of the transition matrix and the Perron-Frobenius theorem to show the existence and convergence to the stationary distribution.
For a random walk on an undirected graph that is finite, connected and not bipartite, the conditions of ergodicity and thus the conditions for Theorem 7 are satisfied.

Random Walks on Undirected Graphs
For a random walk on an undirected graph a pair of vertices u, v communicate if there is a path between them. Furthermore, as stated above, the communicating classes are the connected components of the graph and so the random walk is irreducible if and only if the graph is a single connected component. For aperiodicity, we quote the following lemma from [61], along with the accompanying proof.

Lemma 8 ([61]). A random walk on an indirected graph G is aperiodic if and
only if G is not bipartite.

Proof
A graph is bipartite if and only if it does not have cycles with an odd number of edges. In an undirected graph, there is always a path of length 2 from a vertex to itself. If the graph is bipartite, then the random walk is periodic with period 2. If the graph is not bipartite, then it has an odd cycle and by traversing the cycle, an odd-length path can be constructed from any vertex to itself. It follows that the Markov chain is aperiodic . 2 Thus, by Corollary 6 and Lemma 8 it is seen that Corollary 9. A random walk on an undirected graph that is finite, connected and non-bipartite is ergodic.
The existence of the stationary distribution and the convergence of the walk to it is thus established.

Theorem 10 ([61]).
A random walk on an undirected graph G = (V, E) that is finite, connected, and not bipartite converges to the stationary distribution π where, for any vertex v ∈ V

Time Reversal and a Characterisation of Random Walks on Undirected Graphs
Proof By the handshaking lemma, v∈V d(v) = 2|E|. Thus, it follows that and so π is a proper probability distribution over V . Let P be the transition matrix of the walk on G and let N (v) represent the neighbour set of v. The relation π = πP is equivalent to and the theorem follows. The above proof is for simple graphs. It can be generalised for graphs with loops and/or parallel edges by with stationary probability d(v) 2|E| where now d(v) is given by (2.2). The theorem can be further generalised to (not necessarily simple) weighted graphs with stationary probability π v = c(v) c(G) . See section 2.3 for relevant definitions.

Random Walks on Undirected Graphs
This section discusses a characterisation of Markov chains that precisely captures random walks on undirected graphs, including non-simple graphs (those with loops and/or parallel edges) as well as weighted undirected graphs. To do so we introduce the following definition, taken from [64] Definition 9. Let (X t ) 0≤t≤T be a (sub)sequence of states of a Markov chain M = (Ω, P, π) where π is the stationary distribution of M. The time reversal of (X t ) 0≤t≤T is the sequence

Time Reversal and a Characterisation of Random Walks on Undirected Graphs
The following theorem is given in [64], and we omit the proof.
Theorem 11. Let (X t ) 0≤t≤T be a (sub)sequence of states of a Markov chain M = (Ω, P, π) where π is the stationary distribution of M. Then (Y t ) 0≤t≤T is a (sub)sequence of states of a Markov chain M = (Ω, P, π) where P = [ P i,j ] is given by and P is also irreducible with stationary distribution π.
This leads us to the following definition Definition 10. If P = P then the Markov chain M is said to be time reversible.
If a Markov chain is reversible, then (3.2) becomes known as the detailed balance condition.
Conversely, if the detailed balance condition is satisfied for some distribution p, that is p j P j,i = p i P i,j for all i, j then p is the stationary distribution, which, along with irreducibility and Theorem 11, implies the following The next theorem characterises Markov chains as random walks.
Theorem 13. Random walks on undirected weighted graphs are equivalent to time reversible Markov chains. That is, every random walk on a weighted graph

Time Reversal and a Characterisation of Random Walks on Undirected Graphs
is a time reversible Markov chain, and every time reversible Markov chain is a random walk on some weighted graph.

Proof
The transition matrix for a random walk on a weighted undirected graph G = (V, E) defines where c(u, v) is defined by (2.7) (and therefore valid for non-simple graphs). Thus Hence, the detailed balance condition is satisfied and by Corollary 12, the random walk is a reversible Markov chain.
Consider some reversible Markov chain M = (Ω, P, .) with transition matrix P and where, as before, we assume the states are labelled [1, n]. We define a weighted graph G = (V, E) based on M as follows: Let V = Ω, let (i, j) ∈ E if and only if P i,j > 0 and weight the edge (i, j) as c(i, j) = π i P i,j . By reversibility, the detailed balance equations imply c(i, j) = c(j, i), hence weights are consistent and the weighted graph is proper. The random walk on the graph, by construction, has transition matrix P. 2

Chapter 4
The Electrical Network Metaphor In this chapter we give an introduction to the electrical network metaphor of random walks on graphs and present some of the concepts and results from the literature that are used in subsequent parts of this thesis. Although a purely mathematical construction, the metaphor of electrical networks facilitates the expression of certain properties and behaviours of random walks on networks, and provides a language for which to describe these properties and behaviours. The classical treatment of the topic is [33]. The recent book [57] presents material within the more general context of Markov chains. Other treatments of the topic are found in [4] and [59].
We first present some definitions.

Electrical Networks: Definitions
An electrical network is a connected, undirected, finite, graph G = (V, E) where each edge e ∈ E is has a non-negative weight c(e). The weight is called the conductance. The resistance of an edge e, r(e) is defined as the reciprocal of the conductance, 1/c(e) if c(e) is finite, and is defined as ∞ if c(e) = 0. It is quite often the case in the literature that in the context of electrical networks, the vertices of the network are referred to as nodes. We shall use the terms 'graph' and 'network', and 'vertex' and 'node', interchangeably in the context of electrical network metaphor.
A random walk on an electrical network is a standard random walk on a weighted graph, as per the definition of section 2. 3. A random walk on an electrical network are therefore equivalent to time reversible Markov chains by Theorem 13.
Since edges are always weighted in the context of electrical networks, we shall use the notion G = (V, E, c) for the network, where the third element of the tuple is the weighting function on the edges.

Harmonic Functions
where P u,v is defined by equations (2.10) and (2.11).
For some set V B ⊂ V , called boundary nodes, call the complement V I = V \ V B internal nodes.

Harmonic Functions
that is harmonic on the internal nodes V I attains it's minimum and maximum values on the boundary. That is, there are some b, B ∈ V B such that for any

Proof
We start with the upper bound. Let M = max x∈V f (x) and let is a weighted average of its neighbours. It follows that f (y) = M for each neighbour y of x, i.e., y ∈ V M . Iterating this repeatedly over neighbours, we see that any path in the network x = x 0 , x 1 , . . . , x r = z must have the property that each x i ∈ V M . Since a network is connected by definition (see 4.1), there must be a path from x to some z ∈ V B , in which case we get a contradiction, and therefore deduce that V B ∩ V M = ∅. A similar argument holds for the minimum. 2 R is unique if f is harmonic on all the internal nodes V I .

Proof
Suppose there are functions f, g which extend f V B and are harmonic on each node in V I . Consider h = f − g. This function has h(v) = 0 for any v ∈ V B , and is harmonic on V I . It follows by Lemma 14 that h(v) = 0 for any v ∈ V I as well. Therefore g = h. 2 The problem of extending a function f V B to a function f harmonic on V I is known as the Dirichlet problem, in particular, the discrete Dirichlet problem, (in contrast to the continuous analogue). For electrical networks (and in fact more generally, for irreducible Markov chains), a solution to the Dirichlet problem always exists, as provided by the following function.
thus, f is consistent with f V B on the boundary nodes.
This proves harmonicity on V I .

Voltages and Current Flows
Consider a network G = (V, E, c) and let a pair of nodes a and z be known as the source and sink respectively. Treating a, z as the only elements of a boundary set on the network, a function W harmonic on V \ {a, z} is known as a voltage.

Voltages and Current Flows
define the divergence of ϕ at a node u to be div ϕ(u) = Observe, for a flow ϕ, We term as a flow from a to z a flow ϕ satisfying The strength of a flow ϕ from a to z is defined to be ϕ = div ϕ(a) and a unit flow from a to z is a flow from a to z with strength 1. Observe also that by (4.2) div ϕ(a) = − div ϕ(z).
Given a voltage W on the network, the current flow I associated with W is defined on oriented edges − → e = ( −→ u, v) by the following relation, known as Ohm's Law : Conductances (resistances) are defined for an edge with no regard to orientation, so in (4.3) we have used for notational convenience that c(e) = c( − → e ) = c( ← − e ).
We will continue to use this.
Let Now let I W be the current flow by a voltage W on G (with some chosen source and sink) and I T (W ) the current flow from the transformation T applied to W . It can be seen from the definition of current flow that I T (W ) = α · I W . In particular, this means that current flow is invariant with respect to β. Thus, assuming constant edge conductances, current flow is determined entirely by ∆ W = W (a) − W (z). We may therefore denote the current flow determined by ∆ W by I ∆ W . Observe I 0 = 0 and I α·∆ W = α · I ∆ W . Thus if, for a given G, any finite, non-zero current flow exists, then I ∆ W as a function of ∆ W is a bijective mapping from R to R. In particular, if any finite, non-zero current flow exists, then a unit current flow exists and is unique.
We show that I is a flow from a to z when W (a) ≥ W (z). Firstly, consider any node u / ∈ {a, z}: The last line follows because

Effective Resistance by definition and
by harmonicity.
Thus, having proved both conditions of the definition, it is shown that the current flow is a flow from a to z. Furthermore, since setting ∆ W = W (a) − W (z) = 1 will give some current flow I 1 , setting W (a) − W (z) = 1/ I 1 will give a unit current flow.
The significance of the unit current flow will become clear in the discussion of effective resistance.

Effective Resistance
We begin with the definition Definition 11. Let G = (V, E, c) be a network, and let a, z be a pair of nodes in the network. Let W be any voltage with a, z treated as source and sink respectively and with W (a) ≥ W (z). Using the notation of Section 4.3, the effective resistance between a and z, denoted by R(a, z) is defined as Clearly, for this definition to be proper, the ratio has to be invariant with respect 4.4 Effective Resistance to voltages, and indeed it was shown in section 4.3 that I α·∆ W = α · I ∆ W , thus preserving the ratio.
It is important to note that the resistance r(u, v) of an edge (u, v) is different to the effective resistance R(u, v) between the vertices u, v. Resistance r(u, v) is 1/c(u, v), the inverse of conductance, which is part of the definition of the network G = (V, E, c), and is the weighting function c defined on an edge. Effective resistance, on the other hand, is a property of the network, but not explicitly given in the tuple (V, E, c), and it is defined between a pair of vertices.
Theorem 17 ([33] or [57]). Effective resistance forms a metric on the nodes of Note, the sum in (4.4) is over unoriented edges, so each edge e is considered only once. Because flow is antisymmetric by definition, the term [ϕ(e)] 2 is unambiguous.
The following theorem is useful in using current flows to approximate effective resistance. We shall see such an application in section 6. 8. For a proof, see, for example [57].

Effective Resistance
The unit current flow is the unique ϕ that gives the minimum element of the above set.

Rayleigh's Monotonicity Law, Cutting & Shorting
Rayleigh's Monotonicity Law, as well as the related Cutting and Shorting Laws, are intuitive principles that play important roles in our work. They are very useful means of making statements about bounds on effective resistance in a network when the network is somehow altered. With minor alterations of notation, we quote [57] Theorem 9.12, including proof.
and c, c are two different weightings of the network such that r(e) ≤ r (e) for all e ∈ E, (recall, r(e) = 1/c(e)), then for any u, v ∈ V , where R(u, v) is the effective resistance between u and v under the weighting c (or r), and R (u, v) under weighting c (or r ).

Proof
Note that min ϕ e∈E [ϕ(e)] 2 r(e) ≤ min ϕ e∈E [ϕ(e)] 2 r (e) and apply Thomson's Principle (Theorem 18). 2 Lemma 20 (Cutting Law). Removing an edge e from a network cannot decrease the effective resistance between any vertices in the network.

Proof
Replace e with an edge of infinite resistance (zero conductance) and apply Rayleigh's Monotonicity Law.

Effective Resistance
A new edge has the same conductance as the edge it replaced. Let G denote the network after this operation, and let R and R represent effective resistance in G and G respectively. Then, for a pair of vertices a, z,

Proof
Consider nodes a, z / ∈ {u, v} of the network G = (V, E, c), and let G denote G after a Shorting operation on u, v. For any flow ϕ from a to z in G, we can define a flow ϕ in G as follows: For any e = (x, y) such that (again, orientating the loops arbitrarily). It is easily seen that ϕ is a valid unit flow from a to z, and that the energy on each edge is the same for both ϕ and ϕ . It follows that E(ϕ ) = E(ϕ). Hence by Thomson's Principle, if ϕ = ϕ min , the unit current flow from a to z in G, then R (a, z) ≤ E(ϕ ) = E(ϕ) = R(a, z) A similar argument can be made for R (a, w) ≤ R(a, u) and R (a, w) ≤ R(a, v). 2 Sometimes the Shorting Law is defined as putting a zero-resistance edge between u, v, but since zero-resistance (infinite-conductance) edges are not defined in our presentation, we refer to the act of "putting a zero-resistance edge" between a pair of vertices as a metaphor for shorting as defined above.

Commute Time Identity
The following theorem, first given in [18] is a fundamental tool in our analysis of random walks on graphs, in chapter 6. The proof is not difficult but we omit it because a presentation would be lengthy. We refer to [18] or [57] for a proof.
Then for a pair of vertices

Parallel and Series Laws
(The reader is reminded that c(G) = v∈V c(v) = 2 e∈E c(e), as defined in (2.5)).

Parallel and Series Laws
The parallel and series laws are rules that establish equivalences between certain structures in a network. They are useful for reducing a network G to a different form G , where the latter may be more convenient to analyse. We quote from [57], with minor modifications for consistency in notation.

Lemma 23 (Parallel Law). Conductances in parallel add.
Suppose edges e 1 and e 2 , with conductances c(e 1 ) and c(e 2 ) respectively, share vertices u and v as endpoints. Then e 1 and e 2 can be replaced with a single edge e with c(e) = c(e 1 )+c(e 2 ), without affecting the rest of the network. All voltages and currents in G\{e 1 , e 2 } are unchanged and the current For a proof, check Ohm's and Kirchhoff's laws with I( − → e ) = I( − → e 1 ) + I( − → e 2 ).

Lemma 24 (Series Law). Resistances in series add.
If v ∈ V \ {a, z}, where a and z are source and sink, is a node of degree 2 with neighbours v 1 and v 2 , the edges . All potentials and currents in G \ {v} remain the same and the current that flows from

Chapter 5 Techniques and Results for Hitting and Cover Times
In this chapter we present some of the techniques for bounding hitting and cover times, as well as particular results. We start with section 5.1 where we give calculations for hitting and cover times of some particular graph structures. The graph classes that are the subject of the next section are important for subsequent chapters, and as examples, they serve to convey some of the techniques used to precisely calculate hitting and cover time. This allows comparisons to be drawn with more general techniques and bounds. In general, it is quite difficult to calculate precise cover times for all but a few classes of graphs; the examples given in section 5.1 are amongst the simplest and most common structures studied in the literature.
We refer the reader to section 2.1.2 for reminders on definitions of graph structures and section 2.3 for a reminder of relevant notations and definitions relating to random walks on graphs.
We only deal with connected, undirected graphs in this chapter.
The n'th harmonic number, h(n) = n i=1 1 i is a recurring quantity, and a short

Precise Calculations for Particular Structures
hand proves useful. Note h(n) = ln n + γ + O(1/n) where γ ≈ 0.577 (see, e.g. [19]). Thus even for relatively small values of n, ln n is a close approximation for h n .

Precise Calculations for Particular Structures
We deal with three particular classes of graphs: complete graphs, paths and cycle. These results are given in [59], amongst others.

Complete Graph
Theorem 25. K n = (V, E) be the complete graph on n vertices.
and d(u) = n − 1 for any u ∈ V . Now use Theorem 10 and Theorem 7.
(iii) Let T (r) be the expected number of steps until r distinct vertices have been visited by the walk for the first time. By the symmetry of the graph, T (r) will be invariant with respect to starting vertex. Suppose the walk starts at some vertex u ∈ V . Then T (1) = 0. Since it will move to a new vertex in the next step, T (2) − T (1) = 1. Suppose it visits the r'th distinct vertex at some time t,

Precise Calculations for Particular Structures
where r < n. Then there are n − r unvisited vertices, and the time to visit any vertex from this set is a geometric random variable with probability of success n−r n−1 , the expectation of which is n−1 n−r = T (r + 1) − T (r). Thus by linearity of expectation, Thus, COV[K n ] ∼ n ln n.

Path
Without loss of generality, we label the vertices of the n-vertex path graph, P n by the set [0, n − 1], where labels are given in order starting from one end, i.e., P n = (0, 1, 2, . . . , n − 1).

Theorem 26.
Let P n be the path graph on n vertices.
, because when the walk is on vertex n − 1, it has no choice but to move to vertex n−2 in the next step. So we have H[n−2, n−1] = 2(n−1)−1.

Precise Calculations for Particular Structures
Furthermore, H[r − 1, r] = 2r − 1 for any 0 < r ≤ n − 1, since this is the same as H[r − 1, r] on P r+1 . We have, by linearity of expectation, (iii) Our analysis will be more notationally convenient with n + 1 vertices than with n vertices. Let a r denote the expected time to reach either one of the ends, when starting on some vertex r ∈ [0, n]. The variables a r satisfy the following system of equations: A solution is a r = r(n − r): a 0 = 0(n − 0) = 0 = n(n − n) = a n , and Furthermore, this is the only solution. This can be seen by studying the system of equations written as a matrix equation, and determining that the equations are linearly independent, but a more elegant method relies on the principle that harmonic functions achieve their maximum and minimum on the boundary, as expressed in Lemma 14: Suppose that there is some other solution a r set the system of equations (5.1). Consider f r = a r − a r . We have f 0 = a 0 − a 0 = 0,

Precise Calculations for Particular Structures
and f n = a n − a n = 0. Furthermore, for 0 < r < n, Thus, f r is harmonic on [1, n − 1]. Since f r = 0 on the boundary vertices 0, n, by Lemma 14 f r = 0 for r ∈ [1, n − 1], and so a = a.
To cover P n+1 when starting at vertex r ∈ [0, n], the walk needs to reach either one of the ends, then make its way to the other. Thus When n is even (i.e, the path P n+1 has an odd number of vertices), then COV r [P n+1 ] is maximised at r = n 2 , in which case, When n is odd, COV r [P n+1 ] is maximised at r = n 2 or r = n 2 , in which case,

Cycle
Theorem 27. Let Z n be the cycle graph on n vertices.
(i) R[u] = n for any vertex u.

Proof (i)
The vertices all have the same degree, so by symmetry, and in conjunction with Theorem 10, π u must be the same for all u ∈ V , that is, π u = 1/n. Now apply Theorem 7.
(ii) We use the principles of the proof of Theorem 26. We assume the vertices of Z n are labelled with [0, n − 1] in order around the cycle. Hence, vertex 0, for example, would have vertices 1 and n − 1 as neighbours. We wish to calculate H[r, 0]. Observe that there are two paths from r to 0; one path is (r, r − 1, . . . , 0). On this path the distance between vertices r and 0 is r. The other path is (r, r + 1, . . . , n − 1, 0). The distance between r and 0 on this path is (n − r). By the same principles as the proof of Theorem 26, we calculate H[r, 0] by equating it with the expected time it takes a walk to reach 0 or n of a path graph (0, 1, 2, . . . , n), when the walk starts at vertex r. As calculated for Theorem 26, this is r(n − r).
(iii) To determine the cover time, observe that at any point during the walk, the set of vertices that have been visited will be contiguous on the cycle; there will be an "arc" (path) of visited vertices, and another of unvisited. Let T (r) be expected time it takes a walk starting at some vertex to visit r vertices of Z n . Given that the walk does indeed start on some vertex, we have T (1) = 0. After it moves for the first time, it visits a new vertex, thus giving T (2) − T (1) = 1. By linearity of expectation,

General Bounds and Methods
Suppose the walk has just visited the r'th new vertex, where r < n. Without loss of generality, we can label that vertex r, and further label the arc of already visited neighbours (r − 1, r − 2, . . . , 1), in order. The arc of unvisited vertices is labelled (r + 1, r + 2, . . . , n − 1, 0), such that (r, r + 1) and (0, 1) are edges on the cycle. Thus, the next time the walk visits a new vertex, it will be either the vertex labelled r + 1 or the vertex labelled 0 in the current labelling. Hence, T (r + 1) − T (r) is the same as the expected time it takes a walk on a path graph (0, 1, 2, . . . , r + 1) to reach 0 or r + 1, when it starts on vertex r. As calculated above, this is r(r + 1 − r) = r. Equation (5.2) can thus be calculated as

General Bounds and Methods
In this section, we detail two general approaches for bounding cover times: the spanning tree technique, and the Matthews's technique. Despite the simplicity of the techniques, they can often yield bounds that are within constant factors of the actual cover time. Both methods can be applied to a graph under question, but it is often the case that one is more suited, i.e, yields tighter bounds -than the other for a particular graph. In both cases, the effectiveness of the technique is dependent on finding suitable bounds on hitting times between vertices (or sets of vertices), as well as the way in which the technique is applied.

Upper Bound: Spanning Tree and First Return
Time Let G = (V, E) be an undirected, unweighted, simple, connected graph. Let n = |V | and m = |E|. One way to upper bound the cover time of G is to choose some sequence of vertices σ = (v 0 , v 1 , . . . , v r ) such that every vertex in V is in σ, and sum the hitting time from one vertex to another in the sequence; that is, Proposition 3. For a tree T = (V, E) we can generate a walk (sequence of edge The sequence σ of Proposition 3 contains every vertex of V . It can, in fact, be generated be the depth first search (DFS) algorithm started at some vertex v = v 0 . We shall use DFS again in chapter 6. See, e.g., [55] for a discussion of the algorithm.
The following theorem and proof are given given in [61]. The argument itself goes back to [5].
be an undirected, unweighted, simple, connected graph, and let n = |V | and m = |E|.

General Bounds and Methods
For any v ∈ V , using Theorem 10 and Theorem 7, we have But we also know that . . , v 2n−2 ) be a walk as described in Proposition 3. Since each vertex of V occurs in σ, we have

Upper Bound: Minimum Effective Resistance Spanning Tree
In section 5.2.1, we computed an upper bound on the sum of commute times of a spanning tree of G. We can generalise this to trees that span G, that is, include all the vertices of G, but who's edges are not necessarily contained in G.
Let G be a connected, undirected graph. If G is unweighted, assign unit weights (conductances) to the edges of G. Thus, G = (V, E, c).

General Bounds and Methods
Definition 12. Define the complete graph K = (V, E , ρ) where the weighting is the effective resistance between u and v in G. Let T = {T is a spanning tree of K}, and let T * ∈ T be such that w(T * ) ≤ w(T ) for any T ∈ T (recall w(T ) is the total of the edge weights of T , as defined by equation 2.6). We call T * the minimum effective resistance spanning tree of G.
Theorem 29. Let G be a connected, undirected graph. If G is unweighted, assign unit weights (conductances) to the edges of G. Thus, G = (V, E, c).
where T * is the minimum effective resistance spanning tree of G.

Proof
Using Theorem 22, we have for any u, v ∈ V , Now we continue using the same ideas of the proof of Theorem 28: we apply Proposition 3 to generate a sequence σ that transition each edge of T * once in each direction, thereby visiting every vertex of G. The RHS of the second equality of (5 , is the sum of hitting times for the sequence σ. For all but a few simple examples, it can be difficult to determine w(T * ). However, bounds on effective resistances can often be determined using the various tools of electrical network theory; for example, through the use of flows and

General Bounds and Methods
Thomson's principle (Theorem 18), and other tools such as Rayleigh's laws, cutting and shorting laws, etc.

Upper Bound: Matthews' Technique
Theorem 30 (Matthews' upper bound, [62]). For a graph G = (V, E), We refer the reader to, e.g., [57] for a proof. The proof is not difficult, but is fairly lengthy.
The power of the method is two-fold. Firstly, one needs only to bound H * [G], which can be facilitated through electrical network theory as well as consideration of the structure of G. Secondly, it applies also to weighted graphs (note there is no restriction of being unweighted in the statement of the theorem).
To use electrical network theory, we can use the commute time identity of Theorem 22, and use the commute time as an upper bound for hitting time. In this case, (5.6) is expressible as is the maximum effective resistance between any pair of vertices in G.
Despite the simplicity of the inequality, the method can yield bounds on cover time that are within a constant factor of the precise value. This is always the case if H * [G] can be shown to be O(n), since this gives a cover time of O(n log n), and as we shall see in section 5. 3.1, cover times of graphs are Ω(n log n).
One example of an application of Theorem 30 that gives good bounds is on the complete graph. As was established in Theorem 25, has H[u, v] = n − 1 for any pair u, v. The resulting bound is very close to the precise result.

Matthews' Technique for a Subset
The inequality (5.6) bounds the cover time of all the vertices of the graph, but it applies equally to a subset of the vertices V ⊆ V (G):

Lower Bound: Matthews' Technique
There is also a lower bound version of Matthews' technique. A proof is given in [57].
Theorem 32 (Matthews' lower bound [62]). For the graph G = (V, E), When using Theorem 32, one needs to be careful with the choice of A; the end of a path has hitting time 1 to its neighbour. Thus, if both of these vertices are included in A, the bound is no better than log n, and of course, cover time is at 5.3 General Cover Time Bounds least n.
A refinement on Theorem 32 was given in [74]. We shall quote it as in [37], since this is simpler notation.
. Let S be a subset of vertices of G and let t be such that for

Asymptotic General Bounds
In two seminal papers on the subject of cover time, Feige gave tight asymptotic bounds on the cover time. As usual, the logarithm is base-e unless otherwise stated.

Theorem 34 ([37]).
For any graph G on n vertices and any starting vertex u This lower bound is exhibited by K n the complete graph on n vertices, as was demonstrated in Theorem 25. It is proven using Lemma 33. It is shown that at least one of the two conditions hold for any graph.  The upper bound is as follows For any connected graph G on n vertices The quantity CyCOV[G] is the cyclic cover time, which is the expected time it takes to visit all the vertices of the graph in a specified cyclic order, minimised over all cyclic orders. Clearly, Consider the lollipop graph, which is a path of length n/3 connected to a complete graph of 2n/3 vertices. Let u be the vertex that connects the clique to the path, and v be the vertex at the other end of the path. It can be determined that This can be seen by applying Theorem 22 to get COM[u, v] and Theorem 26 to get H [v, u]. This demonstrates that the asymptotic values of maximum hitting time and cyclic cover time (and therefore also cover time) can be equal (up to lower order terms) even when the cyclic cover time is maximal (up to lower order terms). Theorem 35 is proved by a contradiction argument on the minimum effective resistance spanning tree T * (see section 5.2.2). A trade off is demonstrated between w(T * ), the sum of effective resistances of edges of T * , and m, the number of edges of the graph. This bounds the cover time as per Theorem 29.

Chapter 6
The Cover Time of Cartesian Product Graphs In this chapter, we study the cover time of random walks on on the Cartesian product F of two graphs G and H. In doing so, we develop a relation between the cover time of F and the cover times of G and H. When one of G or H is in some sense larger than the other, its cover time dominates, and can become of the same order as the cover time of the product as a whole. Our main theorem effectively gives conditions for when this holds. The probabilistic technique which we introduce, based on a quantity called the blanket time, is more general and may be of independent interest, as might some of the lemmas developed in this chapter. The electrical network metaphor is one of the principle tools used in our analysis.
G and H are assumed to be finite (as all graphs in this thesis are), undirected, unweighted, simple and connected. 6 We call G and H the factors of F , and we say that G and H are multiplied together.
We can think of F = G2H in terms of the following construction: We make a copy of one of the graphs, say G, once for each vertex of the other, H. Denote the copy of G corresponding to vertex x ∈ V H by G x . Let a x denote a vertex in G x corresponding to a ∈ V G . If there is an edge (x, y) ∈ E H , then add an edge (a x , a y ) to the construction.
Notation For a graph Γ = (V Γ , E Γ ), denote by In addition we will use use the notation N and M to stand for n F and m F respectively. 6.1 Cartesian Product of Graphs: Definition, Properties, Examples

Properties
Commutativity of the Cartesian Product Operation For a pair of graphs G and H, G2H is isomorphic to H2G; that is, if vertex labels are ignored, the graphs are identical. Note, however, that by (i) of Definition 13, the two different orders on the product operation do produce different labellings.
Vertices and Edges of the Product Graph The number of vertices and edges of a Cartesian product is related to the vertices and edges of its factors as follows: (i) follows from the properties of Cartesian product of two sets, and (i) of Definition 13. To see (ii), we have by (ii)-1 of Definition 13 the following: For a vertex x ∈ V H , there is, for each (a, b) ∈ E G , an edge ((a, x), (b, x)) ∈ E F . That is, we have the set Similarly, we have by (ii)-2 of Definition 13 the following: For a vertex a ∈ V G , there is, for each (x, y) ∈ E H , an edge ((a, x), (a, y)) ∈ E F . That is, we have the set

Associativity of the Cartesian Product and a Generalisation to an Arbitrary Number of Factors
We can extend the definition of the Cartesian product to an arbitrary number of factors: If we always represent the resulting product vertices by r-tuples and edges by pairs of r-tuples, then any bracketing in which a bracket contains a product of two graphs (either of which may be a product itself) will give the same product, that is, the Cartesian product is associative. We can therefore represent it unambiguously by F = G 1 2G 2 . . . 2G r . This assumes the order of the operands is kept the same. If the order is permuted, the tuple representing the vertex labelling will be permuted in the same way, but the two permutations will produce isomorphic products.
For a natural number d, we denote by G d the d'th Cartesian power, that is,

Examples
We give examples of Cartesian product of graphs, some of which are important to the proofs of this chapter. First, we remind the reader of some specific classes of graphs, and define new ones: Let P n denote the n-path, the path graph of 6.2 Blanket Time n vertices. Let Z n represent the n-cycle, the cycle graph with n vertices. The Cartesian product of a pair of paths, P p 2P q is a p × q rectangular grid, and when p = q = n, is a n × n grid, or lattice. The product of a pair of cycles Z p 2Z q is a toroid, and when p = q, is a torus. Both grids and toroids can be generalised to higher powers in the obvious way to give d−dimensional grids and toroids respectively, where d is the number of paths or cycles multiplied together, respectively.
To give another -somewhat more arbitrary -example, a pictorial representation of the product of a triangle graph with a tree is given in Figure 6.1.

Blanket Time
We introduce here a notion that is related to the cover time, and is an important part of the main theorem and the proof technique we use.
. For a random walk W u on a graph G = (V, E) starting at some vertex u ∈ V , and δ ∈ [0, 1), define the the random variable where N v (t) is the number of times W u has visited v by time t and π v is the The following was recently proved in [31].
We define the following . For a random walk W u on a graph G = (V, E) starting at some vertex u ∈ V , define the the random variable where N v (t) is the number of times W u has visited v by time t and π v is the stationary probability of vertex v. The blanket-cover time is the quantity Thus the blanket-cover time of a graph is the expected first time at each vertex v is visited at least π v COV[G] times -which we shall refer to as the blanket-cover criterion.
In the paper that introduced the blanket time, [72], the following equivalence was asserted, which we conjecture to be true.

Blanket Time
In the same paper, this equivalence was proved for paths and cycles. However, we have not found a proof for the more general case. It can be shown without much difficulty that . Using the following lemma, we can improve upon this.

Lemma 37 ([53]).
Let i and j be two vertices and k ≥ 1. Let W k be the number of times j had been visited when i was visited the k-th time. Then for every ε > 0, We use it thus:

Proof
At time t some vertex i must have been visited at least π i t times, otherwise we would get is the number of times v has been visited by time t.
We let the walk run for τ = A(log n)COM * [G] steps where A is a large constant. Some vertex i will have been visited at least π i τ times. Now we use Lemma 37 with k = π i τ . Then for any j, Hence with probability at most 1/n c−1 the walk has failed to visit each vertex j at least π j COV[G] times (by Matthews' bound, 6.3 Relating the Cover Time of the Cartesian Product to Properties of its Factors Theorem 30). We repeat the process until success. The expected number of attempts is 1 + O(n 1−c ). The main theorem of this chapter is the following.
The main part of the work is the derivation of (6.4); the inequality (6.3) is relatively straightforward to derive. Note, by the commutativity of the Cartesian product, G and H in the may be swapped in ( 6.4), subject to the condition n G ≥ D H + 1.
Theorem 39 extends much work done on the particular case of the two-dimensional 6.3 Relating the Cover Time of the Cartesian Product to Properties of its Factors toroid on n 2 vertices, that is, Z 2 n = Z n 2Z n , culminating in a result of [29], which gives a tight asymptotic result for the cover time of Z 2 n as n → ∞. Theorem 39 also extends work done in [52] on powers G d of general graphs G, which gives upper bounds for the cover time of powers of graphs. Specifically, it shows is the number of vertices in the product, and θ G = 2|E|/n is the average degree of G. A formal statement of the theorem is given in section 6.4 and further comparisons made in section 6.5. To prove the Theorem 39, we present a framework to bound the cover time of a random walk on a graph which works by dividing the graph up into (possibly overlapping) regions, analysing the behaviour of the walk when locally observed on those regions, and then composing the analysis of all the regions over the whole graph. Thus the analysis of the whole graph is reduced to the analysis of outcomes on local regions and subsequent compositions of those outcomes. This framework can be applied more generally than Cartesian products.
Some of the lemmas we use may be of independent interest. In particular, Lemmas 47 and 48 provide bounds on effective resistances of graph products that extend well-known and commonly used bounds for the n × n grid. Before we discuss the proof of Theorem 39 and the framework use to produce it, we discuss related work, and give examples of the application of the theorem to demonstrate how it extends that work.

Related Work
A d-dimensional torus on N = n d vertices is the d'th power of an n-cycle, Z d n . The behaviour of random walks on this structure is well studied.
In fact, there is a precise asymptotic value for the 2-dimensional case.
The following result of [52] gives bounds on the cover time for powers of more general graphs: These bounds are tight.
[52] does not address products of graphs that are different, nor does it seem that the proof techniques used could be directly extended to deal with such cases. Our proof techniques are different, but both this work and [52] make use of electrical network theory and analysis of subgraphs of the product that are isomorphic to the square grid P k 2P k .
A number of theorems and lemmas related to random walks and effective resistance between pairs of vertices in graph products are given in [13]. To give the reader a flavour we quote Theorem 1 of that paper, which is useful as a lemma implicitly in this paper and in the proof of [52] Theorem 1.2 to justify the intuition that the effective resistance is maximised between opposite corners of the square lattice.

Cover Time: Examples and Comparisons
Lemma 43 ([13], Theorem 1). Let P n be an n-vertex path with endpoints x and y. Let G be a graph and let a and b be any two distinct vertices of G. Consider the graph G × P n . The effective resistance R((a,x),(b,v)) is maximised over vertices v of P n at v = y.
For P 2 n this is used twice:

Cover Time: Examples and Comparisons
In this section, we shall apply Theorem 39 to some examples and make comparisons to established results.

Cover Time: Examples and Comparisons
This is a factor log 2 N out of the actual value 1 π N log 2 N of Theorem 41. Theorem 42 gives O(N log 2 N ) bound.

Two-dimensional Toroid with a Dominating Factor
Theorem 39 does not cope well with squares, for which Theorem 42 provides strong bounds. Instead it is more effectively applied to cases where there is some degree of asymmetry between the factors. The previous example bounded COV[Z p 2Z q ] for the case where p = q. If, however, p log 4 p = O(q), then we get a stronger result.

Cover Time: Examples and Comparisons
(viii) Thus M = 2pq, and Thus, Comparing this to the lower bound of Theorem 39, which implies Thus, Theorem 39 gives upper and lower bounds within a constant a multiple for this example. That is, it tells us COV[Z p 2Z q ] = Θ(COV[Z q ]) = Θ(q 2 ) subject to the condition p log 4 p = O(q). Looking at it another way, it gives conditions for when the cover time of the product F = G2H is within a constant multiple of the cover time of one of it's factors. We describe that factor as the dominating factor.

Some Notation
For clarity, and because a vertex u may be considered in two different graphs, we may use d G (u) to explicitly denote the degree of u in graph G.
In the notation (., y), the '.' is a place holder for some unspecified element, which may be different from one tuple to another. For example, if we refer to two vertices (., a), (., b) ∈ G2H[S], the first elements of the tuples may or may not be the same, but (., a), for example, refers to a particular vertex, not a set of vertices {(x, a) : a ∈ V (G)}.

The Square Grid
The k × k grid graph P 2 k , where P k is the k-path, plays an important role in our work. We shall analyse random walks on subgraphs isomorphic to this structure. It is well known in the literature (see, e.g. [33], [57]) that for any pair of vertices u, v ∈ V (P 2 k ), we have R(u, v) ≤ C log k where C is some universal constant. We shall quote part of [52] Lemma 3.1 in our notation and refer the reader to the proof there.   Call edges of G[S] interior, edges of A(B) exterior. We say that a walk ω = (u, We , but we leave the 'G' subscript in for clarity). This is precisely the probability that the walk ω is taken by a simple random walk on G starting at u. Let

Locally Observed Random Walk
where the sum is over all exterior walks ω.
We set the edge conductances (weights) of H as follows: If e is an interior edge, c(e) = 1. If it is an exterior edge e = (u, v) define c(e) as Thus the edge weight is consistent. A weighted random walk on H is thus a finite reversible Markov chain with all the associated properties that this entails. The intuition in the above is that we wish to observe a random walk W(G) on a subset S of the vertices. When W(G) makes an external transition at the border B, we cease observing and resume observing if/when it returns to the border. It will thus appear to have transitioned a virtual edge between the vertex it left off and the one it returned on. It will therefore appear to be a weighted random walk on H. This equivalence is formalised thus  (Note the H subscript in c H (e) above is redundant since exterior edges are only defined for H, but we leave it for clarity).

Effective Resistance Lemmas
where the sum is over all exterior walks ω. Thus

Effective Resistance Lemmas
For the upper bound of Theorem 39, we require the following lemmas.
Lemma 46. Let G be an undirected graph. Let G ⊆ G, be any subgraph such that such that V (G ) = V (G). For any u, v ∈ V (G), where R(u, v) is the effective resistance between u and v in G and R (u, v) similarly in G .

Proof
Since V (G ) = V (G), G can be obtained from G by only removing edges. The lemma follows by the Cutting Law (Lemma 20). 2 Denote by R max (G) the maximum effective resistance between any pair of ver- 6.8 Effective Resistance Lemmas tices in a graph G.
Lemma 47. For a graph G and tree T , R max (G2T ) < 4R max (G2P r ) where |V (T )| ≤ r ≤ 2|V (T )| and P r is the path on r vertices.

Proof
Note first the following: (i) By the parallel law, an edge (a, b) of unit resistance can be replaced with two parallel edges between a, b, each of resistance 2.
(ii) By the shorting law, a vertex a can be replaced with two vertices a 1 , a 2 with a zero-resistance edge between them and the ends of edges incident on a distributed arbitrarily between a 1 and a 2 .
(iii) By the same principle of the cutting law, this edge can be broken without decreasing effective resistance between any pair of vertices.
Transformations (i) and (ii) do not alter the effective resistance R(u, v) between a pair of vertices u, v in the network. For any vertex u / ∈ {a 1 , a 2 , a}, R(u, a 1 ) = R(u, a 2 ) and these are equal to R(u, a) before the operation.
Points (ii) and (iii) require elaboration. In this thesis, we do not define zeroresistance (infinite conductance) edges. As stated in section 4.4.1, to say that a zero-resistance edge is placed between a 1 and a 2 , is another way of referring to shorting as defined in Lemma 21. It would seem then, that (ii), in fact says nothing. However, it serves as a useful short hand for talking about operations on the graph when used in conjunction with (iii). If (ii) and (iii) are always used together, that is, if a zero-resistance edge created from (ii) is always cut by (iii), then this is equivalent to the reverse of process of shorting two vertices a 1 and a 2 into a 3 , as per Lemma 21. Hence, these two operations together are sound.
We continue thus: 6.8 Effective Resistance Lemmas In what follows, we shall modify F , but shall continue to refer to the modified graphs as F . 2. Starting from some vertex v in T , perform a depth-first search (DFS) of T stopping at the first return to v after all vertices in T have been visited.
Each edge of T is traversed twice; once in each orientation. Each vertex x will be visited d(x) times. 3. Let (e i ) be the sequence of oriented edges generated by the search. The idea is to use (e i ) to construct a transformation from F = G2T to G2P r . From (e i ), we derive another sequence (a i ), which is generated by following (e i ) and if we have edges e i , e i+1 with e i = (a, b), e i+1 = (b, c) such that it is neither the first time nor the last time b is visited in the DFS, then we replace e i , e i+1 with (a, c). We term such an operation an aggregation.
Observe that in the sequence (a i ), all leaf vertices of T appear only once (just as in (e i )), and a non-leaf vertex appears twice. 4. By (i) above, we can replace each (unit resistance) edge in F by a pair of parallel edges each of resistance 2. 5. For a pair of parallel edges in the T dimension, arbitrarily label one of them with an orientation, and label the other with the opposite orientation. Note, orientations are only an aid to the proof, and are not a flow restriction. We therefore see that (e i ) can be interpreted as a sequence of these parallel oriented edges. 6. We further modify F using (a i ): If (a, b), (b, c) was aggregated to (a, c), then replace each pair of oriented edges ((x, a), (x, b)) and ((x, b), (x, c)) in F with an oriented edge ((x, a), (x, c)). The resistances of ((x, a), (x, b)) and ((x, b), (x, c)) were r((x, a), (x, b)) = 2 and r ((x, b), (x, c)) = 2. Set the resistance r ((x, a), (x, c)) = r((x, a), (x, b)) + r ((x, b), (x, c)) = 4. 7. The above operation is the same as restricting flow through ((x, a), (x, b)) and ((x, b), (x, c)) to only going from one to the other at vertex (x, b),

Effective Resistance Lemmas
without the possibility of going through other edges. The infimum of the energies of this subset of flows is at least the infimum of the energies of the previous set and so by Thomson's principle, the effective resistance cannot be decreased by this operation. 8. For each copy G i of G in F excluding those that correspond to a leaf of T , we can create a "twin" copy G i . Associate with each vertex x ∈ V (F ) (except those excluded) a newly-created twin vertex x with no incident edges. Thus, V (G i ) has a twin set V (G i ), though the latter has no edges yet. 9. Recall the parallel edges created initially from all the edges of F ; we did not manipulate those in the G dimension, but we do so now: redistribute half of the parallel edges of G i in the G dimension to the set of twin vertices V (G i ) so as to make G i a copy of G (isomorphic to it). Now put a zeroresistance edge between x and x . By (ii), effective resistance is unchanged by this operation. 10. We now redistribute the oriented parallel edges in the T dimension so as to respect the sequence (a i ). We do this as follows: follow the sequence (a i ) by traversing edges in their orientation. Consider the following event: In the sequence (a i ) there is an element a j = (a, b) and b has appeared in some element a i such that i < j. Then a j is the second time that b has occurred in the sequence. Now change each edges ((x, a), (x, b)) ∈ F to ((x, a), (x, b) ). If b = v, then stop; otherwise, a j is followed by a j+1 = (b, c), for some c ∈ V (T ). In this case, also change all ((x, b), (x, c)) ∈ F to ((x, b) , (x, c)). Continue in the same manner to the end of the sequence (a i ). 11. We then remove the zero-resistance edges between each pair of twin vertices, and by (iii), this cannot decrease the effective resistance.
Using the sequence (a i ) to trace a path of copies of G, we see that the resulting 6.9 A General bound structure is isomorphic to G2P r . Since the aggregation process only aggregates edges that pass through a previously seen vertex, r is at least |V (T )|. Also, because each edge is traversed at most once in each direction, r is at most 2|V (T )|. Each edge has resistance at most 4, and so the lemma follows.
where k ≤ r ≤ 6k and k ≤ s ≤ 2αk. Considering a series of connected P 2 k subgraphs and using Lemma 44 and the triangle inequality for effective resistance, we have R max (P r 2P s ) ≤ 16(6 + 2α)8h(k), where h(k) is the k'th harmonic number. Since T D 2T H ⊆ G2H, the lemma follows by Lemma 46. 2 A diametric path D is involved in the proof of Lemma 48 because the use of D means that the dimension of P r is effectively maximised, and we can break up the grid P r 2P s roughly into k × k square grids, each with maximum effective resistance O(log k) = O(log D G ). If, for example, the shortest path between a and b is used, the product P r 2P s may have r much smaller than s, looking like a long thin grid, which may have a high effective resistance.

A General bound
In this section, we prove Theorem 39, starting with the lower bound. 6.9 A General bound 6.9.

Lower Bound
The following is a partial restatement of Theorem 39 for the lower bound (inequality (6.3)).
In order for the walk W to cover F , it needs to have covered the H dimension of F . That is, each copy of G in F needs to have been visited at least once. The probability of a transition in the H dimension is distributed as a geometric random variable with success probability at most ∆ H ∆ H +δ G . Thus, the expectation of the number of steps of W per transition in the H dimension is at least ∆ H +δ G ∆ H . Transitions of W in the H dimension are independent of the location of W in the G dimension, and have the same distribution (in the H dimension) as a walk on H. This proves By commutativity, The following proves the upper bound in Theorem 39. It is envisaged that theorem is used with the idea in mind that G is small relative to H, and so the cover time of the product is essentially dominated by the cover time of H. We give a partial restatement of the theorem for the upper bound (inequality (6.4)).
are simple, connected, unweighted and undirected. Suppose further that n H ≥ D G + 1.
where = log(D G + 1) log(n G D G ) and K is some universal constant.

Proof
Let k = D G + 1. We group the vertices of H into sets such that for any set S and the subgraph of H induced by S, H[S]: (i)|S| ≥ k, (ii)H[S] is connected, (iii) The diameter of H[S] is at most 4k. We do this through the following decomposition algorithm on H: Choose some arbitrary vertex v ∈ V (H) as the root, and using a breadth-first search (BFS) on H, descend from v at most distance k. The resulting tree T (v) ⊆ H will have diameter at most 2k. For each leaf l of T (v), continue the BFS using l as a root. If T (l) has fewer than k vertices, append it to T (v). If not, recurse on the leaves of T (l). The set of vertices of each tree thus formed satisfies the three conditions above. The root is part of a new set, unless it has been appended to another tree.
In the product F we refer to copies of G as columns. In [Refer to section 6.6.1 for a reminder of the notation (. We use the following two-phase approach to bound the cover time of F = G2H.

Phase 1 Perform a random walk W(F ) on F until the blanket-cover criterion
is satisfied for the H dimension. The expected number of movements on F per movement on the H dimension is at most (∆ G + δ H )/δ H . Therefore, Similarly, Using Hence, We have, using (6.22) and (6.23),

Chapter 7 Random Graphs of a Given Degree Sequence
In this chapter we study the asymptotic cover time of random graphs that have a prescribed degree sequence, that is, for a graph with vertex set V = {1, 2, . . . , n} with n → ∞, we have a sequence d = (d 1 , d 2 , . . . , d n ) of positive integers where d i is the degree of vertex i and we wish to determine the cover time of a graph picked uniformly at random from the set of all connected simple graphs of degree sequence d. Denote by G(d) the space of all such graphs with a uniform distribution on them. Thus, we study the cover time of a graph G picked from G(d). We may relax our terminology slightly and say that a graph G is picked uar from the set G(d), even though G(d) is not a set but a set with an associated distribution on the elements.
It must be noted that not every sequence of n positive integers will allow for a simple graph, nor even a graph. We know, for example, for the sequence to be graphical, the sum of the degrees has to be even, i.e., n i=1 d i = 2m for some natural number m. With this condition, a graph having the prescribed sequence may exist, but may not be simple. For example, a 2-vertex graph with degree sequence (1, 3) will force multiple edges and/or loops. Nevertheless, the study of the types of graphs can be facilitated by means of an intimately related random process known as the configuration model, which is explained in section 7.3.1, and is treated in many sources, including, e.g., [49].
We reiterate some definitions: a statement P(n) parameterised on an integer n holds with high probability (whp) if Pr(P(n) is true) → 1 as n → ∞; the notation f (n) ∼ g(n) means f (n)/g(n) → 1 as n → ∞.
Our study of the cover time imposes certain technical restrictions on the degree sequence under consideration in addition to the n i=1 d i = 2m restriction already mentioned. A degree sequence d satisfying these restrictions, which are described in section 7.4, is called nice.
We denote by θ the average vertex degree, i.e., θ = 2m/n, and by d the effective minimum degree. The latter is a fixed positive integer, and the first entry in the ordered degree sequence which occurs Θ(n) times, meaning that for any d < d, there are o(n) vertices with degree d . The significance of the effective minimum degree is discussed in 7. 4. The logarithms are base-e, as they are in the rest of this chapter, unless stated otherwise.
We note that if d ∼ θ, i.e., the graph is pseudo-regular, then which is the same asymptotic limit for random d-regular graphs given in [20].

Random Graphs: Models and Cover Time
The study of random graphs goes back to [34] and [41] and has since become a highly active field of research. Those two models have proved to be a highly fertile ground in which to develop ideas, tools and techniques for the study of random graphs. Despite the fact that these two models were introduced by different groups of authors, both of them have come to be referred to as Erdős-Rényi (E-R) random graphs, after the authors of [34].
Subsequent models attempted to deal with the shortcomings of Erdős-Renyi in accurately capturing the structural properties of "real world" networks. This has been an area where mathematical theory and empirical study have been mutually beneficial to each other; theory has served to deepen understanding of "real-world" networks, and empirical research has generated data that has led to the developments of theory. Section 7. 1

.3 gives examples.
The classical work on random graphs is [12]. Another popular example is [49], but there are many others.
In the next section, we describe some models of random graphs as well as cover time results on them. We start with the two original ones of [34] and [41]. It should be noted, that in all graphs we consider, vertices are labelled, and thus two graphs which may be indistinguishable without labelling, will be different objects with labelling.
Before doing so, we define the term graph space. A graph space G is a set of graphs together with an assignment of probability p(G) to each graph G ∈ G such that G∈G p(G) = 1, i.e. it is a probability distribution. When we say we pick a random graph G ∈ G, we mean we are picking it from the set with probability p(G).

Erdős-Rényi
In the model of [34], the graph space G(n, m) is the set of all graphs with n (labelled) vertices and m edges, together with a uniform distribution on the set. Hence, a graph G is picked uniformly at random from all graphs on n vertices and m edges. In the model of [41], there are n (labelled) vertices and each of the n 2 possible edges exists with some fixed probability p, independently of the others. This graph space, denoted by G(n, p) contains every graph on n vertices, but the distribution on them is not uniform. For a particular graph G on n vertices, if the edge set E(G) is such that |E(G)| = m, then the probability of G being picked from G(n, p) is Note, that whilst these graphs will always be simple, they may not be connected.
Conditions for connectivity were studied with the introduction of the models, and continued to be thereafter, becoming a major area of focus for research on these models.
A cover time result for G(n, p) was given in [51]:

Random Regular
Let r be a positive integer. A random r-regular graph G on n vertices is a graph picked uar from the set of of all r-regular graphs on n vertices. The graph space is denoted by G(n, r).
The cover time for random regular graphs was studied in [20]:

Other Models
The cover time of a particular generative model of the preferential attachment graph is studied in [22]. In this model, at each time step, a new vertex v is added to the graph, and a fixed number m edges are randomly added between v and the existing vertices. The probability of adding to a vertex u is in proportion to the degree of u at that time in the process. The cover time was determined to be asymptotically equal to 2m m−1 n log n, where n is the final number of vertices in the graph.
This model was suggested by [8] as a means of generating graphs with the scalefree property, which is the name given in the same paper to graphs having a power-law degree distribution. This is one in which P (k) ∝ k −γ for some constant γ, where P (k), the fraction of vertices with degree k. Such a property

Mixing Time, Eigenvalues and Conductance
is thought to exist in many "real world" networks, such as the WWW and actor collaboration networks [8], and the Internet [35] 1 .
In a random geometric graph ( [66]), the n vertices are scattered uar on (some subset of) a d-dimensional space where d ≥ 2, and an edge is placed between vertices u and v if the Euclidean distance between them is at most some fixed constant r, often called the radius. This type of random graph for d = 2 has been used as a model of wireless ad-hoc and sensor networks ( [44], [6], [16]) where the radius represents the radio communication range of devices that are placed randomly on the plane. Two recent papers deal with the cover time of random geometric graphs: [27] and [7].

Mixing Time, Eigenvalues and Conductance
In this section we discuss parameters that are related to random walks on graphs. The concepts introduced here play a fundamental role in the proof Theorem 49. In chapter 3, we discussed the convergence of a random walk W on a graph G to a unique stationary distribution π. The formal statement was made in Theorem 10, which in turn was based on Theorem 7 for Markov chains more general than random walks on undirected graphs.
Although these theorems asserted that a walk would converge to a stationary distribution (given certain conditions), there was no mention of how quickly this convergence happens. That is, there was no mention of how close to stationarity was the distribution of the random walk W after some number of steps t, nor how many steps were required to get close to stationarity (for some well-defined 7.2 Mixing Time, Eigenvalues and Conductance meaning of "close"). There are a number of related definitions of "closeness" between one distribution and another, and also a number of related definitions of "quickness" for convergence of distributions, but they are similar enough to one another that they all reflect the fundamental behaviour of a walk on the graph in roughly the same way. The rate of convergence of the walk is called the mixing rate, and the time it takes the walk to get close to stationarity is called the mixing time. A walk is rapidly mixing if the mixing time is somehow small compared to the size of the graph -say, polylogarithmic in the number of vertices. We shall define these notions in precise terms (see, e.g., [57] or [59]), but first we shall introduce the role of eigenvalues in the study of random walks on graphs.

Theory and Application of the Spectra of Random Walks
Recall that for the matrix P of transition probabilities of a random walk on a graph G, the t-step probabilities are given by P t . This suggests that the set of eigenvalues of P -the spectrum -and their associated eigenvectors may have some important role. Indeed, we have already seen one particularly important lefteigenvector, the stationary distribution π: πP = π. Note further that P1 = 1, where 1 is the column vector of n elements with every element 1.
The spectral theory of the transition matrix allows us to prove a convergence in distribution, and as we shall see, also give bounds on how close the distribution at time t is to the limit give some starting distribution p. This is given in terms of a distance between pP t and π, bounded by a function of eigenvalues and t.
We follow the presentation given in [59]. Recall the definition of the adjacency matrix given in section 2. 1. Let A be the adjacency matrix and P be the transition matrix for a connected, simple, undirected and unweighted graph G. Let n = |V (G)|, and without loss of generality, let us assume the vertices of G

Mixing Time, Eigenvalues and Conductance
are labelled 1 to n. Let D be the diagonal n × n matrix such that D i,i = 1/d(i), the degree of vertex i. Observe P = DA.
Although A is symmetric, P will not be unless G is a regular graph. In order to use the powerful tools of Spectral Theory, we require a matrix to be symmetric. We therefore use the related matrix N = D 1/2 AD 1/2 = D −1/2 PD 1/2 , which is, in fact, symmetric.
Since N is real and symmetric, then by Proposition 4 it has the form Thus w is an eigenvector of N with size w = n i=1 d(i) = √ 2m, where m = |E(G)| is the number of edges in G. Since this eigenvector is positive, by the Perron-Frobenius theorem, the eigenvalue associated with it is unique and strictly larger than the second largest eigenvalue. Furthermore, it is at least the absolute size of the smallest eigenvalue (which may be negative). That is, for the eigenvalues λ 1 , λ 2 , . . . , λ n of N, For a proof of the following proposition, see, for example [58].
The following is from [59] (with modifications for consistency of notation).
If G is not bipartite, then |λ k | < 1 for 2 ≤ k ≤ n and so This proves Theorem 10, and moreover, demonstrates how the eigenvalues are related to the speed of convergence of the walk to the stationary distribution.

Conductance
The conductance we refer to in this section and for the rest of this chapter is not the same concept as that used in conjunction with electrical network theory, where it refers to weight of an edge in a network. It will be suitable for our purposes to first state the definition in terms of Markov chains, and then reduce it for random walks on graphs. Definitions are given in e.g., [32], [57] and [59]. where π(S) = x∈S π(x), and S = Ω \ S.
For an unweighted simple graph G = (V, E) with n = |V |, m = |E|, where E(S : S) denotes the number of edges with one end in S and the other in S and d(S) = i∈S d(i). where π(S) = i∈S π(i) = d(S)/2m is the probability of a random walk on G being in S when it is in the stationary distribution.
To glean some intuition behind equation (7.6), observe that in the stationary distribution, each of the 2m total orientations of the edges has the same probability of being transitioned. The quantity E(S : S) counts the number of orientations out of S, and d(S) counts the total number of orientations that start in a vertex of S. Thus E(S : S)/d(S) gives the probability, in the stationary distribution, of moving out of S at a given step given that the walk was in S. Or said in another way, when in the stationary distribution, it is the frequency of moving out of S, divided by the frequency of being in S. Intuitively, therefore, it would appear that a higher conductance might imply more rapid mixing of a random 7.2 Mixing Time, Eigenvalues and Conductance walk. Indeed, this is the case, as can be seen from this important and useful theorem, which was independently proved by [50] and [56]: . Let λ 2 be the second largest eigenvalue of a reversible, aperiodic transition matrix P. Then To be able to use Theorem 53 on a graph G, it needs to be non-bipartite so that it is aperiodic (see section 3.3, Lemma 8). Furthermore, to use it in conjunction with inequality (7.4), we need to make sure that λ * = λ 2 . Both of these problems can be solved if we make the random walk lazy. This means replacing the transition matrix P with L = 1 2 P + 1 2 I, where I is the identity matrix. This introduces a loop probability of 1/2. It means that asymptotically, the cover time becomes precisely twice as large. Introducing this loop probability makes the graph non-bipartite, but moreover, making it have probability (at least) 1/2 ensures that all eigenvalues are non-negative. This is easy to see: If x is an eigenvector of P with eigenvalue λ, then and λ + 1 ≥ 0 since λ ≥ −1 by the Perron-Frobenius theorem (see (7.2)). Furthermore, since x was an arbitrary eigenvector of P, all the eigenvectors of P are eigenvectors of L. This implies P and L have the same eigenvectors v 1 , v 2 , . . . , v n , and the eigenvector v i with eigenvalue λ i under P has eigenvalue Thus, for the lazy walk L, λ 2 ≥ |λ n | and so λ * = λ 2 . Thus, using inequality 7.3 Random Graphs of a Given Degree Sequence: Structural Aspects (7.7) in conjunction with inequality (7.4), we have, for any i, j Our reason for expressing a probability distance bound in terms of conductance is that it is sometimes far easier to bound conductance than the eigenvalues of a graph. This is the case with the graph space we analyse in this chapter. In section 7.3.2, we shall prove that, the conductance of a random graph with given degree sequence is at least 1/100, whp. This will imply that a random walk on such a graph is rapidly mixing whp, and this is crucial to the proof of Theorem 49. The meaning of "rapidly mixing" in this context shall be made precise in due course.

Random Graphs of a Given Degree Sequence:
Structural Aspects 7. 3

.1 The Configuration Model
The configuration model is a random process that has proved useful for studying graphs with prescribed degree sequences. We assume the necessary condition that the sum of the degrees is even, n i=1 d i = 2m and with each vertex i ∈ V , we associate d i half-edges, or stubs, which we consider distinguishable. Starting with an arbitrary stub from amongst the 2m, we choose another stub in the graph uar and pair the two. We repeat this process, taking an arbitrary stub and pairing it with another chosen uar from the remaining 2m − 3. We continue this way until all stubs have been paired. Since there are an even number of stubs in total, the process must terminate successfully. The set of pairings that results is called a configuration. A configuration C maps to a graph G(C) on 7.3 Random Graphs of a Given Degree Sequence: Structural Aspects the same vertex set and with each stub pairing considered to constitute an edge in G(C). Note that there will be multiple configurations mapping to the same graph (i.e., the mapping from configurations to graphs is many-to-one).
In the above process since every other stub was picked at random with no regard for which vertex it was associated with, we may have loops and/or multiple edges in the resulting graph. It is quite clear that because the stubs are distinguishable, each possible configuration has the same probability, with the number of configurations being (If we think of stubs as vertices themselves, we may consider this process as picking a perfect matching on the stubs uniformly at random from all possible matchings). For a degree sequence d, we shall write CM(d) for the configuration space for d. The point of the configuration model is that it tends to be much easier to analyse and prove statements with than a direct analysis of simple random graphs of a given degree sequence. However this is of little use if statements proved in the paradigm of the configuration model cannot be carried over to statements about the graph space of interest. We use the following principle. and suppose that a statement P(d) proved in the configuration model (and thus parameterised on d) is false with some probability at most g(n). If g(n) = o(f (n)), then P(d) holds whp when we condition on the configuration C drawn from CM(d) being simple (and thus mapping to a simple graph).

Random Graphs of a Given Degree Sequence: Structural Aspects
Each simple graph G is mapped to by Π n i=1 (d i )! configurations, but the actual probability of a simple graph -that is, the total probability of the subspace of configurations which map to simple graphs, is difficult to determine precisely. Estimates are given, e.g. in [60], but these require restrictions on the degree sequence. Further details will be given in section 7.4. It should be noted that [32] gives a similar result, demonstrating that there exists a constant that is a lower bound for the conductance. The analysis in turn relies on results from [42].

Conductance: A Constant Lower Bound
Let d = (d 1 , d 2 , ..., d n ) be a sequence of natural numbers and let G = (V, E) be a graph of n vertices chosen uar from the family G(d) of all simple graphs with degree sequence d, i.e., such that d i denotes the degree of vertex i.
We make the following assumptions about the degree sequence: where m is a natural number.

Random Graphs of a Given Degree Sequence: Structural Aspects
We work in the configuration model and make the following further assumption: (iv) d is further restricted in such a way that statements which fail with probability at most n −Ω(1) in the configuration model hold whp when the model is conditioned on mapping to a simple graph (in other words, we can apply Proposition 6).
As per the statement of Theorem 49, in this chapter the cover time is analysed for nice sequences. As will be seen in section 7.4, a nice sequence d has the property that Pr(C ∈ CM(d) is simple) ≥ e −o(log n) , implying that if a statement is demonstrated to fail in the configuration model with probability at most n −Ω(1) , then by Proposition 6, it holds whp when we condition for simple graphs.
The statements in the proof of Theorem 54 do indeed fail with probability at most n −Ω(1) , and so for the purposes of Theorem 49, the proof of Theorem 54 is valid. Nevertheless, some of the conditions of nice sequences are specified for the sake of the analysis of cover time rather than conductance, and so we leave the details to section 7.4 and present a proof for Theorem 54 that depends on the more general assumptions (i)-(iv). Theorem 54. Subject to assumptions (i)-(iv), for a graph G ∈ G(d), Φ(G) > 1/100 whp.
Before we proceed with the proof, we note an immediate corollary: For a set S ⊆ V let d(S) = v∈S d(v) and for a configuration C, let E C (V 1 : V 2 ) denote the number of edges with one end in V 1 and the other in V 2 in C. Let E C (S) = E C (S : S)/d(S). Let π(S) = d(S)/2m.
We work in the configuration model. Our general approach is to show that when 7.3 Random Graphs of a Given Degree Sequence: Structural Aspects a configuration C ∈ CM(d) is picked, the set is empty with probability at least 1 − n −Ω(1) . Having done this, the theorem follows by condition (iv).
Throughout we make use of the following result of Stirling (see, e.g., [39]): .. where βd(S) * is the smallest even integer greater than or equal to βd(S). For notational convenience, we omit the ceiling and * symbols and note that doing so can only incur (small) constant correcting factors that will not affect the results.

H(S)
is an upper bound on the probability that a particular set of vertices S will have E C (S) ≤ 0.01 when C is picked.

Random Graphs of a Given Degree Sequence: Structural Aspects
So where K is a constant.

Small Sets
We bound the part of the sum of (7.12) for small sets, and we partition it into sets of equal size (in the number of vertices). Since d(S) ≤ (θn) 1/4 , |S| = o(n).
where S i is the set of size i for which H(S) is greatest over all sets S over the range of the sum with |S| = i.
Let S with |S | = s and ∂ = d(S ) be the set over the range of the sum for

Random Graphs of a Given Degree Sequence: Structural Aspects
Using (7.17), for large enough n. Hence,

Random Graphs of a Given Degree Sequence: Structural Aspects
Applying Stirling's approximation to n cn we have where K 2 is some constant (which we shall assume absorbs the correcting factors e λn in the Stirling approximation). Hence g(0) = 1 and the function is monotonically decreasing with minimum g(1/2) = 1/2.

Random Graphs of a Given Degree Sequence: Structural Aspects
.

Assumptions About Degree Sequence
We are studying the cover time of a graph G picked uniformly at random uar from the set G(d) of simple graphs with vertex set V = [n] and degree sequence d = (d 1 , d 2 , . . . , d n ). We make the following definitions: Let V j = {i ∈ V : d i =

Assumptions About Degree Sequence
j} and let n j = |V j |. Let n i=1 d i = 2m and let θ = 2m/n be the average degree.
It seems reasonable to ask how the various entries in the degree sequence affect the cover time. In particular, how much does the cover time depend on the vertices of low degree, and how much on the average degree of the graph? In fact, as in [28], both parameters play a part, as is shown in Theorem 49.
(iv) n d = αn ± o(n). We call d the effective minimum degree.
(v) Maximum degree ∆ = O(n κ(d−1)/d ). Immediately on fixing the degree sequence, d, some definitional problems arise, as e.g. there may be just a few low degree vertices spread over a wide range.
To get round this, we define an absolute minimum degree δ, and an effective minimum degree d. The effective minimum degree is the first entry in the sorted degree sequence which occurs order n times. We fix the minimum degree at 3 to ensure the graph is connected (whp). Between the minimum degree, and the effective minimum degree, we place an upper bound on the number n i of vertices of degree i. The bound we choose of n i = O(n κi/d ), is not as arbitrary as it looks. Certainly when κ = d/(d − 1), the effective minimum degree drops below d, so clearly there is some κ < d/(d− 1) which is critical. Finally, we make some constraints on the average degree and upper tail of the degree sequence, to ensure simple graphs occur with high enough probability in the configuration 7.4 Assumptions About Degree Sequence model. Thus we are left with the above list of conditions.
We call a degree sequence d which satisfies conditions (i)-(vi) nice, and apply the same adjective to G ∈ G(d).
Examples of nice sequences/graphs are: Any r-regular graph (where r is constant); The sequence which has at most n 1/20 vertices with degree at most n 1/20 , and the rest are (constant) degree d. This will have average degree θ = (1 + o(1))d, but possibly high maximum degree; The sequence which has Θ(n 1/20 ) vertices with degree Θ(n 1/20 ), and the rest are equally divided between (constant) degree d and degree Θ( √ log n/ log log n). This will have a high average degree Θ( √ log n/ log log n) as well as a large number of high degree vertices.
Recall from section 7.3.1 we discussed the set of all configurations with degree sequence d and with uniform probability, known as the configuration space That section discussed the probability of a configuration C ∈ CM(d) being simple. It was stated that each simple graph G with degree sequence d had Π n i=1 (d i )! configurations mapping to it, thus, conditioning on simplicity, the distribution across simple graphs was uniform. However, the actual probability of simplicity was not elaborated on. A result of [60] gives asymptotic values of the probability of simplicity, but requires certain constraints on d.
Let ν = i d i (d i − 1)/(2m). Assume that ∆ = o(m 1/3 ) (as it will be for nice sequences). The probability that C ∈ CM(d) maps to a simple graph is given by Observe that our assumptions (i)-(vi) that d is nice imply that ν = o( √ log n).

Estimating First Visit Probabilities
All the whp statements in the analysis below of the structure of random graphs fail with probability at most g(n) = n −Ω(1) , whereas Pr(C simple) in (7.22) is at least f (n) = e −o(log n) . By Proposition 6, this justifies our use of CM(d) to make statements about G(d).

Convergence of the Random Walk
In this section G denotes a fixed connected graph with n vertices and m edges.
A random walk W u is started from a vertex u. Let W u (t) be the vertex reached at step t and let P (t) We assume that the random walk W u on G is ergodic i.e. G is not bipartite. Thus, the random walk W u has the steady state distribution π, where π v = d(v)/(2m). Here d(v) is the degree of vertex v.
Note P
It follows from e.g. Aldous and Fill [4] that D(s + t) ≤ 2D(s)D(t) and so for 7.5 Estimating First Visit Probabilities Next, considering the walk W v , starting at v, let r t = Pr(W v (t) = v) be the probability that this walk returns to v at step t = 0, 1, .. for some sufficiently large constant K.
The following lemma should be viewed in the context that G is an n vertex graph which is part of a sequence of graphs with n growing to infinity. An almost identical lemma was first proved in [20].

There exists
where R T (1) is from (7.27), such that for all t ≥ T , We have the following corollary

Proof
We use Lemma 56 and and note that T 2 π v = o(1). 2 Rather than reproduce the proof of Lemma 56, we instead present a simplified version which conveys some of the core ideas behind it in a more straightforward form. This simplified version gives a bound rather than a bound on Pr(A t (v)) rather than the precise value given in Corollary 57.
NB We use may use R v to denote R T (1), to emphasis the dependence of R T (1) upon v.

First Visit Lemma: Simplification
For the graph G = (V, E) let n = |V | and m = |E|.
Visits to Single Vertices.
Recall from section 2.2 the definition of H[p, a] for a distribution p over states of a Markov chain: The hitting time from the stationary distribution, see e.g. [4].

Estimating First Visit Probabilities
Let P denote the transition matrix for a random walk on G, and, for a walk W v starting from v define Thus R v is the expected number of returns made by W v to v during T steps, in the graph G. We note that R v ≥ 1, as P In subsequent discussions, we will assume T is a mixing time satisfying for any vertices u and As π x ≥ 1/n 2 for any vertex of a simple graph, (7.33) Lemma 58. Let T be a mixing time of a random walk W u on G satisfying (7.33). Let vertex v ∈ V be such that T · π v = o(1), and π v < 1/2, then u (x) − π x |. It follows from e.g. [4] that D(s + t) ≤ 2D(s)D(t). Hence, since max u,x |P (1)). (7.36)

Estimating First Visit Probabilities
The last inequality follows because R v (T ) ≥ 1. Let A t (v) denote the event that W u does not visit v in steps 0, ..., t. We next derive a crude upper bound for Pr(A t (v)) in terms of H[π, v].

Proof
Let ρ = ρ(G, T, u) be the distribution of W u on G after T , then Indeed, Let h ρ (v) be the time to hit v starting from ρ. Then E[h ρ (v)] = H[ρ, v] so by Markov's inequality and using (7.37), By restarting the process at

Estimating First Visit Probabilities
2

Visits to Vertex Sets
We extend the results presented above to a subset of vertices. Let ∅ = S ⊆ V .
From graph G we obtain a (multi)-graph Γ = Γ S by contracting S to a single vertex γ. Note that we retain multiple edges and loops in Γ S , so that d(S) = d(γ) and that m = |E(G)| = |E(Γ)|. Letπ be the stationary distribution of a random walk on Γ. If v ∈ S then π v =π v and also that π S =π γ .
Any walk W v from v ∈ S to S in G with internal vertices not in S corresponds to an identical walkŴ v from v to γ in G S , and both walks have exactly the same probability. Thus we obtain LetP denote the transition matrix for a random walk on Γ S , let T Γ denote the mixing time for Γ S , and define γ (γ). (7.39) Note that R γ is the number of returns to γ in the contracted graph Γ S , rather than a somewhat different notion of the number of returns to S in G. Note also that in the summation in (7.39) we use T Γ , the mixing time in Γ, rather than the mixing time in G.
For any vertices u and x in Γ, we will assume We will always choose mixing times T satisfying T ≥ T G , and T ≥ T Γ . Because We also note that provided T Γπγ = o(1) then Lemma 58 and Lemma 59 both apply to γ in Γ.

Required Graph Properties
Let ω = log log log n (7.41) We use this value throughout our proof.

Mixing Time
We shall define the mixing time to be the smallest T such that (7.23) is satisfied.
From inequality (7.8) we have As explained in section 7.2.2, we require the walk to be lazy, meaning it only makes a move to a neighbour with probability 1/2 at any step. This halves the conductance but if Φ(G) > 1/100 (which will be the case whp, by Theorem 54) we can still set T = ω 3 log n ( 7.43) to satisfy (7.23). The cover time is doubled. Asymptotically the values R v are 7.6 Required Graph Properties doubled too. Otherwise, it has a negligible effect on the analysis and we will ignore this for the rest of the chapter and continue as though there are no lazy steps.
Note that ∆ = O(n c ) for some constant c < 1 implies T 2 π v = o(1) for any vertex v.

Some definitions
We show some properties held by almost all graphs in G(d). First we define some terms: Let = B log 2 n (7.44) for some large constant B.
(i) A vertex v is light if it has degree at most , otherwise it is heavy.
(ii) A cycle C or path P is small if it has at most 2ω + 1 vertices, otherwise it is large.
(iii) A small path is light if all of it's vertices are light, otherwise it is heavy.
(iv) A small cycle is light if it has at most one vertex that is heavy, otherwise it is heavy.

Every other vertex in
T v has degree r in T v (where it may be the case that r = d v ).

The local graph Γ v
For a light vertex v, define the graph Γ v as follows: Γ v is then taken to be the connected component of v in G v after this process has completed. We denote by Γ • v the union of the set of (heavy) vertices that have been pruned and the vertices distance ω from the root v (when v is heavy, we do not need to consider this process, as shall be seen in section 7.9.1).

Structural Properties
Lemma 60. With high probability,

Proof
Before we prove the lemma, we show a useful inequality. For integer The expected number of light cycle-path-cycle (c-p-c) subgraphs µ has the following upper bound: Explanation This is an upper bound on the number of configurations with a light c-p-c, divided by the total number of configurations. We choose a vertices for one cycle, b vertices for the other and c vertices for the path. We multiply by the number of ways of permuting vertices in the two cycles and the path. Every vertex but at most one in a cycle is light, hence has at most degree .
If there is a heavy vertex, it can have any degree up to ∆. Hence, each light vertex has up to ( − 1) ways to connect to a neighbour. We therefore multiply 2 by itself ((a − 1) + (b − 1) + c) times for the number of ways to connect to a neighbour for the two cycles and the path. The remaining (unaccounted for), possibly heavy vertex in each cycle can connect in up to ∆(∆ − 1) ways to a neighbour in the cycle and ∆ − 2 ways to a vertex on the path, hence ∆ 6 serves 7.6 Required Graph Properties as an upper bound. Since a c-p-c subgraph connects 2(a + b + c + 1) ports, the number of ways of connecting the remaining free ports in the configuration is counted by the function F(θn − 2(a + b + c + 1)).
Thus, (7.45) is bounded by Thus, (7.46) is bounded by Thus as in part (a), we have Pr(µ > 0) = o(n − ), for some constant > 0. 2 Corollary 61. With high probability, Γ v is either a tree or contains a unique cycle.

Proof
Clearly, if v is locally tree-like, then Γ v will be a tree. If G v consists entirely of light vertices, then it can't have more than one cycle, since all cycles would be light and any two cycles would either intersect or be connected by a light path. By the lemma, whp no such pair of light cycles exist, and so Γ v will contain a unique cycle. If G v contains a heavy vertex h that has two light paths to the root v, then h is part of a light cycle. No other heavy vertex h can have more than one light path to v as h will also be part of a light cycle, and by the 7.6 Required Graph Properties lemma, whp no such pair of light cycles exists. Therefore, any light cycle in G v will be unique (any other cycle will be heavy). Furthermore, there will be no more than two light paths from h because of h has at least three light paths to v, those three light paths would form an intersecting pair of cycles, which by the lemma, is forbidden whp. We see, therefore, that every heavy vertex in G v has one neighbour on a light path to v, with the exception of at most one heavy vertex, which can have two neighbours with such a property. Since the pruning process deletes edges to neighbours of a heavy vertex that do not have a light path to the root, a pruned (heavy) vertex will have at most degree 1 in Γ v , with at most one vertex (h), having degree 2 (and being part of a unique light cycle). The tree created by process P involves Let σ represent the sum of degrees of vertices of degree less than d. Thus

Required Graph Properties
Let X count the number of vertices v that are not d-compliant. Using the for real c = 1. Hence under the assumption n i = O(n κi/d ), we find that (7.47) gives σ = O(n κ(d−1)/d ).

Proof
We consider d-regular vertices that have a root vertex v of degree d.
A d-regular tree of depth ω contains N 2 vertices. We proceed in a similar manner to Lemma 62, and bound the probability P that a vertex v is d-regular by bounding the probability of success of the construction of a d-regular tree in the configuration model. We have (7.49) and For any vertex v, the number of vertices u such that G v ∩ G w = ∅ is bounded from above by N 2 + dN 2 2 . Using this and (7.50), we can bound (7.49) from above 7.7 Expected Number of Returns in the Mixing Time by µ + µ 2 + µ(N 2 + dN 2 2 ).
By the Chebychev Inequality, for some constant 0 <˜ < 1, for some constant .
The lemma now follows from (7.48). The following is an immediate consequence of Definition 20 and the previously proved theorems and lemmas: As we shall see, G being good allows us to use Lemma 56, and, in particular, Corollary 57. That is, when G is good, the conditions of the lemma hold (to be demonstrated in section 7.8), and we have the tools to calculate the relevant quantities, in particular, (a bound on) the mixing time T (see section 7.6.1), and R v , the expected number of returns in the mixing time to a vertex v. The latter quantity is calculated in the next section.

Time
In this section we calculate bounds for the expected number of returns R v to a vertex v within the mixing time T . First we require the following lemma.

Expected Number of Returns in the Mixing Time
There exists a constant ζ ∈ (0, 1) such that Case t ≤ ω. When a particle starting from v lands at some vertex u ∈ Γ • v , this is either at at distance ω, or u is a heavy vertex at distance less than ω from v. In the case of u being heavy, by the light cycle condition, there are at most two light paths back to v from u of length at most ω. All other paths of length at most ω go via other heavy vertices. Hence if a particle is at u, with probability at most 2/ it will enter a light path to v. Thus the probability of reaching v in time ω after having landed on a heavy vertex of Γ • v is at most O(ω/ ) = o(ζ ω ).
In the alternative case that u is at distance ω from v, then for t < ω, r * t = r t . Thus we can write ω t=0 r t − r * t = o(ζ ω ). (7.52) Case Assume first that Γ v is a tree. We estimate an upper bound for σ t as follows: Consider an unbiased random walk X Now for any t and b with |b| < a, we have which is justified with the following game: We have two walks, A and B coupled to each other, with A starting at position 0 and B at position b, which, w.l.o.g, we shall assume is positive. The walk is a simple random walk which comes to a halt when either of the walks hits an absorbing state (that being, −a or a). Since they are coupled, B will win iff they drift (a − b) to the right from 0 and A will win iff they drift −a to the left from 0. Therefore, given the symmetry of the walk, B has a higher chance of winning. Thus Pr(|X since after t steps, the worst case position for the walk to be at is the origin, 0. Consequently, for any b with |b| < a,

Expected Number of Returns in the Mixing Time
Hence, for t > 0, We now turn to the case where Γ v contains a unique cycle C. The place where we have used the fact that Γ v is a tree is in (7.55) which relies on (7.54). Let x be the furthest vertex of C from v in Γ v . This is the only possible place where the random walk is more likely to get closer to v at the next step. We can see this by considering the breadth first construction of Γ v . Thus we can compare our walk with random walk on [−a, a] where there is a unique value x < a such that only at ±x is the walk more likely to move towards the origin and even then this probability is at most 2/3.

Since we have
We now consider the probability the particle walks from e.g. x to a without returning to the cycle: There is 1/3 chance of moving away from the origin (towards a). Now from standard results, an unbiased random walk in one dimension between x and a starting at position x + 1 would have probability 1/(a − x) of hitting a before hitting x. Since the actual walk will be biased in favour of movement toward a, a probability of 1/3(a − x) serves as a lower bound on the probability of going from x to a without returning to x. Thus Pr(∃τ ≤ ca 2 : |X

Expected Number of Returns in the Mixing Time
and for some constant ζ ∈ (0, 1).

Proof
We use Lemma 64.
(a) We calculate R * v for a walk W * v on an r-regular tree Γ v with Γ • v made into absorbing states. For a biased random walk on (0, 1, ..., k), starting at vertex 1, with absorbing states 0, k, and with transition probabilities at vertices (1, . . . , k− 1) of q = Pr(move left), p = Pr(move right); then This is the escape probability ρ -the probability that after the particle moves from v to an adjacent vertex, it reaches an absorbing state without having visited v again. R * v = 1 + 1/ρ − 1 = 1/ρ.

Expected Number of Returns in the Mixing Time
We project W * v onto (0, 1, . . . , ω) with p = d−1 d and q = 1 d giving and part (a) of the lemma follows.
Treating the edges as having unit resistance, this pruning process cannot decrease the effective resistance between v and a hypothetical vertex ζ that is connected by a zero-resistance edge to each of the vertices in Γ • v (and no others). Then by part (a) and Rayleigh's monotonicity law part (b) of the lemma follows. (Here we are using the the fact that the probability of reaching ζ before returning to v is equal to 1 d(v)R where R is the effective resistance between v and ζ. Rayleigh's Law states that deleting edges increases R).
(c) Using ( 7.42) and the fact that T π v = o(1), we have T t=0 r t ≤ T t=0 (π v + O(ζ t )) = O(1), quickly demonstrating that R v is bounded from above by a constant. To get the tighter bound, we observe that for any locally tree-like vertex v, R v ≤ δ−1 δ−2 +O(ζ ω ) by part (a). If there is a cycle (which will be unique) Γ v will be tree-like up to some distance L − 1 < ω and non-tree-like at level (distance) L, then there will be one vertex v c on the cycle at level L if the cycle is an even size, and two vertices v c , w c if it is an odd size. The subtree up to level L − 1 will be δ-tree-compliant, and so if the particle does reach u c ∈ {v c , w c }, it will halt if u c is an absorbing vertex and move one level down (i.e., further away from the root) with probability at least (δ − 2)/δ if u c is not an absorbing state. If it is an even cycle, it will move up the tree (i.e., closer to the root) back to level L − 1 with probability at most 2/δ, and if it is an odd cycle, it will move up with probability at most 1/δ and stay at the same level (moving to the other vertex in {v c , w c }) with probability at most 1/δ. Levels below L (should they 7.7 Expected Number of Returns in the Mixing Time exist) continue to be tree like and so maintain the probability distribution of going down with probability at least (δ − 1)/δ and going up with probability at most 1/δ.
Given that there exists a unique cycle in Γ v , R * v can be no larger than that for the case where Γ v is such that all non-leaf vertices have degree δ and the absorbing states Γ • v are all at distance ω from the root. The only other variable is the location of the cycle.
We shall resort again to electrical network theory to bound R * v . We assign a unit flow to Γ v with the root vertex v as the source and a hypothetical sink vertex that is connected by a zero-resistance edge to each of the vertices in Γ • v (and no others). We treat each edge in Γ v as having unit resistance. When Γ v is a r-regular tree (apart from leaves), we split the flow coming into a vertex evenly across the r − 1 neighbours down the next level. Denote this energy by P T (r). Note P T (r) > P T (s) for r < s. To calculate bounds for the minimal energy when Γ v contains a cycle, we assign the same flow as for a tree, except at the cycle. Consider first an even-sized cycle. There will be two sources of flow into v c (defined above), and by symmetry, these will be equal -call them f . If δ = 3, these flows combine at v c to become a 2f flow going through one edge, then split off into two flows size f at the next vertex. The flow assignment at subsequent vertices is as per usual, with an even split at each vertex. If δ > 3, then from v c , we assign a flow of f to each of two edges into the next level down and then continue as normal. For δ = 3 the energy P Γv of the system is bound by P T (δ) + (2f ) 2 + 2f 2 = P T (δ) + 6f 2 and for δ > 3 the energy is bounded by P T (δ)+2f 2 and since f ≤ 1 (δ−1)δ , we have a bound of P T (δ)+ 6 (δ−1) 2 δ 2 .
For the case where the cycle is odd size, we assign the flows on the same basis as a tree (as in the case of the even cycle) except that the flow f which comes into 7.8 Lemma Conditions each of vertices {v c , w c } will be directed from each vertex through a single edge going to the next level down. Thus for all δ ≥ 3, P Γv ≤ P T (δ) + 2f 2 , and since f ≤ 1/δ we have P Γv ≤ P T (δ)+2/δ 2 . We bound P T (δ) by calculating the effective resistance of an infinite δ-regular tree: This is an upper bound on the effective resistance between the root vertex and a hypothetical vertex connected to each vertex in Γ • v . The escape probability ρ of a walk starting at the root is related as ρ = Res(v)/P Γv where Res(v) is the parallel resistance of the edges incident with v (or alternatively, the reciprocal of the sum of conductances of the edges incident with v). This is which is monotonically decreasing and for δ = 3 is 8/3.

Lemma Conditions
We address the conditions of Lemma 56. For condition (b), we note that n < m < n 2 implies the condition T π v = Ω(n −2 ) holds since T is larger than constant and T 2 π v = o(1) holds since T 2 = (ω 3 log n) 2 = o(n c ) for any positive constant c, and π v = O(n −c ) for some positive constant c. It remains to show condition (a) holds: Lemma 66. Assume G is good. For |z| ≤ 1 + λ, there exists a constant ψ > 0 such that |R T (z)| ≥ ψ.

Proof
As before, let Γ • v be the set of absorbing states of Γ v . We consider a walk in Γ v that starts at v, and each time it leaves v it is terminated if it doesn't return to it within time T . It is also terminated if it reaches an absorbing state (states in Γ • v ) at any time. Let β(z) = T t=1 β t z t where β t is the probability of a first return to v at time t ≤ T . Let α(z) = 1/(1 − β(z)), and write α(z) = ∞ t=0 α t z t , so that α t is the probability that the walk is at v at time t. Note that α t is not quite the same as r * t in Lemma 65, which would be generated 7.8 Lemma Conditions where b * t represents the probability of a first return of W * v at time t. Observe that α t ≤ r * t ≤ r t . We shall prove below that the radius of convergence of α(z) is at least 1+Ω(1/ω 2 ).
Turning our attention first to Q 1 (z), the following results hold both for Γ v a tree, and Γ v containing a cycle.
Now using part of the proof of lemma 65, we see that T We now turn our attention to Q 2 (z). As in lemma 65, let σ t be the probability that a walk on Γ v (with Γ • v absorbing states) starting at v has not been absorbed at step t. Then σ t ≥ α t , so If G v is a tree we can use (7.55) to see that the radius of convergence of Q 2 (z) is at least e 1/(3ca 2 ) . As a ≤ ω, e 1/(3ca 2 ) 1 + 2λ and for |z| ≤ 1 + 2λ, This lower bounds the radius of convergence of α(z), proves (7.61) and then (7.63), (7.61) and (7.62) complete the proof of the case where Γ v is a tree.

Cover Times
In the case that G v contains a unique cycle, we can use (7.57) to see that the radius of convergence of Q 2 (z) is at least 1 + 1 25cω 3 > 1 + 2λ, assuming that K (defined in (7.28)) is sufficiently large. Finally, if z ∈ C λ then

Cover Times
We now prove the main theorem of the chapter, Theorem 49, which we restate here, Theorem 49 (restated) Let G be chosen uar from G(d), where d is nice. Then whp,

64)
where d is the effective minimum degree and θ is the average degree.
In the following, we assume G is good.

Upper Bound on Cover Time
As per the definition in section 2.3, c u is the time taken by the random walk W u starting from vertex u to visit every vertex of a connected graph G. Let U t be the number of vertices of G which have not been visited by W u by step t. We 7.9 Cover Times note the following: Pr(c u ≥ t), Recall from (7.30) that A s (v) is the event that vertex v has not been visited by time s. It follows from (7.65), (7.66) that Pr(A s (v)).  (1) is sufficiently large that all inequalities claimed below hold. We assume that the high probability claims of Sections 7.4, 7.7 hold.
Recall from (7.29) that p v = (1 + O(T π v ))d v /(θnR v ) and that Corollary 57 gives the probability that W u has not visited v during [T, t] as We consider the following subsets of V :

Cover Times
.

Cover Times
Case (iv): < d v Clearly, R v ≤ T = w 3 log n thus, for vertices v ∈ V D (7.68) is bounded by n −Θ(log n/ω 3 ) . Hence In each of the cases above, the term v s≥t Pr(A s (v)) = o(t 1 ) and thus, from

Lower Bound on Cover Time
Let t 2 = (1 − )t 0 , were = o(1) is sufficiently large that all inequalities claimed below hold. For vertex u of degree d, we exhibit a set of vertices S such that at time t 2 the probability the set S is covered by the walk W u tends to zero. Hence c u > t 2 , whp which implies that COV[G] ≥ t 0 − o(t 0 ).
We construct S as follows. Let S d be the set of d-regular vertices of degree d.
Lemma 63 tells us that |S d | = n 1−o(1) . Let S be a maximal subset of S d such that the distance between any two elements of S is least ω. Thus |S| = Ω(n 1−o(1) /d ω ).
Let S(t) denote the subset of S which has not been visited by W u after step t.
Let v ∈ S, then (The above is justified because (1+x) y = e y log(1+x) = e y(x− x 2 for real x, y with |x| < 1).
We apply Lemma 56 to G. That π Z = 2d θn is clear. Furthermore, the vertex Z is tree-like up to distance ω in G. The derivation of R Z as in Lemma 65(a) is valid. The fact that the root vertex of the corresponding infinite tree has degree 2d does not affect the calculation of R * Z .

Cover Times
Thus Equation (7.72) follows because there is a natural measure-preserving mapping from the set of walks in G which start at u and do not visit v or w, to the corresponding set of walks in G which do not visit Z.
We have shown that

Chapter 8 Weighted Random Walks
Chapters 6 and 7 studied random walks on different graph structures, but in both cases the walks were simple, meaning that each step an edge is chosen uar from the edges incident on the current vertex, and the walk transitions that edge. However, we may also define random walks on graphs G = (V, E, c) with differently-weighted edges, where an edge e = (u, v) has some non-negative weight, or conductance, c(e), and the probability of transitioning e from u is given by c(e)/c(u) where c(u) = e=(u,v)∈E c(e). Simple random walks are a special case where c is a constant function. Chapters 2, 3 and 4 discuss the details, and we refer the reader there. We shall call random walks on weighted graphs weighted random walks.
In this chapter, to avoid confusion between conductance c(e) of an edge, and conductance Φ(M) of a Markov chain M as defined in Definition 19, we instead refer to edge conductance as weight and use w rather than c. We will still use resistance r(e) and effective resistance R(u, v) as there is no ambiguity.
As with chapters 6 and 7, we deal only with simple, connected, undirected graphs. 8 [47] and [48]. The investigation is framed as follows. For a graph G let P(G) denote the set of all transition probability matrices for G, that is, stochastic matrices (i.e., non-negative entries with each row summing to 1), that respect the graph structure. The latter means that P u,v = 0 if (u, v) / ∈ E(G). For P ∈ P(G) let H G (P ) denote the maximum hitting time in G with transition matrix P , and C G (P ) similarly for cover time. Let H G (P ) and C G = inf P ∈P(G) Note that if for a graph G one knows a spanning tree T G , a transition matrix P can be constructed that is a simple random walk on T G , and ignores all other edges of G. As per section 5.2 (2) What is the minimum local topological information on G that is always sufficient to construct a transition matrix that achieves each of H(n) and C(n)?
In [48], it is shown that for a path graph P n , any transition matrix will have Ω(n 2 ) maximum hitting time (and therefore, cover time). This, in conjunction with the spanning tree argument, implies Θ(n 2 ) for both H(n) and C(n).
The second question is addressed with a particular weighting scheme that gives O(n 2 ) maximum hitting time for any graph. Note, Matthews' upper bound technique (see section 5.2.3) applies to weighted walks as well, implying a O(n 2 log n) bound on cover time. The weighting scheme, which we call the Ikeda scheme is as follows: where d(v) is the degree of v and N (v) is the neighbour set of v.
A note on application In the algorithmic context of graph exploration, simple random walks are generally considered to have the benefit of not requiring information beyond what is needed to choose the next edge uar. Generally, this implies that a token making the walk can be assumed to know the degree of the vertex it is currently on, but no more information about the structure of the graph. In the Ikeda scheme, information required in addition to the vertex degree, is the degrees of neighbouring vertices. Other local information -such as connectivity, is not required.

Minimum Degree Weighting Scheme
We present an alternative weighting to the Ikeda scheme: Simply, for G = (V, E), assign each edge (u, v) weight w(u, v) = 1/ min{d(u), d(v)} (equivalently, each edge is assigned resistance r(u, v) = min{d(u), d(v)}). This weighting scheme defines the transition matrix of a weighted random walk. We may, as a matter of convenience, say that w(u, v) = 0 if (u, v) / ∈ E in calculations of transition probabilities.
We call this scheme the minimum degree (or min-deg) scheme. It places no greater information requirement in applications than the Ikeda scheme; it also only uses limited, local knowledge. In fact, it is easily checked that equation (8.1) is equivalent to weighting the edges w(u, v) = 1/ d(u)d(v).
We have the following (in)equalities.

Minimum Degree Weighting Scheme
From equation (2.5) (and noting that we are using w to stand in for c), so summing over all edges and using ( 8.2), w(u, v) = 2w(G) (8.7) Then using (8.6) in the middle part of (8.7), n ≤ w(G) ≤ 2n. (8.8) Thus, the min-deg weighting scheme has the following transition probabilities:

Hitting Time
The proof of O(n 2 ) hitting time in [48] applies the following, generally useful lemma.  where d(x) is the degree of vertex x and n = |V (G)|.

Minimum Degree Weighting Scheme
Proof For any 0 ≤ i < i + 2 < j ≤ , it is the case that (x i , x j ) / ∈ E(G) and N (x i ) ∩ N (x j ) = ∅. If not, then there would be a shorter path. Therefore, each vertex in G can be connected to at most 3 vertices on ρ, and the lemma follows. 2 We have the following R(x i , x i+1 ) ( 8.12) where R(x, y) is the effective resistance between vertices x and y and (8.12) follows (8.12) by Theorem 22.

Now
R(x, y) ≤ r(x, y) = min{d(x), d(y)} and so where the last inequality follows by Lemma 67.
By (8.8) we have w(G) ≤ 2n, and the theorem follows. [48] does not use electrical network theory; the proof that the Ikeda weighting scheme results in an O(n 2 ) upper bound on hitting time is different. Furthermore, [48] conjectures that this weighting scheme in fact gives an O(n 2 ) upper bound on cover time. We do the same for our weighting scheme: The minimum degree weighting scheme has O(n 2 ) cover time on all graphs G.
To our knowledge, no weighting scheme has been shown to meet an O(n 2 ) on all graphs G (where, as stated in the introduction to the chapter, G is assumed to be simple, connected and undirected).

Random Graphs of a Given Degree Sequence
In chapter 7 we determined the following theorem: Theorem 49 (restated) Let G be chosen uar from G(d), where d is nice. Then whp, 13) where d is the effective minimum degree and θ is the average degree.
Recall ω = log log log n as defined in equation (7.41). In this section we prove the following:   4 . Weight the edges of G with the min-deg weighting scheme, that is, for an edge (u, v), assign it weight w(u, v) = 1/ min{d(u), d(v)}.
Note that the degree sequence assumptions of section 7.4 allow for the ratio θ/d to be unbounded. Hence, the ratio of the min-deg cover time to the simple cover time, that is, the speed up, can be unbounded.
Our approach in this section is similar to that in the chapter 7, and we borrow heavily from there. We sometimes use d v for d(v).

Conductance
We restate the definition of conductance from section 7.2.2: Q(u, v) = π(u)P u,v , and for a set S ⊂ V , π(S) = u∈S π(u), S = V \S and Q(S, S ) = u∈S,v∈S Q(u, v).
We show

Random Graphs of a Given Degree Sequence
Proof Section 7.6.1, equation (7.42) restated: where K is a constant.

The Number of Returns in the Mixing Time
Recall the definitions in section 7.6.2 and the results in section 7. 7. We first require a version of Lemma 64 for weighted Γ v . We only require the case that it has no cycles.
Lemma 75. Assume G w is good. Let W * v denote the walk on Γ v (weighted) starting at v with Γ • v made into absorbing states. Assume further that there are no cycles in Γ • v . Let R * v = ∞ t=0 r * t where r * t is the probability that W * v is at vertex

Random Graphs of a Given Degree Sequence
v at time t.

Proof
We use the proof of Lemma 64 to prove equation (7.51), reproduced here Firstly, observe that since Γ • v has no cycles and no heavy vertices (by the restriction on ∆), it is a tree with leaves at distance ω.

Random Graphs of a Given Degree Sequence
Proof (a) Suppose u is locally tree-like, but not necessarily regular. Let G(u) be the locally (i.e., out to distance ω = log log log n) induced subgraph of G w and let v ∈ G(v). Let p be the probability of movement away from u and q the probability toward it. Observe the weighting scheme gives This ratio is the same as an unweighted walk on a δ-regular vertex u. Therefore, using Lemma 75 and by the same principles as Lemma 65 (b) Since any cycle in Γ • v is unique, at most two of the edges, (u, v 1 ), (u, v 2 ) out of u lead to vertices on a cycle. Let bad be the event event of moving from u to some v ∈ {v 1 , v 2 } Then Pr(bad) ≤ 2/δ 2/δ + (d u − 2)(1/d u ) = 2/δ 2/δ + 1 − 2/d u ≤ 2/δ.

The Number of Vertices not Locally Tree-like
We wish to bound the number of vertices v that are not locally tree-like, i.e., for which Γ v has a cycle. We use the following from the proof of Lemma 60 of section 7.6.2: F(2x) = (2x)! 2 x x! , then 8.3 Random Graphs of a Given Degree Sequence F(θn − 2x) F(θn) ≤ 1 θn − 2x x Lemma 77. With probability at least 1 − n −Ω(1) , the number of vertices not locally tree-like is at most n 1/10 .

The Probability a Vertex is Unvisited
We use the same principles as in section 7.9. 1. Restating (7.67), Pr(A s (v)). (8.21) We use Lemmas 58 and 59, which hold for weighted random walks (see chapter 2, General Markov Chains, in [4] for justification of (7.31) and the inequality D(s + t) ≤ 2D(s)D(t). All other expressions in the proofs hold for weighted 8

.3 Random Graphs of a Given Degree Sequence
If v is locally tree-like, then using Theorem 76 (a), the RHS of ( 8.22) is bounded by = Ω(θ), Therefore S → ∞ as n → ∞ if θ → ∞ as n → ∞. That is, we can have an unbounded speed up.
We conjecture that the following tighter bound holds:

Main Results
In particular, we have proved the following theorems 1 .
For the first case, we showed in chapter 6:

COV[H]D G
where M = |E F | = n G m H + n H m G , = log(D G + 1) log(n G D G ) and K is some universal constant.
(We remind the reader that in the above, for a graph Γ, n Γ = |V (Γ)|, m Γ = |E(Γ)|, D Γ is the diameter of Γ, and δ Γ and ∆ Γ are the minimum and maximum degrees respectively).
For the second case, we showed in chapter 7: Theorem 49 Let G be chosen uar from G(d), where d is nice. Then whp, where d is the effective minimum degree and θ is the average degree.
Theorem 39 answers the question within bounds, whilst Theorem 49 gives a precise asymptotic value. We reiterate some definitions: a statement P(n) parameterised on an integer n holds with high probability (whp) if Pr(P(n) is true) → 1 as n → ∞; the notation f (n) ∼ g(n) means f (n)/g(n) → 1 as n → ∞.

Main Results
The third case was addressed in chapter 8. Each edge e is given a non-negative weight w(e), and the probability of transitioning e from vertex u is w(e)/w(u) where w(u) = e=(u,v)∈E w(e). We presented a simple weighting scheme, the minimum degree (min-deg) weighting scheme, where each edge e = (u, v) has w(e) = 1/ min{d(u), d(v)}. That is, the transition probability matrix was We proved the following theorem for general graphs (G is assumed to be simple, connected and undirected): We then studied this weighted walk on the specific class of graphs that is the subject of Theorem 49, applying the min-deg weighting scheme to G ∈ G(d).
We presented the following theorem:  where δ is the minimum degree.
We have, by the above, extended the body of knowledge on random walks on graphs, in particular, the cover time of random walks on graphs.

Secondary Results
Additionally, in the course of proving the above theorems, we have presented a number of results which may be of independent interest. Specifically, we have given results related to effective resistance of the Cartesian product of two graphs, a frame work for analysing walks on a graph by analysing "local observations" of the walk, and structural results for G ∈ G(d).
The following lemmas were proved in chapter 6: Lemma 47 For a graph G and tree T , R max (G2T ) < 4R max (G2P r ) where |V (T )| ≤ r ≤ 2|V (T )| and P r is the path on r vertices.
(We remind the reader that R max (G) is the maximum effective resistance between a pair of vertices in a graph G).
In chapter 6, to prove the Theorem 39, we presented a framework to bound the cover time of a random walk W(G) on a graph G by dividing the graph up into regions -sets of vertices S ⊆ V (G) -and analysing the behaviour of the walk whilst on those regions. It does so by relating W(G) whilst walking on S to a random walk W(H) on H, where H is weighted graph derived from (G, S). The analysis of the W(H) walks can then be composed over the whole graph. Thus the analysis of the whole graph is reduced to the analysis of outcomes on local regions and subsequent compositions of those outcomes. This framework can be applied more generally than Cartesian products. The details are presented in section 6. 7.
In chapter 7, we presented the following result on the conductance of a graph G ∈ G(d): Theorem 54 Subject to assumptions (i)-(iv) listed in section 7.3.2, for a graph

Future Work
The B-C model is a n-cycle with a random matching. In the W-S model, the graph begins as an n cycle with each vertex v connected to k others; the k/2 nearest neigbours on each side. Labelling the vertices round the cycle (0, 1, . . . , n−1), for each vertex i in turn, "rewire" each edge (i, j), i < j to (i, k) where k is chosen uar from amongst the vertices that would avoid loops or parallel edges.
As we envisage it, the crux of a proof, as in chapter 7, would be the application of Lemma 56. This would require verification that the conditions of the lemma hold, determining a suitable mixing time T , degree distribution of the vertices, and calculations for the expected number of returns R v to a vertex v within the mixing time.
We envisage that the aforementioned models will be rapidly mixing (i.e., T = O(log a n) for some constant a), and that, for sufficiently sparse graphs, it will be possible to determine degree distributions and demonstrate tree-like local graph structures (which will facilitate the calculation of R v ). Indeed, for the B-C model, each vertex has degree 3 by construction, and [32] shows T = O(log n), thus satisfying condition (b) of Lemma 56.

Weighted Random Walks
The study of weighted random walks, in particular, the cover time, is not nearly as developed as for the unweighted case. We reiterate the following conjecture, made in chapter 8:

Conjecture 2
The minimum degree weighting scheme has O(n 2 ) cover time on all graphs G.
We do not believe that "standard" techniques (for examples, those presented in chapter 5, and subsequent chapters) are sufficient to prove this conjecture. In fact, we believe that it may require new techniques or further development of the underlying theory of weighted random walks.