Infinitely Long Walks on Two Colored Graphs
Peter S. Gemmell
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-719
December 1992
http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-719.pdf
Suppose we have a undirected graph G = (V,E) where V is the set of vertices and E is the set of edges. Suppose E consists of red colored edges and blue colored edges. Suppose we have an infinite sequence S of characters R and B.
We take a random walk starting at vertex v on G based on the sequence S as follows:
At the ith step, if S has an R at position i the walk traverses a random red edge out of the current vertex (chosen uniformly from the outgoing edges). If S has a B the walk traverses a random blue edge out of the current vertex.
We say S covers G starting at vertex v when a random walk using S starting at v covers every vertex of G.
<strong>Theorem 1</strong> If G is a red-blue colored undirected graph which is connected in red and connected in blue and there exists an RB-sequence S such that starting at some vertex v, Pr[S covers G] < 1, then G contains a proper subgraph H such that H's vertices can be divided into two sets: U and W where there are no red edges between U and V - W and no blue edges between U and V - U.
BibTeX citation:
@techreport{Gemmell:CSD-92-719,
Author = {Gemmell, Peter S.},
Title = {Infinitely Long Walks on Two Colored Graphs},
Institution = {EECS Department, University of California, Berkeley},
Year = {1992},
Month = {Dec},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6015.html},
Number = {UCB/CSD-92-719}
}
EndNote citation:
%0 Report %A Gemmell, Peter S. %T Infinitely Long Walks on Two Colored Graphs %I EECS Department, University of California, Berkeley %D 1992 %@ UCB/CSD-92-719 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6015.html %F Gemmell:CSD-92-719