Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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.

Theorem 1 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},
    Abstract = {Suppose we have a undirected graph <i>G</i> = (<i>V</i>,<i>E</i>) where <i>V</i> is the set of vertices and <i>E</i> is the set of edges. Suppose <i>E</i> consists of red colored edges and blue colored edges. Suppose we have an infinite sequence <i>S</i> of characters <i>R</i> and <i>B</i>. <p>We take a random walk starting at vertex <i>v</i> on <i>G</i> based on the sequence <i>S</i> as follows:   <p>At the <i>i</i>th step, if <i>S</i> has an <i>R</i> at position <i>i</i> the walk traverses a random red edge out of the current vertex (chosen uniformly from the outgoing edges). If <i>S</i> has a <i>B</i> the walk traverses a random blue edge out of the current vertex. <p>We say <i>S</i> covers <i>G</i> starting at vertex <i>v</i> when a random walk using <i>S</i> starting at <i>v</i> covers every vertex of <i>G</i>.   <p><strong>Theorem 1</strong> If <i>G</i> is a red-blue colored undirected graph which is connected in red and connected in blue and there exists an <i>RB</i>-sequence <i>S</i>  such that starting at some vertex <i>v</i>, <i>Pr</i>[<i>S</i> covers <i>G</i>] < 1, then <i>G</i> contains a proper subgraph <i>H</i> such that <i>H</i>'s vertices can be divided into two sets: <i>U</i> and <i>W</i> where there are no red edges between <i>U</i> and <i>V</i> - <i>W</i> and no blue edges between <i>U</i> and <i>V</i> - <i>U</i>.}
}

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