ABSTRACT
Title of Dissertation: DISCRETE INVERSE CONDUCTIVITY PROBLEMS
ON NETWORKS
Farshad Foroozan, Doctor of Philosophy, 2006
Dissertationdirectedby: CarlosA.Berenstein,Professor,
Department of Mathematics and
The Institute for Systems Research
The purpose of this dissertation is to present a mathematical model of network tomog-
raphy through spectral graph theory analysis. In this regard, we explore the properties of
harmonic functions and eigensystems of Laplacians for weighted graphs (networks) with
and without boundary. We prove the solvability of the Dirichlet and Neumann boundary
value problems. We also prove the global uniqueness of the inverse conductivity problem
on a network under a suitable monotonicity condition. As a physical interpretation to the
discrete inverse conductivity problem, we dene a variant of the chip-ring game (a dis-
crete balancing process) in which chips are added to the game from the boundary nodes and
removed from the game if they are red into the boundary of the graph. We nd a bound on
the length of the game, and examine the relations between set of spanning weighted forest
rooted in the boundary of the graph and the set of critical congurations of the chips.
DISCRETE INVERSE CONDUCTIVITY PROBLEMS ON NETWORKS
by
Farshad Foroozan
Dissertation submitted to the Faculty of the Graduate School of the
University of Maryland, College Park in partial fulllment
of the requirements for the degree of
Doctor of Philosophy
2006
Advisory Committee
Professor Carlos Berenstein, Chairman
Professor Kenneth Berg
Professor David Mount
Professor Clyde Kruskal
Professor James Purtilo
c Copyright by
Farshad Foroozan
2006
To my daughter, Sarvnaz, and my wife, Lili.
ii
ACKNOWLEDGEMENTS
I am indebted to my advisor, Professor Carlos Berenstein, for his vision, patience, guid-
ance, and support. His original idea of discretization of the inverse connectivity problems
and its contribution to the eld of network tomography, inspired me to do this dissertation.
This work would denitely have been impossible without him. I would like to express
my gratitude to Professor Berg and Professor Mount whom I benetted a lot from their
very interesting comments and fruitful discussions over the last year. My warm thanks to
Professor Levermore for his support and advice on many occasions. I would also like to
thank my advisory committee members; Professor Kruskal, and Professor Purtilo for their
helpful and stimulating discussions.
I am grateful to all the professors of the mathematics and the electrical engineering
courses I took at University of Maryland over the years and who thereby shaped my un-
derstanding of applied mathematics; Professor Baras, Professor Benedetto, Professor Berg,
Professor Freidlin, Professor Krishnaprasad, Professor Levine, Professor Narayan, Profes-
sor Papamarcou, Professor Schwartz, and Professor Warner.
It would have been impossible for me to survive without the nancial support of the
Mathematics department. I would like to thank the department for providing me with
teaching assistantships.
Finally, I wish to express my deepest thanks to my parents and my family for their
iii
patience, understanding, and encouragement.
iv
Contents
1 Introduction 1
1.1 Calculus on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Properties of Harmonic Functions . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Spectra of the Normalized and the Combinatorial Laplacians . . . . . . . 13
1.4 Dirichlet and Neumann Eigenvalues . . . . . . . . . . . . . . . . . . . . . 17
1.4.1 Dirichlet Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2 Neumann Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5 The Diameter of a Weighted Graph . . . . . . . . . . . . . . . . . . . . . . 26
2 The Discrete Inverse Conductivity Problem 29
2.1 Discrete Green's Function . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Dirichlet and Neumann boundary Value Problems . . . . . . . . . . . . . . 40
2.3 Inverse Conductivity Problem on the Network . . . . . . . . . . . . . . . . 48
3 The Physical Interpretation of The Discrete Inverse Conductivity Problem 62
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2 Basic Theory of the Dirichlet Game . . . . . . . . . . . . . . . . . . . . . 67
3.3 Critical Conguration of the Dirichlet Game . . . . . . . . . . . . . . . . . 70
3.4 Dirichlet Game as a Discrete Dynamical System . . . . . . . . . . . . . . . 75
3.5 Basic Theory of Electrical Networks . . . . . . . . . . . . . . . . . . . . . 79
3.6 Random Walk interpretation of Electrical Networks . . . . . . . . . . . . . 88
3.7 Upper Bound for Run-Time Estimates . . . . . . . . . . . . . . . . . . . . 95
v
4 Algebraic Aspects of the Dirichlet Game 101
4.1 The Determinant of the Dirichlet Laplacian . . . . . . . . . . . . . . . . . 102
4.2 Relation of Green's Function to Dirichlet Game . . . . . . . . . . . . . . . 106
4.3 Critical Conguration and Rooted Spanning Weighted Forest . . . . . . . . 111
5 REFERENCES 116
vi
Chapter I
1 Introduction
A network consists of interconnecting any pair of users or nodes by means of some links.
Because of the complexity and the size of the network, it is desirable to study only a sub-
set of the nodes ( known as boundary nodes) to discover and detect certain problems in
the interior of the network. These problems might include checking connectivity, nding
largest components, tracking data trafc, assessing and dealing with a variety of security
and reliability issues. From the practical point of view, this is normally done by setting
up ?monitors? at a relatively small subset of the nodes. From the monitors, data can be
collected and examined. The problem of discovering the detailed inner structure of the
network from a collection of ?end-to-end? measurements can be seen as a type of inverse
problem, analogous to those arising in tomography, but with a discrete avor.
Motivatedbythisapplication,BerensteinandChung[6]initiatedtheworkofdiscretiza-
tion of the inverse conductivity problem by means of the spectral graph theory. Their work
led to a key result in the domain of discrete inverse conductivity problem which proves
the uniqueness of weights (conductivity or connectivity) under certain monotonicity con-
ditions. Further investigations include exploring some variant of chip-ring game as a
physical interpretation of the discrete inverse conductivity problem. This is motivated in
part by communication network models in which chips represent packets or jobs and the
boundary nodes represent processors.
This thesis is divided into four chapters. Chapter I is a substantive introduction to
1
the Laplacians of graphs, including properties of the spectra of Laplacians, and the de-
velopment of calculus on graph. Chapter II introduces the discrete Green's function, and
improves the result of Berenstein and Chung [6] under a weaker condition. Chapter III de-
scribes the Dirichlet chip-ring game on weighted graph as a physical interpretation of the
discrete inverse conductivity problem and provides an upper bound estimate on the time for
the conguration to reach a stable conguration in terms of the diameter of the weighted
graph. Chapter IV combines the results of Chapter III and the discrete Green's function to
allow fast computation of the upper bound run-time estimate.
Before presenting a more detailed summary of the contents of this chapter, we mention
some important contributions to the eld of spectral graph theory. An early fundamental
problem in the study of the spectra of graphs was the question of whether a graph can be
determined by its set of eigenvalues. The answer was found to be negative. That led to
further research in the study of isospectral graphs [ 16, 29]. Motivated by the study of the
eigenvalues of Laplacians of compact Riemannian manifolds, bounds for the eigenvalues
of the discrete Laplacian have been studied [3, 21, 31, 50]. Further developments in this
area include, properties of the second smallest eigenvalue [49, 50], expansion properties
[2], isoperimetric number and Cheeger's constant [52], and the heat kernel of Laplacian
[18].
Thischapterisdividedintovesections. Therstsectionstudiescalculusongraphs. In
thesecondsection,westudythepropertiesofharmonicfunctionasasolutiontothediscrete
Laplace's equation and formulate a theorem that gives a necessary and sufcient condition
for a function to be harmonic. In the third section, the symmetric versions of the discrete
Laplacian which are the combinatorial and the normalized Laplacians are introduced. This
2
symmetrization will allow us to study the eigenvalues of the discrete Laplacian. The nor-
malization of the Laplacian is mainly due to keep the subject parallel to the eigenvalues of
thecompactRiemannianmanifold. Theoremsinvolvingpropertiesoftheeigenvaluesofthe
weighted Laplacian have been developed. In section four, we study the Neumann and the
Dirichlet boundary conditions along with the spectrum of the Neumann and the Dirichlet
Laplacians. Oneoftheobjectivesofthissectionistoformulatematriceswhoseeigenvalues
are the Neumann and the Dirichlet eigenvalues. We also discuss the relationship between
the Neumann eigenvalue and the eigenvalue of the transition probability matrix of the Neu-
mann random walk. In the last section, we introduce the concept of the diameter of the
weighted graph and its relation to the rst eigenvalue of Laplacian. Interesting bounds on
the diameter of the graph are also introduced.
1.1 Calculus on Graphs
We will begin with some denitions of graph theoretic terminologies which are largely
derived from Berenstein-Chung [6].
By a graph G D.V;E;2/;we mean a non-empty nite set V of vertices, a non-empty
nite set E of edges, and an injective map 2 from E into the two element subsets of V.
The elements of 2.e/ are called the endpoints of the edge e: For simplicity, we drop the
notation2and write the graph as G D.V;E/:
A path in G is an ordered set of vertices x0;x1;x2;:::;xn such that for eachi;1  i  n
implies xi 1  xi: Here, the notation xi 1  xi means that two vertices xi 1 and xi are
connected (adjacent) by an edge in E. The graph G is connected if any two vertices are
3
connected by a path.
A graph .S;T/ is said to be a subgraph of G D .V;E/; if S and T are non-empty
subsets of V and E respectively. If .S;T/ consists of all edges of G which have both
endpoints in S, then .S;T/ is called an induced subgraph of G and is denoted by GS
D .S;ES/: We dene the boundary @S of S to be set of all vertices not in S but adjacent
to some vertex in S, i.e., @S D fy 2.V n S/j 9x 2 S; such that x  yg. And the inner
boundary is dened by@0S D fz 2 S j 9y 2@S; such that y  zg:
A weighted graph G D.V;E/has associated with it a non-negative function
w : V  V ! R;
such thatw.x;y/Dw.y;x/;andw.x;y/D 0 if either x D y or x and y are not connected
by an edge in E.
For x 2 V and a non-empty subset U of V, we dene a relative degree dGU.x/ of x
with respect to the induced subgraph GU of G as
dGU.x/D
X
y2U
w.x;y/;
if U D V;we call dG.x/DPy2V w.x;y/the degree of the vertex x.
The weighted discrete Laplacian1w of a function f : V ! R on a graph G D.V;E/
and a point x 2 V such that dG.x/6D 0 is dened as
1w f.x/D
X
y2V
.f.x/  f.y//w.x;y/d
G.x/
;
4
if x isanisolatedvertexof G,i.e.,dG.x/D 0thenweset1w f.x/D 0:
The symmetrized versions of the discrete Laplacian are the weighted combinatorial
Laplacian Lw and the weighted normalized Laplacian ?w. The combinatorial Laplacian
is related to the algebraic aspect of the graph theory, whereas the weighted normalized
Laplacian is related to the geometric aspect of the spectral graph theory [18]. The weighted
combinatorial Laplacian Lw of a function f : V ! R is dened as
Lw f.x/D
X
y2V
.f.x/  f.y//w.x;y/:
The weighted normalized Laplacian ?w of a function f : V ! R on a graph G D.V;E/
and a point x 2 V such that dG.x/6D 0 is dened as:
?w f.x/D
X
y2V
 f.x/
pd
G.x/
  f.y/pd
G.y/
 w.x;y/
pd
G.x/
;
if dG.x/ D 0 then we set ?w f.x/ D 0: The matrix formulation of the above Laplacians
become:
1w.x;y/ D
8
>>>>
>><
>>>
>>>
:
1 if x D y and dG.x/6D 0
 w.x;y/d
G.x/
if x is adjacent to y
0 otherwise:
5
Lw.x;y/D
8>
>>>
>><
>>>
>>>:
dG.x/ if x D y
 w.x;y/ if x is adjacent to y
0 otherwise:
?w.x;y/D
8>
>>>>
><
>>>>
>>:
1 if x D y and dG.x/6D 0
  w.x;y/.d
G.x/dG.y//1=2
if x is adjacent to y
0 otherwise.
Let T denotethediagonalmatrixwiththe.x;x/-theentryhavingthevaluedG.x/:Then
the following relations hold between1w; Lw;?w :
Lw D T1=2?wT1=2 D T1w;
?w D T 1=2LwT 1=2 D T1=21wT 1=2;
1w D T 1Lw D T 1=2?wT1=2;
provided that G does not have an isolated vertex x, i.e., dG.x/6D 0:
We now develop the concept of differential and integral calculus on graphs. Let S be
a non-empty subset of V and GU an induced subgraph of the graph G. For a function f
dened on S, the integration of f over S with respect to the relative degree dGU.x/for each
6
x 2 S is dened as
Z
S
f.x/dGU.x/D
X
x2S
f.x/dGU.x/:
If U D V then the integration of f over S simply becomes:
Z
S
f.x/dG.x/D
X
x2S
f.x/dG.x/:
The directional derivative of the function f dened on V for the graph G with no isolated
vertices is dened as
Dw;y f.x/D.f.x/  f.y//
w.x;y/
dG.x/
1=2
;
for each x and y 2 V: The gradient rw of a function f is dened to be a vector in Rn,
where n is the number of vertices,
rw f.x/D. Dw;y f.x//y2V:
We now introduce the notion of outward normal derivative. For an induced subgraph GS D
.S;ES/of a graph G with non-empty boundary@S, the outward normal derivative @f@
wn
.z/
at z 2@S is dened as
@f
@wn.z/D
X
y2S
.f.z/  f.y//w.z;y/d
GS.z/
:
As a consequence of the above denitions, it is easy to see that the following lemma is
7
true.
Lemma 1.1.1
Let f be dened on the set of vertices V of the graph G with no isolated vertices. Then
Z
V
j rw f.x/j2 dG.x/D 2
X
xy
j f.x/  f.y/j2 w.x;y/;
wherePxy denotesthesumoverallunorderedpairsfx;ygforwhich x and y areadjacent.
Proof: The proof follows easily from the denition of the integral.
Z
V
j rw f.x/j2 dG.x/D
X
x2V
X
y2V
j f.x/  f.y/j2 w.x;y/
D 2
X
xy
j f.x/  f.y/jw.x;y/
QED
Theorem 1.1.2
For any pair of functions f; h dened on the set of vertices V of the graph G with no
isolated vertices;we have:
2
Z
V
h.x/1w f.x/dG.x/D
Z
V
.rw f.x//:.rwh.x//dG.x/:
Proof:
2
Z
V
h.x/1w f.x/dG.x/ D 2
X
x2V
h.x/1w f.x/dG.x/
D 2
X
x2V
h.x/
X
y2V
.f.x/  f.y//w.x;y/d
G.x/
dG.x/
8
D 2
X
x2V
h.x/
X
y2V
.f.x/  f.y//w.x;y/
D
X
x2V
X
y2V
.h.x/  h.y//.f.x/  f.y//w.x;y/
D
X
x2V
.rw f.x//:.rwh.x//dG.x/
D
Z
V
.rw f.x//:.rwh.x//dG.x/:
QED
Theorem 1.1.3
Under the same hypothesis as in Theorem 1.1.2, we have the following identities
a/2RV f.x/1w f.x/dG.x/DRV j rw f.x/j2 dG.x/;
b/RV h.x/1w f.x/dG.x/DRV f.x/1wh.x/dG.x/;
Furthermore, for an induced subgraph GS of G with non-empty boundary@S , we have
c/RS.f.x/1wh.x/ h.x/1w f.x//dGS.x/DR@S.h.z/ @f@
wn
.z/  f.z/ @h@
wn
.z//dGS.z/;
where S D S [@S:(c) is also known as Green's theorem.
Proof: (a) follows from Theorem 1.1.2, by substituting h for f: (b) also follows from
Theorem 1.1.2 by symmetry. We prove part (c) as follows. Letw0 be a real valued function
on S S dened by
w0.x;y/D
8>
><
>>:
w.x;y/ if either x or y are in S
0 otherwise.
Let ES be the subset of edges ES such that w0.x;y/ > 0 if fx;yg is an edge in ES with
endpoints x and y: Then GS D .S; ES/ is a subgraph of G: Applying the Theorem 1.1.3
9
(b) to the graph GS withw0 as its weight function, we see that
0 D
Z
S
.h.x/1w0 f.x/  f.x/1w0h.x//d0G
S
.x/
D
Z
S
.h.x/1w0 f.x/  f.x/1w0h.x//d0G
S
.x/

C
Z
@S
.h.z/1w0 f.z/  f.z/1w0h.z//d0G
S
.z/

(1)
where d0G
S
.x/ is the degree of the vertex x of the graph GS with respect to the weight
functionw0:From the denitions of the degree and the discrete Laplacian, it is easily seen
that if x 2 S then d0G
S
.x/D dGS.x/;1w0 f.x/D1w f.x/;and1w0h.x/D1wh.x/:Also,
if z 2@S then d0G
S
.z/D dGS.z/;1w0 f.z/D @f@
wn
.z/;and1w0h.z/D @h@
wn
.z/:Substituting
these equalities to (1) gives the required result:
Z
S
.f.x/1wh.x/  h.x/1w f.x//dGS.x/ D
Z
@S
.h.z/ @f@
wn
.z/  f.z/ @h@
wn
.z//dGS.z/:
QED
1.2 Properties of Harmonic Functions
Let GS D.S;ES/beaconnectedinducedsubgraphof G D.V;E/withnon-emptybound-
ary set@S :A function f : S ! R such that
1w f.x/D
X
y2S
.f.x/  f.y//w.x;y/d
G.x/
D 0; for all x 2 S;
10
is said to be harmonic on GS. Solving the above equation for f.x/;we get
f.x/D 1d
G.x/
X
y2S
f.y/w.x;y/; for all x 2 S:
Therefore, a harmonic function is the weighted average of the values of function at its
neighboring vertices. The following theorem shows that the maximum and minimum of a
harmonic function cannot occur in the interior of the graph.
Theorem 1.2.1
Let GS be a connected induced subgraph of G with non-empty boundary @S: For a
non-constant function f : S ! R , we have:
a) If1w f.x/D 0 for all x 2 S;then f has no maximum or minimum value in S:
b) If1w f.x/ 0 for all x 2 S;then f has no minimum value in S:
c) If1w f.x/ 0 for all x 2 S;then f has no maximum value in S:
Proof: Part (a) follows from parts (b) and (c) together. Part (c) carries the same argu-
ment as (b). So we only prove part (b). Assume S has a vertex x such that f.x/is minimum
and there is a vertex y0 2 S adjacent to x such that f.x/6D f.y0/. Such a choice is possible
by the connectedness of GS and the fact that f is a non-constant function on S. Because
1w f.x/ 0 then
f.x/  1d
G.x/
X
y2S
f.y/w.x;y/
D 1d
G.x/
X
y6Dy0
y2S
f.y/w.x;y/C f.y0/w.x;y0/ 1d
G.x/
11
> 1d
G.x/
X
y6Dy0
y2S
f.x/w.x;y/C f.x/w.x;y0/ 1d
G.x/
D f.x/:
This is clearly a contradiction, therefore, f has no minimum value in S.
QED
Under the same hypothesis as in Theorem 1.2.1, the following statements are true.
Corollary 1.2.2
If 1w f.x/ D 0 and1wg.x/  0 for all x 2 S then g j@S f j@S implies g  f on
S:
Corollary 1.2.3
If a function f : S ! R satises1w f.x/ D 0 for all x 2 S and j f j has a maximum
on S, then f is a constant function.
The next theorem gives a necessary and sufcient condition for a function to be har-
monic on GS:
Theorem 1.2.4
Let GS be a connected induced subgraph of G with non-empty boundary@S. Then the
function f : S ! R is harmonic on GS if and only if for every subset S0 of S; we have
R
@S0
@f
@wn.z/dGS0.z/D 0:
Proof: Suppose that R@S0 @f@
wn
.z/dGS0.z/ D 0 for every subset S0 of S: For x 2 S; let
S0 D fxg. Since
Z
@S0
@f
@wn.z/dGS0.z/D
X
z2@S0
.f.z/  f.x//w.z;x/;
12
therefore,
X
z2@S0
.f.z/  f.x//w.z;x/D 0:
This implies that f is harmonic on GS . Conversely, suppose that 1w f.x/ D 0 for all
x 2 S:Clearly f is harmonic on any subset S0 of S:Applying the Green's theorem , with
h identically 1 and noting that1w f.x/D 0 on S0, givesR@S0 @f@
wn
.z/dGS0.z/D 0:
1.3 Spectra of the Normalized and the Combinatorial Laplacians
In this section, we discuss the spectra of the normalized and the combinatorial Laplacians
for weighted graphs. We begin by characterizing the eigenvalues of the normalized and the
combinatorial Laplacians in terms of the Rayleigh quotient, which for a given matrix A and
vector x is dened as
R.x/D hx; Axihx; xi ;
where the notation h;i is the standard inner product. In particular, the Rayleigh quotient
for a matrix A and eigenvector x evaluates to the corresponding eigenvalue. Let f denote
an arbitrary function dened on the vertices V of the graph G . We can view f as a column
vector. Then the Rayleigh quotient for Lw is
hf; Lw fi
hf; fi D
P
xy.f.x/  f.y//2w.x;y/P
x f 2.x/
:
13
And the Rayleigh quotient for ?w and the function g dened on V is
hg; ?wgi
hg; gi D
D
g;T  12 LwT  12 g
E
hg; gi
D hf; Lw fiD
T 12 f; T 12 f
E
D
P
xy.f.x/  f.y//2w.x;y/P
x f 2.x/dG.x/
;
where g D T 12 f:Let0  1  2  :::  n 1 be the eigenvalues of the real symmetric
matrix ?w: Then, as a consequence of the Courant-Fisher theorem [39, Theorem 4.2.11],
we have
0 D min
f6D0
P
xy.f.x/  f.y//2w.x;y/P
x f 2.x/dG.x/
;
and
n 1 D max
f6D0
P
xy.f.x/  f.y//2w.x;y/P
x f 2.x/dG.x/
:
We can easily see from the above equations that all eigenvalues of ?w are non-negative and
0 is the minimum eigenvalue of ?w. Let 1 denote the constant function which has a value 1
on each vertex. Then T 121 is an eigenfunction of ?w that corresponds to the eigenvalue 0.
Applying the Courant-Fisher theorem again, we obtain the minimum nonzero eigenvalue
to be:
1 D min
f6D0; T 12 f ? T 121
P
xy.f.x/  f.y//2w.x;y/P
x f 2.x/dG.x/
:
In general, for k D 0;:::;n  1,
k D min
f6D0;T 12 f ?'0;:::;'k 1:
P
xy.f.x/  f.y//2w.x;y/P
x f 2.x/dG.x/
:
14
where'0;:::;'n 1 are the corresponding eigenfunctions. Applying similar argument to the
eigenvalues0 1 :::n 1 of Lw;we obtain0 D 0 and for k D 0;:::;n   1;we
have:
k D min
f6D0; f ? 0;:::; k 1
P
xy.f.x/  f.y//2w.x;y/P
x f 2.x/
;
where  0;:::; n 1 are the corresponding eigenfunctions. The following important and
relatively simple lemma of which the non-weighted version appears in Fan Chung [18,
page 7].
Lemma 1.3.1
Let0  1  :::  n 1 be the eigenvalues of the combinatorial Laplacian Lw;and
0 1 2 :::n 1 the eigenvalues of ?w . Then
(a)Pi i DPx dG.x/andPi i  n;where n is the number of vertices in G:
(b) For n  2;
1  nn  1 .
Also for a graph G without isolated vertices, we have
n 1  nn  1 .
(c) The multiplicity of zero eigenvalue is the same as the number of connected compo-
nents of G:
(d) For all i  n  1;we havei  2dmax andi  2:
Proof: (a) follows by considering the traces of Lw and ?w:
For(b)suppose1 > nn  1;thenitcanbeeasilyseenthatPi i >n whichcontradicts
15
(a):And if there is no isolated vertex, we easily see thatn 1  nn  1 :
For (c) suppose that G is connected. Let  be an eigenfunction of Lw for the zero
eigenvalue . Then
Lw. /D 0;
or
h ;Lw i D
X
xy
. .x/  .y//2w.x;y/D 0:
This implies that  must be a constant function on G and the eigenspace of Lw corre-
sponding to zero eigenvalue must be one dimensional. When G is not connected, the
result follows from block diagonalizing Lw in terms of the combinatorial Laplacian of the
connected components of G: For the normalized Laplacian ?w; the same argument ap-
plies.
Toshow(d),weusetheRayleighquotientcharacterizationofn 1 andn 1:Asargued
above,
n 1 D max
f6D0
hf ; Lfi
h f ; f i D maxf6D0
P
xy.f.x/   f.y//2w.x;y/P
x2V f 2.x/
:
Since
X
xy
.f.x/  f.y//2w.x;y/
X
xy
2.f 2.x/C f 2.y//w.x;y/;
therefore,
n 1  max
f6D0
2Px2V f 2.x/dG.x/P
x2V f 2.x/
 2dmax
16
The argument forn 1 is similar. The Rayleigh quotient forn 1 is
n 1 D max
f6D0
P
xy.f.x/   f.y//2w.x;y/P
x2V f 2.x/dG.x/
 max
f6D0
P
xy 2.f 2.x/C f 2.y//w.x;y/P
x2V f 2.x/dG.x/
 max
f6D0
2Px2V f.x/2dG.x/P
x2V f 2.x/dG.x/
 2:
QED
1.4 Dirichlet and Neumann Eigenvalues
1.4.1 Dirichlet Eigenvalues
Let GS be an induced subgraph of the graph G D.V;E/with the non-empty boundary@S
such that S D V:A function f : S ! R is called a Dirichlet function if f.x/ D 0 for all
x 2@S. We wish to study those Dirichlet functions f and g that satisfy
Lw f.x/ D  f.x/ for all x 2 S;
?wg.x/ D g.x/ for all x 2 S:
Inthiscase, f isaDirichlet eigenfunctionof Lw correspondingto aDirichleteigenvalue;
andsimilarly g isaDirichleteigenfunctionof?w correspondingtoaDirichleteigenvalue:
Viewing Lw as a matrix, we now dene the Dirichlet Laplacian Lw;S to be Lw restricted to
the rows and columns of S. We dene the Dirichlet normalized Laplacian and the Dirichlet
discrete Laplacian similarly. The following lemma generalizes the Lemma 8.2 of [18] to
17
graphs with arbitrary weights.
Lemma 1.4.1
A Dirichlet function f : S ! R is a Dirichlet eigenfunction if and only if f jS is an
eigenfunction of Lw;S:Similarly, a Dirichlet function g : S ! R is a Dirichlet eigenfunc-
tion if and only if gjS is an eigenfunction of ?w;S:The eigenvalue of Lw;S corresponding
to f is given by
 D
P
xy.f.x/   f.y//2w.x;y/P
x2V.f.x//2
;
and the eigenvalueof ?w;S corresponding to g is given by
D
P
xy.f.x/   f.y//2w.x;y/P
x2V.f.x//2dG.x/
;
where g D T1=2 f:
Proof: Let f be a Dirichlet function on S. Then for all x 2 S;
Lw;S f jS .x/ D f jS .x/dG.x/ 
X
y2S;xy
f jS .y/w.x;y/
D f.x/dG.x/ 
X
y2V;xy
f.y/w.x;y/ D Lw f.x/:
Therefore, for all x 2 S and f a Dirichlet function on S ; Lw f.x/D f.x/ if and only if
Lw;S f jS .x/ D  f jS .x/:The Rayleigh quotient of Lw;S for an eigenfunction f of Lw;s
18
shows that
 D h f jS ; Lw;s f jSih f j
S; f jSi
D
P
x2S f jS .x/

f jS .x/dG.x/ Py2S;xy f jS .y/w.x;y/

P
x2S f j2S .x/
D
P
xy;x2S; y2S .f.x/   f.y//2w.x;y/P
x2V f 2.x/
D
P
xy.f.x/   f.y//2w.x;y/P
x2V.f.x//2
:
The proof for the normalized Laplacian proceeds analogously. Let g be a Dirichlet function
on S:Then for all x in S;
?w;SgjS .x/ D
X
y2S;x~y
gj
S .x/p
dG.x/  
gjS .y/p
dG.y/
 w.x;y/
pd
G.x/
D g.x/ 
X
y2S;x~y
g.y/p
dG.y/dG.x/w.x;y/D ?wg.x/:
Thus for all x 2 S;?w;SgjS .x/DgjS .x/if and only if ?wg.x/Dg.x/:The Rayleigh
quotient for ?w;S shows thatsatises
 D h gjS ; ?w;SgjSih gj
S ; gjSi
D
P
x2S gjS .x/

gjS .x/ Py2S;xy gjS .y/pd
G.y/dG.x/
w.x;y/

P
x2S gjS
2.x/
D
P
xy.f.x/   f.y//2w.x;y/P
x2V.f.x//2dG.x/
;
where g D T1=2 f:
19
QED
ThefollowingexampleshowsthedifferencebetweentheDirichleteigenfunctions(eigen-
vectors) and the eigenvectors of the Laplacians.
Example 1
Consider the complete graph K3 on the vertices f1;2;3g. Let S D f1;2g and@S D f3g:
Then the Laplacians and the Dirichlet Laplacians are
Lw.x;y/D
8>
><
>>:
2 if x D y
 1 if x 6D y
and ?w D Lw2
Lw;s.x;y/D
8
>><
>>:
2 if x D y
 1 if x 6D y
and ?w;s D Lw;s2
Lw has eigenvectors.1;1;1/;.1; 1;0/;.0;1; 1/with eigenvalues 0;3;3 respectively.
However, only .1; 1;0/ is a Dirichlet eigenvector for Lw with respect to S. The other
Dirichlet eigenvector is .1; 1; 0/ with Dirichlet eigenvalue 1; since Lw;s.1;1/ D .1; 1/.
But.1;1;0/is not an eigenvector of Lw:Moreover, since ?w D Lw2 and ?w;s D Lw;s2 , ?w
has the same eigenvectors and Dirichlet eigenvectors with the corresponding eigenvalues
and Dirichlet eigenvalues multiplied by 12.
Letting n D jSj, we label the Dirichlet eigenvalues of Lw ( or the eigenvalues of the
Dirichlet combinatorial Laplacian Lw;s/ by S1  S2  :::  Sn . Similarly, we label
the Dirichlet eigenvalues of ?w (or the eigenvalues of the Dirichlet normalized Laplacian
?w;s ) by S1 S2  :::Sn . The following lemma describes the structure of the Dirichlet
eigensystem of combinatorial and normalized Laplacian.
20
Lemma 1.4.2
The following holds for the Dirichlet eigensystem of the combinatorial and the corre-
sponding eigensystem for the normalized Laplacian.
(a)Pi Si DPx dG.x/;andPi Si  n;where n D jSj:
(b) Lw;S and ?w;S are positive semi-denite, thereforeSi andSi are real and nonneg-
ative. Furthermore, S1 and S1 > 0 if and only if every connected component of G has a
vertex adjacent to a vertex in@S:
(c) For all 1  i  n;we haveSi  2dmax andSi  2:
Proof: (a) follows from considering the traces of Lw;s and ?w;s: For (b), according to
the Lemma 1.4.1,Si andSi are expressed in terms of Rayleigh quotient of Lw;S and ?w;S
respectively, which are all nonnegative. Furthermore, we easily see that S1 > 0; since
there does not exist a nonzero Dirichlet function with f.x/D f.y/ for all fx;yg  E; if
and only if every connected component of G has at least one of its vertices adjacent to a
vertex in the boundary@S:The proof ofS1 > 0 is similar. The proof of part (c) is similar
to the proof of Lemma 1.3.1.
QED
1.4.2 Neumann Eigenvalues
Now, we consider the Laplacian ?w act on functions f : S ! R such that the value of
the function at a boundary vertex is the weighted average of the values of the function
at adjacent vertices in S. In other words, f satises the following Neumann boundary
21
condition:
X
y2S
.f.x/  f.y//w.x;y/D 0; for all x 2@S:
We are interested in studying those functions that satisfy Neumann conditions and
?w.f.x//Df.x/:
Todothis, wewillusethesameideaasusedforthedescriptionoftheDirichleteigenvalues.
Wedenethefollowingmatrix Dw withrowsindexedbyverticesin S andcolumnsindexed
by vertices in S;
Dw.x;y/D
8>
>>>>
><
>>>>
>>:
1 if x D y
w.x;y/
dGS.x/ if x 2@S; y 2 S and x  y
0 otherwise:
Using the matrix Dw, we dene the combinatorial Neumann Laplacian as
Nw;S D DTwLwDw :
Similarly, we dene the normalized Neumann Laplacian as
LNw;S D T  12 DTwLwDwT  12 :
The action of the normalized Neumann Laplacian LNw;S on the space of functions f on S
is the same as the action of ?w on the space of functions f on S that satises the Neumann
22
condition, that is,
LNw;S.f.x//D ?w.f.x// for x 2 S :
Therefore the eigenvalues of LNw;S and the corresponding eigenfunctions, f satisfy the
following relation
?w.f.x//DS;i f.x/;
where we dene the values of f on @S in such a way that f would satisfy the Neumann
condition on S. Now, applying the Courant-Fisher theorem to the real symmetric matrix
LNw;S, we see that
S;1 D min
g ?T 12 1
hg; LNw;Sgi
h g ;gi
D min
g ?T 12 1
P
x2S g.x/ LNw;S.g.x//P
x2S g2.x/
D min
g ?T 12 1
P
x2S g.x/?w.g.x//P
x2S g2.x/
D min
f : P f.x/dG.x/D0
P
x2S f.x/Lw.f.x//P
x2S f 2.x/dG.x/
;
where g D T 12 f:From the following relation
X
x2S
f.x/Lw.f.x//D
X
fx;yg2S0
.f.x/  f.y//2w.x;y/;
where S0 denotes the union of edges in S and the boundary edges (the edge with one end-
point in S and the other endpoint not in S/, we dene the rst Neumann eigenvalue of an
23
induced subgraph as follows
NS;1 D min
fP
f.x/dG.x/D0
P
fx;yg2S0.f.x/  f.y//2w.x;y/P
x2S f 2.x/dG.x/
; .1/
where minimum is taken over all f that satises the Neumann condition. In general, we
dene the i-th Neumann eigenvalueNS;i to be
NS;i D min
f6D0; f ? 0;:::; i 1
P
fx;yg2S0.f.x/  f.y//2w.x;y/P
x2S f 2.x/dG.x/
;
where  k is an eigenfunction corresponding to S;k: Clearly NS;0 D 0: From the follow-
ing lemma whose proof is simple and appears in [18], we easily see that the Neumann
eigenvalue is the eigenvalue of the normalized Neumann matrix.
Lemma 1.4.3
Let f : S ! R be a function that satises (1). Then f satises,
a) For x 2 S;
Lw f.x/D
X
y
fx; yg2S0
.f.x/  f.y//w.x;y/DNS;1 f.x/dG.x/:
(b) For x 2@S,
Lw f.x/D 0:
(c) For any function h : S ! R;we have
X
x2S
h.x/Lw f.x/D
X
fx; yg2S0
.h.x/  h.y//.f.x/  f.y//w.x;y/:
24
We close this section by presenting a special type of random walk that is related to Neu-
mann matrix and call it the Neumann random walk. For an induced subgraph GS with
non-empty boundary@S;let the probability of moving from a vertex x in S to a neighbor
y of x be w.x;y/d
G.x/
if y is in S: If y is in @S; we then move from x to each neighbor z of
y in S with the (additional) probability w.x;y/w.y; z/d
G.x/dGS.y/
: From Pz~y
z2S
w.z;y/ D dGS.y/,
it implies thatPz~y
z2S
w.y; z/
dGS.y/ D 1. Hence
P
z~y
z2S
w.x;y/w.y; z/
dG.x/dGS.y/ D
w.x;y/
dG.x/ for y in@S.
Using the relationPyw.x;y/D dG.x/;it follows that the probabilities of moving from a
vertex x in S to the neighboring vertices or neighboring to the boundary vertices adjacent
to x will add up to 1. The Neumann random walk is a little different from the random
walk often used in which the probability of staying in x which has neighboring vertices
in @S is
P
y2@Sw.x;y/
dG.x/ . In other words the walker in the Neumann random walk, takes
advantage of reecting from the boundary imposed by the Neumann boundary condition.
The transition matrix Pw for this walk is as follows:
Pw D T  12 .I   LNw;S/T 12;
The eigenvalues i of the transitional matrix Pw associated with the Neumann walk are
closely related to the Neumann eigenvaluesSi as follows [18] :
i  1  Si :
25
1.5 The Diameter of a Weighted Graph
In a connected graph G, the distance between two adjacent vertices x and y, is dened to
be 1w.x;y/, where w.x;y/ is the weight of an edge connecting x to y. And the length
of the path, P that connects a vertex x0 to a vertex xn through a sequence of vertices
fxigniD0 is dened to be Pn 1iD0 1w.x
i;xiC1/
. The distance between two vertices x and y;
denoted by dist.x;y/; is dened to be the minimum over the length all possible paths
connecting x and y: The diameter of G, denoted by D, is the maximum over the distance
of all pairs of vertices in G:When graphs are used as models for communication networks,
the diameter corresponds to delays in passing messages through the network, hence it plays
an important role in performance analysis and cost optimization. In this section, we present
a relationship between the diameter of the graph and the smallest positive eigenvalues of
its Laplacians Lw and ?w. The following lemma generalizes the result of Chung [18] to
graphs with arbitrary weights.
Lemma 1.5.1
Let G be a connected weighted graph with the weight functionw:Let S be a connected
induced subgraph of G D.V;E/. Then the eigenvalues1 ;1 are related to the diameter
D as follows
(a)1  1DP
x2V dG.x/
(b)1  1D j V j
Proof: For (a) let f be an eigenfunction achieving 1: Let x0 denote a vertex with
j f.x0/jD maxx2V j f.x/j:Since f is orthogonal to the function T1 (the eigenfunction
of zero eigenvalue), we have Px2V f.x/dG.x/ D 0: Therefore, there exists a vertex xk
26
such that f.x0/f.xk/<0:Let P denote a shortest path in G joining x0 to xk with vertices
x0;x1;:::;xk:Then, from the Rayleigh quotient expression for1, we have:
1 D
P
xy.f.x/   f.y//2w.x;y/P
x2V f.x/2dG.x/

Pk
iD1.f.xi 1/   f.xi//2w.xi 1; xi//
f.x0/2Px2V dG.x/
D
Pk
iD1.f.xi 1/   f.xi//2w.xi 1; xi/
Pk
iD1

1p
w.xi 1 ;xi/
2
Pk
iD1

1p
w.xi 1 ;xi/
2
f.x0/2Px2V dG.x/

1
dist.x0 ;xk/.
Pk
iD1.f.xi 1/   f.xi//2
f.x0/2Px2V dG.x/ ;by Cauchy-Schwarz

1
D.f.x0/   f.xk//
2
f.x0/2Px2V dG.x/
 1DP
x2V dG.x/
(b) follows an almost similar argument as that above. By Rayleigh quotient expression for
1, we have:
1 D
P
xy.f.x/   f.y//2w.x;y/P
x2V f.x/2

Pk
iD1.f.xi 1/   f.xi//2w.xi 1; xi//
f.x0/2 j V j

1
dist.x0 ;xk/.
Pk
iD1.f.xi 1/   f.xi//2
f.x0/2 j V j by Cauchy-Schwarz

1
D.f.x0/   f.xk//
2
f.x0/2 j V j
 1D j V j
QED.
27
There are other interesting bounds are in the literature. Let M denote an n  n matrix
with rows and columns indexed by the vertices of G such that M.x;y/ D 0 if x and y
are not adjacent. Furthermore, suppose there exists a polynomial pt.x/ of degree t such
that pt.M/.x;y/6D 0 for all x;y in V then we conclude that the diameter D satises D  t
[18]. In particular, if we take M to be sum of identity matrix and adjacency matrix of G,.
i.e, A.x;y/D 1if x isadjacentto y, and0otherwise/andthepolynomial pt.x/D.1Cx/t,
then the following inequality for the diameter of regular graphs which are not complete
graphscanbederived,
D 
2
66
6
log.j G j  1/
log.n 1C1n 1 1/
3
77
7
:
The above bound can be further improved by choosing pt to be the Chebyshev polynomial
of degree t. In this case, the logarithmic function is replaced by cosh 1:According to [20],
we have
D 
2
66
6
cosh 1.j G j  1/
cosh 1.n 1C1n 1 1/
3
77
7
:
28
Chapter II
2 The Discrete Inverse Conductivity Problem
Introduction
A network (weighted graph) represents a way of interconnecting any pair of users (nodes)
bymeansofsomelinks(edges). Thus, itisquitenaturalthatitsstructurecanberepresented
in a simplied form. When we have some problem on a part of network or try detecting
such a problem, it is desirable to recognize this problem from measurements made on the
boundary of the network since the network may be very large and its inner structure too
complicated.
Problems involving graph identication have been previously studied by a number of
researchers in the domain of realization of graphs with given distances [24], and on the
reconstruction of graphs from vertex deleted problems [22, 31].
ThemostrecentmethodintroducedbyBerensteinandChung[6]isbasedonananalogy
to the continuous version of the inverse conductivity problem. The inverse conductivity
problem's original aim was to identify the conductivity coefcient in continuous media
from boundary measurements, such as Dirichlet data, Neumann data. The discrete version
of the inverse problem is to identify the connectivity of the nodes and the conductivity
of the edges between each adjacent pairs of nodes from boundary measurements. In this
chapter, we will provide an improved version of the following global uniqueness result due
to Berenstein and Chung [6] for the inverse conductivity problem in a network satisfying
the monotonicity condition:
29
Theorem:
Let w1 and w2 be weights with w1  w2 on S [@S  S [@S and fi be functions
satisfying for each i D 1;2:
8
>>>>
>><
>>>
>>>:
1wi fi.x/D 0; for x 2 S
@fi
@win.z/D .z/; for z 2@S
R
S fi.x/dGwi.x/D K
for a given function  : @S ! R such that R  D 0 and for suitably chosen K > 0:
Furthermore, if we assume that w1.z;y/ D w2.z;y/ on @S @0S and f1 j@SD f2 j@S :
Then we have:
f1 D f2 on S;
and
w1 Dw2 on S  S :
We organize this chapter as follows: We rst discuss the Discrete Green's function in
Section 1. In Section 2, we provide the solution of the Dirichlet and the Neumann value
problems by means of the discrete Green's function. And nally in the last section, we
arrive at the global uniqueness result discussed above and will give an improved version of
this result under a weaker condition.
30
2.1 Discrete Green's Function
Discrete Green's functions are the inverse or pseudo-inverse of combinatorial Laplacians.
The Green's function in the continuous case has been extensively used in solving differen-
tial equations [ 1, 3]. A treatment of Green's functions for partial differential equation can
be found in [58]. The rst major work on the discrete Green's functions as an inverse of
the combinatorial Laplacians is [23]. Just as the Green's function in the continuous case
depends on the domain and the boundary conditions, the discrete Green's functions are
associated with underlying graph and boundary conditions.
We consider a weighted connected graph G D .V;E/. The Green's function for the
casewherethegraph G hasnoboundarycanbedeterminedbybruteforcepseudo-inversion
of the corresponding Laplacian. The following theorem explains this in greater detail.
Theorem 2.1.1
Let f : V ! R be a function. Then the equation
1w f.x/D g.x/; for x 2 V;
has a solution if and only if Px2V g.x/dG.x/D 0. In this case, the solution is given by
f.x/D a0 C
X
y2V
Zw.x;y/g.y/;
where a0 is an arbitrary constant and the matrix Zw is given by
Zw.x;y/D
n 1X
iD1
1
ii.x/i.y/
s
dG.y/
dG.x/:
31
Here the i are the eigenvalues of ?w with the corresponding eigenfunctions i for i D
1;2;:::;n  1:
Proof: SupposePx2V g.x/dG.x/ D 0:Then by considering0.x/ D
s
dG.x/P
x dG.x/
as
an eigenfunction of ?w corresponding to the zero eigenvalue, we have
hT 12g;0i D
X
x
p
dG.x/g.x/
s
dG.x/P
x dG.x/
D
s
1P
x dG.x/
X
x2V
g.x/dG.x/ D 0:
Now, consider the orthogonal expansion of T 12 f;
.T 12 f/.x/D
n 1X
iD0
aii.x/;
where ai D hT 12 f ;ii:Then since 1w D T 1=2?wT1=2;and
iai D ihT 12 f;ii
D hT 12 f;iii
D hT 12 f;?wii
D h?wT 12 f;ii
D hT 12g;ii:
We, therefore, have:
ai D 1
i
X
x
p
dG.x/g.x/i.x/; for i D 1;2;:::n  1:
32
For i D 0, since
0a0 D 0hT 12 f;0i
D hT 12 f;00i
D hT 12 f;?w0i
D h?wT 12 f;0i
D hT 12g;0i
D 0:
and0 D 0;we have a0 that could be an arbitrary constant. From the orthogonal expansion
of T 12 f;we get:
p
dG.x/f.x/D a0
s
dG.x/P
x dG.x/
C
n 1X
iD1
1
i
"X
y2V
p
dG.y/g.y/i.y/
#
i.x/;
or
f.x/ D a0 C
X
y2V
n 1X
iD1
1
ii.x/i.y/
s
dG.y/
dG.x/g.y/
D a0 C
X
y2V
Zw.x;y/g.y/:
Conversely, suppose that 1w f.x/ D g.x/ has a solution. Then Px2V g.x/dG.x/ D 0
because of Green's theorem ( Theorem 1.1.3).
QED
The following corollary is a simple consequence of the above theorem.
33
Corollary 2.1.2
Under the same conditions as in Theorem 2.1.1, let GS be an induced subgraph of G.
Then every solution to
1w f.x/D 0 for all x 2 VnS;
has the following form:
f.x/D a0 C
X
y2S
Zw.x;y/.y/; for x 2 V;
where a0 is an arbitrary constant and .y/D1w f.y/;for y 2 S.
The proof of Theorem 2.1.1 suggests the following denition of Green's function for
graphs with no boundary in a closed form. We dene Gw;Gw;Zw as Green's functions for
Lw;?w;and 1w respectively, as follows:
Gw D
X
i>0
1
i i 
T
i ;
Gw D
X
i>0
1
ii
T
i ;
Zw D T  12 GwT 12 :
The above denitions of Gw and Gw are equivalent to the following relations:
GwLw D LwGw D I   0 T0 and Gw 0 T0 D 0;
Gw?w D ?wGw D I  0T0 and Gw0T0 D 0;
34
where
0T0.x;y/D
pd
G.x/dG.y/P
x2G dG.x/
;
and
 0 T0.x;y/D 1j G j:
Also
Zw1w D .T  12 GwT 12/.T  12 ?wT 12/
D T  12 .I  0T0/T 12
D I   DP
x2G dG.x/
and ZwD D 0;
where D.x;y/D dG.y/:
In the case where the graph has a boundary, it is easier to dene its Green's function.
Let GS be a subgraph of a connected graph G with non-empty boundary @S. Then Lw;S,
?w;S;and1w;S are invertible and the combinatorial Green's function Gw;S;the normalized
Green's function Gw;S, and the discrete Green's function Zw;S are dened as follows:
Lw;S Gw;S D Gw;S Lw;S D IS;
?w;SGw;S D Gw;S?w;S D IS;
1w;SZw;S D Zw;S1w;S D IS :
35
Using the diagonal matrix T, as before, we have the following relations:
Gw;S D T  12 Gw;ST  12 D Zw;ST 1;
Gw;S D T 12Gw;S D T 12 Zw;ST  12 ;
Zw;S D Gw;ST D T  12 Gw;ST 12:
There is a random walk interpretation of the discrete Green's function Zw;S corresponding
to the Dirichlet Laplace operator1w;S which is as follows. Let P Dpxybe the transition
probability matrix for the weighted transient random walk on S with absorbing states @S;
where the probability pxy of moving to state y from x is w.x;y/d
G.x/
. Then 1w;S D I   P
and from the fact that.I   P/ 1 D I C P C P2 C:::, it follows
Zw;S D I C P C P2 C::::
where Pn is the n-step transition probability matrix .
We have studied several explicit formulas for the Green's function. We now consider a
directmethodforevaluatingtheGreen'sfunctionforapathandacycle[23]. Forsimplicity,
we take the graph to be a standard graph, i.e.,w.x;y/D 1 if and only if x  y .
Example 1: Green's function for a path
Theorem 2.1.4
Let the vertex set Pn be denoted by S D f1;2;:::;ng with boundary @S D f0;n C1g.
36
Then its Green's function satises:
Gw;S.x;y/D 2n C1x.n C1  y/;
for 1  x  y  n:
Proof: Since 1w;S D?w;S D Lw;S=2; we have ?w;S Gw;S D I , and Gw;S?w;S D I .
Here we assume that 1  x < y  n:From ?w;S Gw;S D I, it follows that
1
2.2Gw;S.x;y/ Gw;S.x  1;y/ Gw;S.x C1;y//D 0:
From Gw;S?w;S D I , we have
1
2.2Gw;S.x;y/ Gw;S.x;y  1/ Gw;S.x;y C1//D 0:
with the condition that Gw;S.x;y/ D 0 if either x or y are the boundary point. Therefore,
we have
Gw;S.x;y/ Gw;S.x  1;y/ D Gw;S.x  1;y/ Gw;S.x  2;y/
D Gw;S.x  2;y/ Gw;S.x  3;y/
D :::::
D Gw;S.1;y/:
This implies that
Gw;S.x;y/D xGw;S.1;y/: .1/
37
Using similar argument, we have
Gw;S.1;y/D c.n C1  y/; .2/
for some constant c:Now, we use the fact that
1
2.2Gw;S.x;x/ Gw;S.x  1;x/ Gw;S.x C1;x//D 1
to get c D 2n C1 and Gw;S.x;x/D cx.n C1  x/:From (1) and (2), the result follows.
QED
Example 2 : Green's function for a cycle
Let the vertex set of the cycle Cn be denoted by f1;2;:::;ng: Then the Laplacians are
related by 1w D?w D Lw=2. Knowing the fact that a cycle is a boundary-less graph, the
Green's function Gw is determined by the following relationship which was studied before,
Gw?w D ?wGw D I   Jn;
and GwJ D 0;
where J is the n  n matrix with all entries 1: Before stating the theorem regarding the
Green's function for a cycle, we note the following facts regarding cycles. Since a cycle
is invariant under translations, then the values ?w.x;y/ and Gw.x;y/ depend only on the
distance j x   y j between x and y: Secondly, the distance between x and y on the cycle
38
can be measured by travelling in either direction. So, we dene
Gw.j x   y j/D Gw.n  j x   y j/:
The following theorem describes the Green's function for the cycle.
Theorem 2.1.5
Let n  3:Then the cycle Cn's normalized Green's function has the following form
Gw.x;y/D .y   x/
2
n   j x   y j C
.n C1/.n  1/
6n :
Proof: From Gw?w D?wGw D I   Jn and GwJ D 0;we have the recurrence:
2Gw.x;y/ Gw.x;y  1/ Gw.x;y C1/D
8>
><
>>:
2  2n if x D y
 2
n if x 6D y
or
2Gw.z/ Gw.z  1/ Gw.z C1/D
8>
><
>>:
2  2n if z D 0
 2
n if z >0
where z Dj x   y j :The condition GwJ D 0 implies that the sum of Gw across any row
must be zero, i.e.,
n 1X
zD0
Gw.z/D 0:
By considering the difference equation:
.Gw.z C1/ Gw.z// .Gw.z/ Gw.z  1/D 2n for z >0;
39
we conclude that Gw.z/is quadratic in z which we write as,
Gw.z/D z
2
n C Bz CC:
Knowing the fact that Gw.z/ D Gw.n   z/; we obtain B D  1. Now applying the
condition:
n 1X
zD0
Gw.z/D 0;
or
n 1X
zD0
.z   z
2
n /D nC:
Therefore,
C D .n C1/.n  1/6n :
Hence, we obtain the desired result.
QED
2.2 Dirichlet and Neumann boundary Value Problems
In this section, we are interested in solving the equation 1w f.x/ D g.x/ for x 2 S;
such that f satises Dirichlet or Neumann boundary conditions on the boundary @S. The
Dirichlet boundary value problem was solved by Chung [23] for standard graphs. (Al-
though, there is an error in her proof, her idea of the proof as a whole is correct). We will
extend her result to the graphs with arbitrary weights by using the same idea .
Theorem 2.2.1
40
Let GS be a connected and induced subgraph of G with a non-empty boundary@S and
 : @S ! R be a given function. Then the unique solution f to the Dirichlet boundary
value problem (DBVP): 8
>><
>>:
1w f.x/D 0; for x 2 S;
f j@SD
can be represented as:
f.x/D
X
y2S
X
z2@S
jSjX
iD1
1
i
S
i .x/
S
i .y/.z/
w.y;z/p
dG.x/dG.y/, for x 2 S:
Proof: By considering the function T 12 f.x/;we see that this function is the solution of the
following equation:
?w.T 12 f.x//D 0;
for x 2 S:We also dene the function f0 : S [@S ! R by
f0.x/D
8
>><
>>:
0 if x 2 S
.x/ if x 2 @S
then T 12 f  T 12 f0 is a Dirichletfunction on S[@S;since.T 12 f  T 12 f0/j@SD 0:Therefore,
we can write T 12 f   T 12 f0 as a linear combination of the eigenfunctionsSi of ?w;S :
T 12 f   T 12 f0 D
X
i
aiSi ;
which implies that
ai D hSi ; .T 12 f   T 12 f0/i:
41
Therefore, we have the following chain of equalities:
iai D hiSi ; .T 12 f   T 12 f0/i
D h?w;SSi ; .T 12 f   T 12 f0/i
D hSi ;T  12 Lw.f   f0/jSi
D hT 12Si ;1w.f   f0/jSi
D hT 12Si ;. 1w f0/jSi
D  
X
y2S
pd
G.y/i.y/
1
dG.x/
X
z2S
.f0.y/  f0.z//w.x;z/
D
X
y2S
X
z2@S
1p
dG.y/
S
i .y/.z/w.y;z/:
Therefore,
ai D 1
i
X
y2S
X
z2@S
1p
dG.y/
S
i .y/.z/w.y;z/:
Since we have,
.T 12 f   T 12 f0/.x/D
X
i
1
i
X
y2S
X
z2@S
1p
dG.y/
S
i .y/.z/w.y;z/
S
i .x/;
we arrive at the following conclusion. Namely,
f.x/ D
X
y2S
X
z2@S
jSjX
iD1
1
i
S
i .x/
S
i .y/.z/
w.y;z/p
dG.x/dG.y/; for x 2 S:
QED.
42
By dening the function B : S ! R as
B.y/D
X
z2@S
.z/w.y;z/d
G.y/
;
we can rewrite f as
f.x/D hGw;S.x;:/;BiS ; for x 2 S;
wherethenotationh;iS isthestandardinnerproductin Rn;i.e.,hf;giS DPx2S f.x/g.x/:
Notethatthevalueof B.y/dependsonlyonthevalueof on@S:Inotherwords, B.y/D
0 for all y 2 Sn@0S: Also, two different boundary conditions 1 and 2 may give rise to
the same solution f as long as B1 D B2 . By rewriting f.x/ D hGw;S.x;:/;Biy2S
as a matrix multiplication, i.e., f D Gw;SB; the Dirichlet boundary value problem is
equivalent to the following equation:
1w;S f D B on S:
This relationship will allow us to identify uniquely the boundary values from a harmonic
function f which satises 1w f.x/ D 0; for x 2 S: The next theorem characterizes the
harmonic functions with a set of singularities in a subgraph with non-empty boundary.
Theorem 2.2.2
Let GS be a connected induced subgraph of a graph G D.V;E/such that V D S[@S.
If ? 6D T  S then every f : V ! R satisfying
1w f.x/D 0; x 2 SnT
43
can be written uniquely as
f.x/D h.x/C
X
y2T
Gw;S.x;y/1w f.y/; x 2 V ;
where h is a harmonic function on S with the same boundary values as f , i.e., h j@SD
f j@S :
Proof: For x 2 S [@S, dene f1 and h as
f1.x/ D
X
y2T
Gw;S.x;y/1w f.y/;
h.x/ D f.x/  f1.x/:
Then h j@SD f j@S :And for each x 2 S;
1wh.x/ D 1w f.x/ 1w f1.x/
D 1w f.x/ 1w
 X
y2T
Gw;S.x;y/1w f.y/
!
D 1w f.x/ 1w
 X
y2T
jSjX
iD1
1
ii.x/i.y/1w f.y/
s
dG.y/
dG.x/
!
D 1w
 
f.x/ 
X
y2T
jSjX
iD1
1
i
i.x/p
dG.x/i.y/1w f.y/
p
dG.y/
!
D 1w
 
f.x/ 
X
y2T
.x;y/1w f.y/
!
D 0:
Hence h is a harmonic function. The uniqueness is evident.
QED
The following theorem formulates the solution to a nonhomogeneous Dirichlet bound-
44
ary value problem which is a consequence of the Theorem 2.2.1. We will state this without
proof.
Theorem 2.2.3
The solution to the following Dirichlet boundary value problem:
8
>><
>>:
1w f.x/D g.x/; x 2 S
f j@SD
is given by
f.x/D hGw;S.x;:/;BiS ChGw;S.x;:/;giS:
We will now study the necessary and sufcient condition for the existence of the solu-
tion to the Neumann boundary value problem (NBVP). The next theorem discusses these
conditions.
Theorem 2.2.4
Let GS be an induced subgraph of a graph G D.V;E/such that V D S . For the real
valued functions f : S ! R ; g : S ! R;and : @S ! R;the necessary and sufcient
condition for the solution to the NBVP
8
>><
>>:
1w f.x/D g.x/; x 2 S
P
y2S.f.z/  f.y//
w.z;y/
dGS.z/ D .z/; z 2@S
.1/
to exist, is
Z
S
g.x/dG.x/D  
Z
@S
 .z/dGS.z/:
45
In this case, the solution is given by
f.x/D a0 ChZw0.x;:/;giS ChZw0.x;:/; i@S ;
where a0 is an arbitrary constant and Zw0 is the Green's function with respect to the fol-
lowing weight function,w0 :
w0.x;y/D
w.x;y/ if either x or y are in S
0 otherwise.
Proof: We associate G with the following weight function,w0 :
w0.x;y/D
w.x;y/ if either x or y are in S
0 otherwise.
Then it is easily seen that d0G0.z/ D dGS.z/ for z 2 @S and d0G0.x/ D dGS.x/ for x 2 S
where d0G0.x/is the degree of the vertex x with respect tow0 . Assume thatRS g.x/dG.x/D
 R@S .z/dGS.z/:Hence, the equation (1) can be written as:
8
>>><
>>>:
P
y2S[@S.f.x/  f.y//
w.x;y/
d0G0.x/ D g.x/; x 2 S
P
y2S[@S.f.z/  f.y//
w.z;y/
d0G0.z/ D .z/; z 2@S
We can combine the above two equations into one equation to obtain
X
y2S[@S
.f.x/  f.y//w.x;y/d0
G0.x/
D9.x/; x 2 S [@S ;
46
where,
9.x/D
8
>><
>>:
g.x/; x 2 S
 .x/; x 2@S
Therefore, NBVP is equivalent to
1w f.x/D 9.x/; for x 2 S:
By the Theorem 2.1.1, we have:
f.x/ D a0 ChZw0.x;:/;9iS
D a0 C
X
y2S
Zw0.x;y/9.y/
D a0 C
X
y2S
Zw0.x;y/g.y/C
X
y2@S
Zw0.x;y/ .y/
D a0 ChZw0.x;:/;giS ChZw0.x;:/; i@S :
where a0 is an arbitrary constant. The converse is trivial.
QED
The above theorem shows that the solution to NBVP is uniquely determined by the
Neumann data on the boundary of the graph up to an additive constant. Therefore, we get
a unique solution once the value of f at some special vertex in S is dened.
47
2.3 Inverse Conductivity Problem on the Network
In this section, we study the inverse conductivity problem on the network (graph) S with
non-empty boundary. The idea is to recover the conductivity w of the graph by using an
input-output map, for example the Dirichlet data induced by the Neumann data ( Neumann
to Dirichlet map), with one boundary measurement. This Neumann to Dirichlet map is
suggested by the previous section's result. As we have seen for a function  : @S ! G
withR@S .z/dGS.z/D 0;the Neumann boundary value problem:
8>
><
>>:
1w f.x/D 0; x 2 S
P
y2S.f.z/  f.y//
w.z;y/
dGS.z/ D .z/; z 2@S
has a unique solution up to an additive constant. Therefore the Dirichlet data (the boundary
value of f ) is well-dened up to an additive constant. But even though we are given all
these data on the boundary, we are not guaranteed, in general, to be able to identify the
conductivityw uniquely. To illustrate this, we consider the following example:
Example 1
Consider a graph G D .S;E/ where S D f1;2;3g forms a cycle and @S D f0;4g has
the following weight conditions:
w.0;1/D 1 andw.0;k/D 0; for k D 2;3;4
and
w.3;4/D 1 andw.k;4/D 0; for k D 0;1;2:
48
Let f : S [@S ! R be a function satisfying 1w f.x/D 0;k D 1;2;3:Assume that
f.0/D 0; f.1/D 1; f.2/D unknown; f.3/D 3; f.4/D 4
therefore, the boundary data f j@S; @f@wn j@S;andw j@S@0S are known. In fact
@f
@wn.0/ D f.0/  f.1/D  1
@f
@wn.4/ D f.4/  f.3/D 1
The problem is to determine
w.1;2/D x;w.2;3/D y;w.1;3/D z; and f.2/:
From 1w f.x/D 0;for x D 1;2;3;we have:
f.1/ D f.0/C xf.2/C3z1C x C z D 1
f.2/ D xf.1/C yf.3/x C y
f.3/ D xf.1/C yf.2/C f.4/z C y C1 D 3
The above system is equivalent to
49
x.y  1/C y.x  1/C2z.x C y/ D 0
x C3y
x C y D f.2/: .1/
It is obvious that the above system has innitely many solutions. Assuming z D 0; i.e.,
disconnect the edge between 1 and 3, we see that the above system reduces to
1
x C
1
y D 2
x C3y
x C y D f.2/;
wherethereareinnitelymanypairs.x;y/ofnonnegativenumberssatisfyingtheequation.
However, if we impose the following constraints
x  1; y  1; and z  0;
then the equation (1) yields a unique triple solution x D 1; y D 1; z D 0 and f.2/ D 2:
Motivated by this example, we see that there must be certain monotonicity conditions im-
posed on the weights to yield the global uniqueness results. The following theorem is
due to Berenstein and Chung [6]. For the sake of completeness, we present its proof.
Theorem 2.3.1
Letw1andw2 be weights withw1  w2 on S  S and fi : S [@S ! R be functions
50
for i D 1;2 satisfying:
8
>>><
>>>:
1wi fi.x/D 0; x 2 S
@f
@win.z/D
P
y2S.f.z/  f.y//
wi.z;y/
dGS;wi.z/ D .z/; z 2@S
for a given function  : @S ! R with R@S .z/dGS;wi.z/ D 0; where dGS;wi.z/ is the
relative degree with respect to the weightwi and S :Furthermore, we assume that
1/w1.z;y/Dw2.z;y/on@S @0S
2/ f1 j@S D f2 j@S Then
we have:
f1 D f2 on S [@S
w1.x;y/ D w2.x;y/whenever f1.x/6D f1.y/or f2.x/6D f2.y/; for x;y 2 S:
To prove this theorem, we use the method of energy functional which is mostly used for
nonlinear partial differential equations. For a function :@S ! R;we dene a functional
by
Iw[h] D
Z
S[@S
1
4 j rwh j
2  hg

.x/dGw.x/
for every function h in the set
A D fh : S [@S ! R j h j@SDg;
which is called the admissible set. In the continuous case, there is a well known Dirichlet
51
principle which states that the energy minimizer in the admissible set is a solution of the
Dirichlet boundary value problem. In the discrete version, there is a similar result which
we will formulate in the next lemma.
Lemma 2.3.2 (Dirichlet's Principle) Assume that f : S[@S ! R is a solution to the
equations 8
>><
>>:
1w f.x/D g for x 2 S
f j@SD
then
IwfD min
h2A
Iw[h]:
Conversely, if f 2 A such that IwfD minh2A Iw[h] then f is the unique solution to
the above DBVP.
Proof: Let h be function in A:By the Theorem 1.1.2, Chapter 1, we have
0 D
Z
S[@S
.1w f   g/.f   h/.x/dGw.x/
D
Z
S[@S
.1w f.f   h/  g.f   h//.x/dGw.x/
D
Z
S[@S
1
2..rw f/:rw.f   h//  g.f   h/

.x/dGw.x/
D 12
Z
S[@S
j rw f j2 .x/dGw.x/  12
Z
S[@S
..rw f/:.rw.f   h///.x/dGw.x/
 
Z
S[@S
g.f   h/.x/dGw.x/:
52
Therefore, we have
Z
S[@S
1
2 j rw f j
2  gf

.x/dGw.x/
D
Z
S[@S
1
2..rw f/:.rwh//  gh

.x/dGw.x/
D 12
X
x2S[@S
X
y2S[@S
.f.x/  f.y//.h.x/  h.y//w.x;y/
 
Z
S[@S
.gh/.x/dGw.x/
 12
X
x2S[@S
X
x2S[@S
.f.x/  f.y//2 C.h.x/  h.y//2
2 w.x;y/
 
Z
S[@S
.gh/.x/dGw.x/
D 14
Z
S[@S
j rw f j2 .x/dGw.x/C 14
Z
S[@S
j rwh j2 .x/dGw.x/
 
Z
S[@S
.gh/.x/dGw.x/:
Therefore, it follows that
Z
S[@S
1
2 j rw f j
2  gf

.x/dGw.x/ 
Z
S[@S
1
4 j rwh j
2  gh

.x/dGw.x/;
or
Iwf Iw[h]; h 2 A:
Since f 2 A;we have:
IwfD min
h2A
Iw[h]:
To prove the converse, LetT be the characteristic function on T, the subset of vertices in
53
S;Then f CT 2 A for each real number;sinceT D 0 on@S:Then
Iw f CT D
Z
S[@S
1
4 j rw f CrwT j
2  .f CT/g

.x/dGw.x/
D 14
Z
S[@S

j rw f j2 C2rw frwT C2 j rwT j2

.x/dGw.x/
 
Z
S[@S
..f CT/g /.x/dGw.x/:
Since the quantity Iw f CTis minimum when D 0;therefore,
d.Iw f CT/
d jD0D 0;
Hence
0 D 12
Z
S[@S
.rw f:rwT/.x/dGw.x/ 
Z
S[@S
.Tg/.x/dGw.x/
D
Z
S[@S
.T.1w f   g//.x/dGw.x/
D
X
x2T
.1w f   g/.x/dGw.x/:
By taking T as a singleton set fxg;for x 2 S , we obtain the desired result, namely
1w f.x/D g.x/:
We will use now the above lemma to prove the Theorem 2.3.1. We may assume that the
boundary nodes are not connected by an edge since by lettingwi.x;y/D 0 for x;y 2@S;
54
the Theorem 2.3.1 will be unchanged. Now, by letting :@S ! R be a function such that
 D f1 j @S D f2 j@S;
we dene Iw1 by:
Iw1 [h] D 14
Z
S[@S

j rwh j2

.x/dGw1.x/;
for every h in the admissible set
A D fh : S [@S ! R j h j @S Dg:
Therefore, by the Theorem 1.1.2 of Chapter 1, we have:
Iw1 [h] D 12
Z
S[@S
h.x/1w1h.x/dGw1.x/
D 12
Z
S
h.x/1w1h.x/dGw1.x/C 12
Z
@S
h.x/1w1h.x/dGw1.x/:
Furthermore, for z 2@S;we have
1w1 f1.z/D 1w2 f2.z/:
It follows from the monotonicity condition of the weights, i.e.,w1 w2 that
Iw1 f1 D 12
Z
S
.f11w1 f1/.x/dGw1.x/C 12
Z
@S
.f11w1 f1/.x/dGS;w1.x/
55
D 12
Z
@S
.f11w1 f1/.x/dGS;w1.x/
D 12
Z
S
.f21w2 f2/.x/dGS;w2.x/ C 12
Z
@S
.f21w2 f2/.x/dGS;w2.x/
D 12
Z
S[@S
.f21w2 f2/.x/dGS;w2.x/
D 14
Z
S[@S
j rw2 f2 j2 .x/dGS;w2.x/
 14
X
x2S[@S
X
y2S[@S
f
2.x/  f2.y/
2w
1.x;y/; sincew1 w2
D 14
Z
S[@S
j rw1 f2 j2 dGw1.x/D Iw1 f2:
Since f1 isthesolutiontotheDBVP,bytheDirichletprinciple f1 mustminimizetheenergy
functional. On the other hand, we just proved that Iw1 f1  Iw1 f2, therefore f1 D f2
on S[@S:Now, bytaking f D f1 D f2 on S[@S andthefactthat Iw1 f1D Iw2 f2;we
get
X
x2S[@S
X
y2S[@S
f.x/  f.y/2w
1.x;y/D
X
x2S[@S
X
y2S[@S
f.x/  f.y/2w
2.x;y/:
or equivalently
X
x2S[@S
X
y2S[@S
f.x/  f.y/2w
1.x;y/ w2.x;y/
D 0:
Hence,
w1.x;y/Dw2.x;y/; if f1.x/6D f1.y/or f2.x/6D f2.y/:
QED
From the proof of the above theorem, we see that if f1 and f2 are injective functions
56
then we are able to show the uniqueness of weights, i.e, w1.x;y/ D w2.x;y/ on S  S:
For a special class of graphs, for instance, paths, it is easy to see that harmonic functions f1
and f2 are injective and hence all the weights are identied. But, in general, most graphs
do not admit an injective solution to either the DBVP or the NBVP. The objective of the
next theorem is to impose an extra condition to yield uniqueness of weights. To better
understand the idea of the next theorem, we examine the following example.
Example 2
Consider S D f1;2;3;4;5;6g with @S D f0;7g and the following weight conditions:
w1.0;y/ D
8>
><
>>:
1 if y D 1
0 otherwise
w1.1;y/ D
8
>><
>>:
1 if y D 0 and 2
0 otherwise
w1.2;y/ D
8>
><
>>:
1 if y D 1; 3, and 4
0 otherwise
w1.3;y/ D
8
>><
>>:
1 if y D 2; 4, and 5
0 otherwise
w1.4;y/ D
8
>><
>>:
1 if y D 2; 3, and 5
0 otherwise
57
w1.5;y/ D
8
>><
>>:
1 if y D 3; 4, and 6
0 otherwise
w1.6;y/ D
8>
><
>>:
1 if y D 5; 6, and 7
0 otherwise
w1.7;y/ D
8
>><
>>:
1 if y D 6
0 otherwise
Andw2 Dw1 everywhere exceptw2.3;4/D k;k  1:Thusw1 w2 throughout S [@S:
Dene f : S [@S ! R by
f.0/ D a; f.1/D a  b; f.2/D a  2b; f.3/D f.4/D .a Cc/ .b Cd/2 ;
f.5/ D c  2d; f.6/D c  d; f.7/D c;
where a; b; c; d are any real numbers. It can be seen that f is a harmonic function with
respect to both weights,w2;w1;Namely,
1w1 f.x/D1w2 f.x/D 0; for x 2 S :
From the Dirichlet and the Neumann boundary data, we have:
f.0/ D a; f.7/D c; @f@
w1
.0/D @f@
w2
.0/D f.0/  f.1/D b; and
@f
@w1.7/ D
@f
@w2.7/D f.7/  f.6/D d :
58
We observe that f is uniquely determined by these data regardless of the weights. So
w2.3;4/ D k cannot be identied. But if we assume that the boundary values, f.0/ D
a > 0;and f.7/ D c > 0 then by the maximum principle, f being a harmonic function,
we will have f.x/>0 for all x 2 S [@S :Furthermore, if we suppose that
Z
S
f.x/dGw1.x/D
Z
S
f.x/dGw2.x/;
then
Z
S
f.x/dGw1.x/D 2 f.1/C3 f.2/C3 f.3/C3 f.4/C3 f.5/C2 f.6/;
and
Z
S
f.x/dGw2.x/D 2 f.1/C3 f.2/C.2Ck/f.3/C.2Ck/f.4/C3 f.5/C2 f.6/:
Therefore,
f.3/C f.4/D k. f.3/C f.4//:
This forces k D 1, since f.3/C f.4/ 6D 0. Thus arriving at the conclusion that we have
the uniqueness of weights. Using these conditions, we will improve Theorem 2.3.1 under
weaker conditions.
Theorem 2.3.3
Let w1 and w2 be weights with w1  w2 on S [@S  S [@S and fi be functions
59
satisfying for i D 1;2 8
>><
>>:
1wi fi.x/D 0; for x 2 S
@fi
@win.z/D .z/; for z 2@S
for a given function  : @S ! R such that R@S .z/dGS;wi.z/ D 0: Furthermore, if we
assume that
1/w1.z;y/Dw2.z;y/on@S @0S;
2/ f1 j@SD f2 j@S>0;
3/RS f1.x/dGw1.x/DRS f2.x/dGw2.x/:
Then we have
f1 D f2 on S;
and
w1 Dw2 on S  S:
Proof: By Theorem 2.3.1, f1 D f2 on S . So we dene f D f1 D f2 on S[@S . Since
f1 j@SD f2 j@S> 0, by Theorem 1.2.1 we must have f D f1 D f2 > 0 on S: It follows
from the condition
Z
S
f1.x/dGw1.x/D
Z
S
f2.x/dGw2.x/;
that we have
X
x2S
f.x/dGw1.x/D
X
x2S
f.x/dGw2.x/;
or
X
x2S
f.x/.dGw2.x/  dGw1.x//D 0: (1)
60
From the monotonicity condition of weights, i.e., w1.x;y/  w2.x;y/ on S  S and the
fact that weights are non-negative functions on S  S, we have
dGw1.x/ dGw2.x/:
Using the fact that f >0 on S;equation (1) implies that
dGw2.x/  dGw1.x/D 0; for x 2 S;
or
X
y2S
.w2.x;y/ w1.x;y//D 0; for x 2 S:
Sincew1 w2;we obtain the desired result.
QED
61
Chapter III
3 ThePhysicalInterpretationofTheDiscreteInverseCon-
ductivity Problem
In the previous chapter, we studied the inverse conductivity problem as a means for identi-
fying the inner structure of network by measurements made on the boundary. This method
was initially proposed by Curtis and Morrow [26, 27] later developed by Carlos Berenstein
into an important result in the domain of the discrete inverse conductivity problem [6]. The
physical interpretation of the weighted Laplacian which is used here for the discrete inverse
conductivity problem will be in terms of the chip-ring game. This is motivated in part by
communication network models in which chips represent packets or jobs and the bound-
ary nodes represent processors. Alternatively, the discretization of the inverse conductivity
problem demands a discretization of an electrical network as a physical interpretation.
The chip-ring game (CFG) is a discrete dynamical model used in Physics, Computer
Science, and Economics. It was introduced by Bjorner, Lovasz, and Shor in [11, 12].
The CFG is dened over an undirected graph G, called the support graph of the game.
A conguration of the game is a mapping s : V ! N that associates a weight to each
vertex, which can be considered as the number of chips stored in the vertex. The CFG
is a discrete dynamical model, with the following ring rule: If, when the game is in a
conguration s , a vertex v contains at least as many chips as its degree, one can transfer
a chip from v along each of its edges to the corresponding neighboring vertex. CFGs are
strongly convergent games [37], which means that, given an initial conguration, either the
62
game can be played forever, or it reaches a unique stable conguration (where no ring is
possible) independent on the order in which the vertices were red. If for a given nite
sequence of vertices of G, such that starting from s, this sequence of vertices is ready to
re to obtain a new conguration s0;then the conguration s0 is given by
s0.v/D s.v/  f.v/dG.v/C
X
f.u/w.u;v/;
where f.v/is the number of timesv occurs in the sequence, dG.v/is the degree ofv;and
w.u;v/is the weight or the number of edges connecting u tov. This is true because each
time v is red it loses dG.v/ chips, and each time u 6D v is red it gains w.u;v/ chips.
The relationship between s0and s can be written more concisely in terms of the weighted
Laplacian as follows:
s0 D s   Lw.f/:
CFG has been studied previously in terms of the classication of legal game sequences
[11, 12], critical congurations [7,8,9], and by use of the chromatic polynomial [8], the
Tutte polynomial [7,47], and matroids [48]. A parallel version of CFG, in which all ready
vertices re simultaneously, is studied in [35]. The chip-ring game is closely related to
self-organized criticality [4, 5], and the sandpile model [36].
The discrete conductivity problem studied in Chapter 2 requires that1w.f/D 0 on S:
This raises an interesting question of what the analogous condition in the context of CFG
would be. In other words, since this condition requires the absence of sinks and sources
in the interior of the graph, we would like to study a set of congurations that are stable.
63
Moreover, the necessary condition of R@S .z/dGS.z/ D 0 on the boundary of the graph
forces us to allow the number of chips to be negative.
We consider a new variant of the chip-ring game, in which chips are red in the game
from the boundary, removed from the game when they are red across a boundary, and
the number of chips can be negative. Chung and Ellis [17] called their own variation of
the chip-ring game, which is a special case of our version, the Dirichlet game. Their
version considers only positive number of chips in the interior of a simple graph and the
boundary nodes do not re chips into the interior vertices after the game reaches a stable
conguration. Because this difference is small we call our variant the Dirichlet game as
well. We would like to point out that we are liberal about the usage of names either calling
it Dirichlet game or simply CFG.
In this chapter, our objective is to obtain a bound on the length of the Dirichlet game,
that is, how long it will take for a conguration to reach a stable and recurrent congura-
tions, in terms of the initial number of chips in the game and the diameter of the graph. We
start with the preliminaries in the rst section of this chapter. The second section covers the
fundamentals of CFG. The set of critical groups are discussed in the third section. In the
fourth section, we explain how CFG is viewed as a discrete dynamical system. In Section
5, we discuss electrical networks in a naive way to attempt to understand the dynamics of
CFG intuitively. The sixth and seventh sections give a probabilistic approach to the prob-
lem of CFG and electrical networks to obtain a bound on the time for the network to reach
a stable conguration.
64
3.1 Introduction
The Dirichlet chip-ring game takes place in the setting of a connected graph G D.V;E/
with multiple edges such that V D S [@S where we call S the interior of G and @S the
boundary of G. Furthermore, we assume that the boundary nodes are not connected by any
edges, i.e., w.u;v/ D 0 if u;v 2 @S. An instance of the Dirichlet game on the graph G
starts with a number of chips on each of the vertices on the interior of G, where we allow
the number of chips to be negative. The following steps are the rules of the Dirichlet game:
1) Choose a vertex v in the interior of G which has more than dG.v/ chips, remove
dG.v/ chips from v and add w.u;v/ chips to each vertex u in the neighborhood of v;
NG.v/:Such a step is called ring the vertexv;
2) If there is no vertex v in the interior of G which has more than dG.v/ , then add
w.u;q/chips to each vertex u in NG.q/for every q in the boundary of G:In other words,
all the nodes in the boundary of G re simultaneously only when no ring is possible in
the interior of G,
3) Chips red from a vertex in the interior of G to a vertex in the boundary of G are
instantly processed and removed from the game.
A conguration s of the Dirichlet game is a function dened on the vertices such that
s.v/ is the number of chips in the vertex v: If s.v/  d.v/ for some v in the interior of
G, then we say that v is ready in s. If s.v/ < dG.v/ for all v in the interior of G; then
the boundary nodes are ready. Given a conguration s, a nite sequencev1;v2;v3;...;vk of
vertices is legal for s if v1 is ready in s, v2 is ready in the conguration obtained from s
after ringv1;etc.
65
A conguration s is said to be stable if s.v/< dG.v/for allv in the interior of G. It is
called recurrent if there is a non-empty legal sequence which leads to the same congura-
tion. And a conguration is called a critical conguration if it is both stable and recurrent.
ThefollowingtheoremsduetoBiggs[9]statethateverycongurationwilleventuallyreach
a critical conguration. For completeness, we state the proof with minor variations.
Theorem 3.1.1
For every conguration s, there is an upper bound on the length of a legal sequence of
rings that does not contain the vertices in the boundary nodes.
Proof: Recall that vertices in the boundary of G re only when no ring is possible
in the interior of G and processes any chips that re across the boundary nodes. Suppose
that we start with nite number of chips and there is a vertexv1 2 S that is red innitely
often. Let P Dv1;:::;vn be a path with multiple edges according to the weight of G fromv1
to some vertex vn 2 @S; where all the vertices of the path except vn belong to S: If some
vertex in P, sayvi, for some i  n   1;res innitely often, thenviC1 receives innitely
many chips and therefore, res innitely often also. Repeating this argument, we therefore
see that the vertex vn must process innitely many chips. This is a clear contradiction to
the fact that we started with a nite number of chips.
QED
Theorem 3.1.2
Let s be a conguration of the Dirichlet game: Then there is a critical conguration c
which can be reached by a legal sequence of rings starting from s.
Proof: By Theorem 3.1.1, if we start from s and re the vertices other than the bound-
ary nodes then we must eventually reach a conguration where no vertex in G is ready to
66
re except the boundary nodes, that is, a stable conguration. If we then re the boundary
nodes and repeat the process, we reach another stable conguration. This procedure can be
repeated as often as we would like to. Since the number of stable congurations is nite,
at least one of them must recur, and this is the critical conguration.
QED
3.2 Basic Theory of the Dirichlet Game
In the following sections, we present the fundamentals of CFG from [9, 17, 63]. These
results are still valid in our version of CFG with slight changes in the proofs. Suppose D
v1;v2;v3;...;vk is a nite sequence which is legal for the conguration s. Then we denote
the number of times v occurs in  by f.v/: As argued above, the relationship between s
and the conguration s0 which is obtained by applying  to s can be written in terms of
weighted Laplacian, i.e.,
s.v/ s0.v/D Lw.f.v//:
The CFG is based on the conuence property. If we start with a given conguration
s then there may be many different legal sequences starting from s; but they all lead to
the same outcome in some sense. The following lemma and theorem explain this more
precisely.
Lemma 3.2.1
Let  Dv1;:::,vk and 0 Dv01;:::;v0l be legal sequences for a conguration s. Then
67
there is a legal sequence D u1;:::;uj for s with the property that
f.u/D max.f.u/; f0.u//;
forallu in G.
Proof: Suppose the result is true for any positive integer less than kCl ( the sum of the
lengths of the two legal sequences for the conguration s):If k D 0 or l D 0 we are done
by setting D 0or D , respectively.
If v1 D v01, then we can apply the induction hypothesis to the conguration obtained
by applyingv1 on s with the sequencesv2;v3;:::;vk andv02;:::;v0l:
If v1 6D v01 and v1 does not occur in 0, then v1;v01;v02;:::;v0l is also legal for s. This
is because by starting with v1; we will be adding more chips to v01 and the sequence 0
was already legal for s. Now we can apply the induction hypothesis to the conguration
obtained by applyingv1 to s with the sequences v2;v3;:::;vk andv01;:::;v0l:
Ifv1 6Dv01 andv1 does occur in0, then by shifting the rstv1 to the start of the0, we
will have a new sequencev1;v01;:::v0i 1;v0iC1;:::;v0l which is still legal for s. We can now
apply the induction hypothesis to the conguration obtained by applying v1 to s with the
sequencesv2;v3;:::;vk andv01;:::;v0i 1;v0iC1;:::;v0l:
QED
Theorem 3.2.2. Conuence property
Let and0 belegalsequencesforthecongurations whichleadtonewcongurations
s1 and s2: Then there is a conguration s3 which is obtained from s1 and s2 by applying
legal sequences, respectively.
68
Proof: According to the above lemma, there is a legal sequence for the conguration
s where f.u/ D max .f , f0/. We can choose the initial part of  to be the same as
; and  would still be legal for s. Then the remaining subsequence of  will be legal
for s1: Similarly, there is a legal sequence 0 for the conguration s such that f0.u/ D
max .f.u/ , f0.u// and the initial part of 0would be the same as that in 0; and the
remaining subsequence of0will be legal for s2:By Laplace's equation, both and0 will
lead s to the same conguration s3 .
QED
Corollary 3.2.3
Using the same assumption as above, we have:
(a) If every vertex in  and 0 appears at most once then the conguration s3 can be
obtained by ring the vertices at most once.
(b) If the boundary nodes do not appear in both  and 0 and all the vertices appear
at most once, then s3 can be obtained by ring the vertices at most once and the boundary
nodes do not appear in this sequence of ring.
Proof: Part (a) follows from the simple observation that if f  1 and f0  1 then
f0  1: And part (b) follows from the fact if f.q/ D f0.q/ D 0; then f.q/ D 0; for
every boundary node q.
QED
69
3.3 Critical Conguration of the Dirichlet Game
Based on Berenstein and Chung's mathematical formulation of the discrete inverse conduc-
tivity problem, we require that1w.f/D 0 in the interior of the graph. This is a reasonable
assumption if one wants to detect the problem of inner structure of the network through
measurements made on the boundary of the graph. In the language of chip-ring game, we
require that the net ow or net ring in the interior of the graph to be zero. In other words,
we desire that the interior of the network be at a stable conguration. This is why the study
of set of stable and recurrent congurations of the Dirichlet game becomes important in
connection to the Berenstein and Chung's mathematical model of network tomography .
Lemma 3.3.1
Suppose  D v1;:::;vk is a legal sequence for a stable conguration s in which the
boundary nodes appear only once. Then every vertex in G appears at most once in:
Proof: Since s is stable, the boundary nodes must appear at the beginning of the ring
sequence . Let's suppose that some vertex appears more than once. Let v be the rst
vertex that appears more than once andvi be the second appearance ofv. Thenvi is ready
after v1;:::;vi 1 has been applied to s: According to Laplace's equation, the number of
chips onvi afterv1;:::;vi 1 is applied to s is
s.vi/  f.vi/dG.vi/C
X
u
f.u/w.u;vi/D s.vi/ dG.vi/C
X
u
f.u/w.u;vi/:
Sincevi appears exactly once inv1;:::;vi 1:The upper bound for the number of chips on
70
the vertexvi after the sequencev1;:::;vi 1 has been applied to s is
s.vi/ dG.vi/C
X
u2NG.vi/
f.u/w.u;vi/ s.vi/ dG.vi/CdG.vi/D s.vi/:
But since s is stable, the number of chips at the vertexvi, after the second appearance, will
be less than the degree ofvi. This contradicts the fact thatvi is ready for the second ring
time.
QED
Corollary 3.3.2
Let s be a stable conguration and Dv1;:::;vk be a legal sequence for s. Then every
vertex in G appears in at most as often as the boundary nodes.
Proof: Partition  D v1;:::;vk into parts where the boundary nodes appear at the
beginning of each part. Since s is stable, the boundary nodes must appear rst. After
applying the rst part of to s we will obtain a new stable conguration. This is because
the boundary nodes appear the second time in the second part. By applying Lemma 3.3.1
to each part, we obtain the result.
QED
The following result gives a necessary condition for a stable conguration to reappear.
Theorem 3.3.3
Let  D v1;:::;vk be a legal sequence for a stable conguration s such that after ap-
plying  to s we return to the conguration s. Then every vertex in G appears the same
number of times in:
Proof: It is easy to see that every vertex in G must appear in : Since s reappears
71
after applying, if a vertex does not re then it should not receive chips from neighboring
vertices. Therefore, if a vertex v in G does not appear in , then all neighboring vertices
do not appear in either. By the connectedness of G, none of the vertices of G appear in
, which is a contradiction. So all the vertices of G must appear in . Let v be a vertex
that appears a minimal number of times in and that is adjacent to a vertexv0 that appears
more often in thanv itself (otherwise, since G is connected all the vertices must appear
equally often). By Corollary 3.3.2, v cannot be a boundary node. After applying  to s,
v loses pdG.v/ chips and gains at least pw.u;v/ chips from each u in the neighborhood
ofv and, in fact, at least.p C 1/w.v;v0/chips fromv0;where p is the number of timesv
appears in. The lower bound on number of chips inv after applying is
s.v/  pdG.v/C
X
u
pw.u;v/Cw.v;v0/D s.v/Cw.v;v0/;
contradicting the fact that s should reappear after applying:
QED
Theorem 3.3.4
Let Dv1;:::;vk bealegalsequenceforacriticalcongurations suchthatafterapply-
ing to s, we get a stable conguration. If the boundary nodes appear exactly once in the
ring sequence, then every vertex in G appears exactly once and the resulting conguration
is s.
Proof: Since s is a critical conguration, there is a legal sequence of ring 0 D
v01;:::;v0l for s such that after applying 0 the conguration s is returned. By Theorem
3.3.3, every vertex in G must appear in0 the same number of times. And by Lemma 3.3.1
72
every vertex in G appears at most once in . This means that for allv in G
max.f.v/; f0.v//D f0.v/:
According to the Theorem 3.2.2, we can form a legal sequence whose vertices appear the
same number of times as in0:Therefore every vertex appears the same number times in
and applying to s will yield s again. Also, we can choose in such a way that the initial
part of will be the same as. Let0 be the part of after the initial part. Then0 is a
legal sequence for a stable conguration resulted from applying to s. Therefore, we have
a sequence in which each vertex appears equally often, and the initial part of is equal to
 in which each vertex appears at most once. In the remaining part,0, each vertex appears
at most as often as the boundary nodes. This is only possible if each vertex appears exactly
once in, and the resulting conguration after is being applied to s is s again.
QED
Theorem 3.3.5
Let s be a conguration of the Dirichlet game. Then there is a unique critical congu-
ration which can be reached by a legal sequence of rings.
Proof: By Theorem 3.1.2, one such critical conguration exists. Suppose c is the
rst critical conguration that is reached by the sequence of rings. Then by Theorem
3.3.4, once we activate the boundary nodes the rst stable conguration will be a critical
conguration which coincides with c. This proves the uniqueness.
QED
Corollary 3.3.6
73
Let c be a critical conguration. Then 0  c.v/ dG.v/ 1 for allv in the interior of
G:
Proof: The upper bound for c.v/ arises directly from the denition of critical cong-
uration. For the lower bound, by above theorem, there is a legal sequence such that every
vertex appears exactly once. vreceives only dG.v/chips when applying the legal sequence.
On the other hand, since v is red as well, there must be a moment when v holds at least
dG.v/. This is only possible if c.v/ 0:
QED
The above theorem shows that a critical conguration is in some sense a saturated state,
a state in which the network is neither in an active nor passive position. In other words,
the total net ow in the interior of network is zero. Theorem 3.3.4 also provides a way to
recognize the critical conguration. Once a stable conguration s is obtained, start with
the boundary nodes to form a legal sequence of ring, until another stable conguration s0
is obtained. By Lemma 3.3.1, this happens after at most n rings, where n is the number
of vertices in G. If s D s0, then s0 is a critical conguration, otherwise repeat the pro-
cedure starting with s0. The following theorem shows one can also recognize the critical
conguration by knowing whether every vertex has been red or not.
Theorem 3.3.7
Suppose s is an arbitrary conguration and Dv1;:::;vk is a legal sequence such that
when it is applied to s results in a stable conguration s0. If all the vertices appear at least
once in, then s0 is a critical conguration.
Proof: If all the vertices appear exactly once in;then the conguration s0 will be the
same as s by Laplace's equation. Since s0 is a stable conguration, so is s. This means that
74
s is a critical conguration. For the remaining cases, we use induction on k. Ifv1 appears
more than once then we apply the induction hypothesis to the conguration obtained by
applying v1 to s with the following legal sequence v2;:::;vk for this new conguration.
Therefore, assume that some vertex other than v1 appears more than once. Let vi be the
vertex in  that appears more than once and if vj is the second appearance of vi in 
then D v1;:::;vi 1;vi;viC1;:::;vj 1 appears at most once in:We consider two cases.
Assume rst that vi is not a boundary node. Since vi is ready after applying  to s, and
vi loses dG.vi/ chips and gains at most Puw.u;vi/ D dG.vi/ chips, vi must have been
ready before the application of  on s. Now apply the induction hypothesis to the con-
guration obtained by applying vi to s with the legal sequence of v1;:::;vi 1;viC1;:::;vk
in which each vertex appears at least once. For the second case, we assume vi is one of
the boundary nodes. Let s00 be the conguration obtained from s by adding w.v;q/ chips
to all v in the neighborhood of q for every q in the boundary of G: Then the sequence
0 D v1;:::;vi 1;vl;:::;vk;in which the vertices fromvi 1 tovl in are all the boundary
nodesandwereremovedfrom;isalegalsequencefors00:Wecannowapplytheinduction
hypothesis to s00 and0:Note that applying0 to s00 will result in the same conguration as
applying to s:
QED
3.4 Dirichlet Game as a Discrete Dynamical System
In order to dene time in a discrete sense, we have to nd a way to get from one con-
guration to another irrespective of choices of the legal sequence within one unit of time.
75
Suppose we start with an unstable conguration s. If  D v1;:::;vk and 0 D v01;:::;v0l
are two legal sequences such that all the vertices in the interior of G appear at most once
in each of the sequences and, moreover, k and l are as large as possible with this prop-
erty. Then, by the conuence property, there is a legal sequence whose vertices appear at
most once and the its initial part is  D v1;:::;vk. As k is the largest integer with the
property that no vertices appear more than once, this new sequence must be : By a sim-
ilar argument, there is a legal sequence whose vertices appear at most once and its initial
part is 0: Since l is the largest possible value with the property that no vertices appear
more than once, this new sequence must be0:By the conuence property, D v1;:::;vk
and 0 D v01;:::;v0l will lead s to the same conguration. The above argument leads us to
introduce the following denition:
Let s be a conguration, then a cycle for s is a legal sequence Dv1;:::;vk such that
(a) If the boundary nodes do not appear in;all the vertices appear at most once, and
k is as large as possible.
(b) If s is a stable conguration, then the boundary nodes appear in the rst part of
 Dv1;:::;vk and all the vertices appear at most once, and k is as large as possible.
Obviously, the cycles are not uniquely determined by s, but they all lead s to the same
conguration. Let s be the initial conguration. We call s the conguration at time 0,
denoting it by s0: If st is the conguration at time t, then the conguration at time t C
1 is dened as conguration obtained by applying a cycle to st: The following theorem
describes the dynamics of the CFG.
Theorem 3.4.1
Let s0 be the starting conguration of a Dirichlet game on the connected graph G. Then
76
for everyv in the interior of G and positive integer t we have:
(a) if st.v/<0, then st.v/ st0.v/ dG.v/ 1 for all t0  tI
(b) if 0  st.v/ dG.v/ 1, then 0  st0.v/ dG.v/ 1 for all t0  tI
(c) if st.v/ dG.v/, then 0  st0.v/  st.v/for all t0  t:
Proof: Let v be in the interior of G, t a positive integer, and let  be a cycle for
st: Since every vertex in the interior of G appears at most once in ;v receives at most
P
uw.u;v/D dG.v/chips when applying the cycle to st:On the other hand, ifvis red,
it loses dG.v/chips.
If st.v/ < 0; then v is not red in the cycle ; therefore, st.v/  stC1.v/  st.v/C
dG.v/ dG.v/:This proves part (a).
If 0  st.v/ dG.v/ 1;thenv gains at most dG.v/chips. Ifv is red in the cycle
then it loses dG.v/chips. Hence, we have 0  stC1.v/  dG.v/  1:And ifv is not red
then we immediately have 0  stC1.v/ dG.v/ 1. This proves part (b).
If st.v/ dG.v/;thenv is certainly red in the cycle, hence it loses dG.v/chips but
gains at most dG.v/ chips. So we have 0  stC1.v/  st.v/ which proves part (c). The
result follows by applying induction on k where t0 D t Ck:
QED
One of the difculties in analyzing the discrete dynamics of the Dirichlet game arises
when a vertexv is at a conguration s, such that 0  st.v/  dG.v/  1:In this case, it is
not completely determined that the vertexvwill re after applying a cycle to s. Depending
on the structure of the network and the number of chips at every vertex, the ring might or
might not occur. The main tool in analyzing the dynamics of the Dirichlet game will be its
continuous version, which is the electrical network. Recall the following equation for the
77
Dirichlet game:
stC1.v/ st.v/D  ft.v/dG.v/C
X
u
ft.u/w.u;v/;
where ft.v/is either 1 or 0 depending on whethervres or not at time t:In the continuous
version, stC1.v/ st.v/is substituted by the differential of s, s.v/is regarded as the amount
of charge at the vertexv;which could be positive or negative, and ft.v/D1 or 0 depending
on the charges being positive or negative at the vertexv. And when there is a zero charge
at vertexv, we would like to have Kirchhoff's law applied to the vertexv. In other words,
since the continuous dynamics obey the following differential equation:
ds
dt D  ft.v/dG.v/C
X
u
ft.u/w.u;v/;
we require that if a vertexv has zero charges, i.e, st.v/ D 0 then st0.v/ D 0 for all t0  t:
This results in dsdt D 0 or
 ft.v/dG.v/C
X
u
ft.u/w.u;v/D 0;
whichisexactlytheKirchhoff'slaw.
78
3.5 Basic Theory of Electrical Networks
As in the Dirichlet game we assume we are given a nite, undirected, connected graph
with boundary nodes. At time t we assume at each vertex v in the interior contains a
certain amount of charge rt.v/, which can be negative. In the continuous version, ring is
denoted by't.v/and the value of't.v/is determined by the following rule:
1) If rt.v/<0 forv in the interior of G then't.v/D 0;
2) If rt.v/>0 forv in the interior of G then't.v/D 1;
3) If rt.v/D 0 forvin the interior of G then't.v/is obtained according to Kirchhoff's
law, i.e.,
't.v/D
X
u
't.u/w.u;v/d
G.v/
:
4) If rt.u/> 0 for some u in the interior of G then't.q/D 0 for all q in the boundary
of G,
5) If rt.u/ 0 for all u in the interior of G then't.q/D 1 for all q in the boundary of
G.
Based on the theory of electrical networks [13, 26, 27, 34], 't is uniquely determined
by the above rules.
We dene a vertexv as being passive if rt.v/<0;saturated if rt.v/D 0;and active if
r.v/ > 0: From the above rules, it is obvious that the boundary of G is active if no other
vertices are active, and passive otherwise. For a certain conguration r, we call Var the set
of active vertices, and V pr the set of passive vertices.
Theorem 3.5.1
79
For a conguration r as above;we have 0 't.v/ 1;for all verticesv.
Proof : Suppose there exists a vertexv such that't.v/> 1:Choosev such that't.v/
is maximum. Because of the rule (2),vcannot be in the boundary of G. From the equation
't.v/ D Pu't.u/w.u;v/d
G.v/
; since 't.u/  't.v/ for all u in the neighborhood of G, we
therefore have
dG.v/'t.v/ D
X
u
't.u/w.u;v/

X
u
w.u;v/'t.v/D dG.v/'t.v/:
The above inequality is forced to be an equality everywhere. Hence
't.v/D
X
u
't.u/w.u;v/d
G.v/
;
for all u in the neighborhood ofv. Since't.v/is maximum,'t.v/D't.u/for all u in the
neighborhood ofv:By repeating the same argument for the vertices neighboring u, and the
fact that G is connected, we have 't.u/ D 't.v/ for all u in G. But this contradicts the
ow 't.q/ D 1 for q in the boundary of G. By similar argument, we have 't.v/  0 for
allv in G:
QED
ThefollowingtheoremshowsthatthedynamicsofthecontinuousversionoftheDirich-
let game is almost the same as the discrete one.
Theorem 3.5.2
For anyv in the interior of G and t  0 we have
80
(a) If rt.v/D 0;then rt0.v/D 0 for all t0  tI
(b) If rt.v/<0;then rt.v/ rt0.v/ 0 for all t0  tI
(c) If rt.v/>0;then 0  rt0.v/ rt.v/for all t0  t:
Proof:
If rt.v/ D 0; then 't.v/ D Pu't.u/w.u;v/d
G.v/
: Therefore, by the differential equation
drt
dt D  't.v/dG.v/C
P
u't.u/w.u;v/;
drt
dt D 0:Hence we must have rt0.v/D 0 for all
t0  t:This proves part (a).
If rt.v/< 0;then't.v/ D 0. By Theorem 3.5.1, 't.u/  0 for all u in G. Using the
equation drdt D  't.v/dG.v/CPu't.u/w.u;v/;we have
dr
dt D  0.dG.v//C
X
u
't.u/w.u;v/ 0:
Hence rt.v/  rt0.v/ for all t0  t as long as rt0.v/ < 0: Once we reach rt0.v/ D 0; we
obtain rt00.v/D rt0.v/D 0 for all t00  t0 by part (a). This proves part (b).
If rt.v/> 0; then 't.v/ D 1. By Theorem 3.5.1, 't.u/  1 for all u in G. Using the
equation,
dr
dt D  1.dG.v//C
X
u
't.u/w.u;v/
  dG.v/C
X
u
w.u;v/  0;
we have rt0.v/  rt.v/ for all t0  t as long as rt0.v/> 0: Once we reach rt0.v/ D 0; we
get rt00.v/D rt0.v/D 0 for all t00  t0 by part (a). This proves part (c).
QED
81
We say a conguration rt is an active conguration, if there is a vertexv in the interior
of G such that rt.v/>0:Otherwise, it is called inactive or passive. Note that the boundary
nodesareactiveinaninactiveconguration. Acongurationiscalledrecurrentif drt.v/dt D
0; for all v in the interior of G. We consider a recurrent conguration, as analogous to a
critical conguration for the Dirichlet game.
Although we have different critical congurations in the Dirichlet game, in electrical
networks there is only one recurrent conguration which has zero charge at every vertex in
the interior of the graph.
Theorem 3.5.3
Foraconnectedgraph G, ifrt isarecurrentconguration, thenrt.v/D 0and't.v/D 1
for allv in the interior of G:
Proof:
Suppose there is a vertexvin the interior of G such thatrt.v/>0. Then't.v/D 1 and
't.q/ D 0 for all q, the boundary nodes: By the connectedness of G, we can choose v so
that there would be a vertex u in the neighborhood ofv with't.u/<1:From the equation
drt.v/
dt D  't.v/dG.v/C
X
u
't.u/w.u;v/;
we obtain drt.v/dt < 0:Hence rt cannot be a recurrent conguration. Furthermore, rt.v/
0 for all v in the interior of G. Now, if there is a vertex v in the interior of G such that
rt.v/ < 0 then 't.q/ D 1 for all boundary nodes, q: By the connectedness of G, we can
choosev so that there would be a vertex u in the neighborhood ofv with't.u/< 1:From
the equation, drt.v/dt D  't.v/dG.v/CPu't.u/w.u;v/; we obtain drt.v/dt > 0: Hence
82
rt cannot be a recurrent conguration. We conclude that the only recurrent conguration is
the conguration with rt.v/ D 0 for allv in the interior of G:It is obvious that't.v/ D 1
for allv in the interior of G.
QED
We now study the connection between the Dirichlet game and electrical networks. For
a starting conguration r0 of the electric network and a positive real number t, dene
8t.v/D
Z t
0
'x.v/dx;
because 0  'x.v/  1 , we have 0  8t.v/  t; for all v: Similarly, for a starting
conguration s0 and a positive integer t;dene
zt.v/D
tX
xD1
fx.v/;
since fx.v/ D 0 or 1;therefore, we again have 0  zt.v/  t:From the dynamics of the
Dirichlet game and the electric network, we have
st.v/ s0.v/ D  dG.v/zt.v/C
X
u
w.u;v/zt.u/D  Lw.zt.v// .1/
rt.v/ r0.v/ D  dG.v/8t.v/C
X
u
w.u;v/8t.v/D  Lw.8t.v// .2/
The following two theorems describe the connections between the Dirichlet game and the
electrical networks.
Theorem 3.5.4
83
Let s0 be a stable conguration of the Dirichlet game. Dene r0 to be the starting
conguration of the electric network by r0.v/ D s0.v/   .dG.v/   1/ for all v in the
interior of G. If rT is a recurrent conguration then for an integer t > T , st is a critical
conguration of the Dirichlet game.
Proof:
By Theorem 3.3.7, it sufces to show that all the interior vertices will re within the
time interval between 0 and t; i.e., zt.v/ > 0 for all vertices v in G: This is done by
showing that8t.v/ zt.v/for all verticesvin G:Since rt is a recurrent conguration for
t  T , we havet.v/> 0 for t > T and for all verticesv in G. Now, suppose that there
exists a vertex v such that 8t.v/  zt.v/ > 0. Furthermore, we assume that the choice
of v makes the quantity 8t.v/  zt.v/ maximum. From zt.q/ D t and 8t.q/ D t, we
conclude that v cannot be one of the boundary nodes. From Equations (1) and (2) above
(see p. 83) and the fact that8t.u/ zt.u/8t.v/ zt.v/for all u in G, we have:
rt.v/ st.v/ D r0.v/ s0.v/ .Lw.8t.v//  Lw.zt.v///
 r0.v/ s0.v/ 
 
dG.v/ 
X
u
w.u;v/
!
.8t.v/ zt.v//
D r0.v/ s0.v/:
Therefore,rt.v/ st.v/ .dG.v/ 1/:Now, sincert.v/D 0weobtainst.v/dG.v/ 1:
We also have st.v/  dG.v/  1;i.e., st.v/is a stable conguration. Hence, we must have
equality everywhere in the above inequality. In other words, 8t.u/  zt.u/ D 8t.v/ 
zt.v/ for all u in the neighborhood of v. Repeat this argument for the neighborhood of
u. By the connectedness of G; we nally get 8t.q/ zt.q/> 0 for all q, the boundary
84
nodes. But this is clearly a contradiction.
QED
Theorem 3.5.5
Suppose s0, the initial conguration of the Dirichlet game, is not a stable conguration
and dene r0 to be the initial conguration of the electrical network as r0.v/ D s0.v/ for
allv in the interior of G. If rt is a passive conguration for an integer t then st is a stable
conguration of the Dirichlet game.
Proof: Suppose st is not a stable conguration. In this case, we claim that 8t.u/ 
zt.u/ for all vertices u in G. Now, choose a vertex x such that st.x/  dG.x/; then
zt.x/D t and8t.x/ t:By the above claim, we have8t.x/ zt.x/D 0. Therefore,
rt.x/ st.x/ D r0.x/ s0.x/  Lw.8t.x/ zt.x//
 r0.x/ s0.x/D 0:
Hence,rt.x/st.x/:But this clearly contradicts the fact thatrt.x/ 0 and st.x/ dG.x/:
Now, we will prove the claim. Suppose there exists a vertex v such that 8t.v/ < zt.v/.
Furthermore, we assume that the choice ofv makes the quantity zt.v/ 8t.v/maximum.
Since st is not a stable conguration we have zt.q/ D 0 and 8t.q/  0 for all q; the
boundary nodes. Hence v cannot be one of the boundary nodes. From Equations (1) and
(2) (see p. 83), we have:
st.v/ rt.v/ D s0.v/ r0.v/ .Lw.zt.v//  Lw.8t.v///
85
 s0.v/ r0.v/ 
 
dG.v/ 
X
u
w.u;v/
!
.zt.v/ 8t.v//
D s0.v/ r0.v/D 0
Hence st.v/  rt.v/  0. But rt is a passive conguration so st.v/  0: On the other
hand, from zt.v/ > 8t.v/  0; we conclude that st.v/  0: But this forces equalities
everywhere in the above inequality. Hence 8t.u/  zt.u/ D 8t.v/  zt.v/ for all u in
the neighborhood ofv:Repeating the same argument for u and using the connectedness of
G; we nally get zt.q/  8t.q/ > 0 for all q, the boundary nodes. But this is clearly a
contradiction.
QED
Ourobjectiveistondanupperboundforthetimeittakesforacongurationtoreacha
recurrent conguration. Intuitively, this time is bounded by a minimal path from the unique
active vertex to the unique passive vertex. Since the active and passive vertices will change
over time, the correct bound will be the diameter of the graph (the maximum of minimal
paths between two vertices). To simplify the analysis, we will use the short circuits or
contraction technique used in the theory of electrical networks [13].
Given a nonrecurrent conguration r on a connected graph G, the graph G0 is obtained
from G by contracting all active vertices, Var , into one vertex a0 and similarly all passive
vertices, V pr ;intoonevertex p0;andremovealltheloops. Ifr isinactivethentheboundary
nodes become active, and we would contract all boundary nodes into one vertex, q0. In an
inactiveposition,wesetq0 D a0;andr0.p0/DPv2V pr r.v/Isimilarlyinanactiveposition,
we set q0 D p0 and r0. a0/ D Pv2Var r.v/: For neither passive nor active vertices we set
86
r0.v/Dr.v/:Now,ifthereexistsanedgebetweentwopassiveverticesthenthereisnoow
between these two vertices. Similarly, if there is an edge between two active vertices then
there is no ow between these vertices because the vertices have the same voltages. Hence,
we can remove these edges. If we identify two active vertices into one vertex, we then see
that this does not change the ow pattern of the network A similar argument applies on the
set of passive vertices. Continuing this process, we see that if we contract all the active
vertices into one vertex and all the passive vertices into one vertex then the ow pattern in
the contracted graph will be the same as the original graph. The following theorem gives a
mathematical translation of the above argument.
Theorem 3.5.6
Given a graph G with a nonrecurrent ow rt , let '0t be the ow in the graph G0 with
conguration r0t;then we have the following properties:
(a) If rt is active then
dr0t.a0/
dt D  dG0.a0/C
X
u
w.u;a0/'0t.u/
D
X
v2Vart
"
 dG.v/C
X
u
w.u;v/'.u/
#
D
X
v2Vart
drt.v/
dt :
(b) If rt is inactive then
87
dr0t.p0/
dt D
X
u
w.u; p0/'0t.u/
D
X
v2V prt
"X
u
w.u;v/'.u/
#
D
X
v2V prt
drt.v/
dt :
The quantity dG0.a0/ Puw.u;a0/'0t.u/is known as the effective conductance CEFF
of the graph G0 in electrical networks theory. We will use the random walk interpretation
of electrical networks [30, 31, 43] to better understand CEFF of the electrical network.
3.6 Random Walk interpretation of Electrical Networks
As usual, we assume that G is connected with multiple edges. We assign to each edge a
resistance 1. We can replace an edge with multiplicity w by one resistor with resistance
1
w: This way, we can convert our graph to a simple graph such that a resistance Rxy is
assigned to each edge connecting x to y:The conductance of an edge xy isw.x;y/D 1R
xy
:
We dene a random walk on G to be a Markov chain with transition matrix P given by
Pxy D w.x;y/d
G.x/
.
We choose two points a ( an active vertex) and b ( a passive vertex) and put a one-volt
battery across these points establishing a voltage '.a/ D 1 and '.b/ D 0: Our objective
now is to give a probabilistic interpretation of voltage and currents. By Ohm's law, the
currents through an edge connecting x to y of the graph are given by
ixy D .'.x/ '.y//R
xy
D.'.x/ '.y//w.x;y/:
88
By Kirchhoff's law, we have:
X
y
ixy D 0;
therefore,
'.x/ D
X
y
w.x;y/
dG.x/ '.y/D
X
y
Pxy'.y/; for x 6D a;b:
Let h.x/ be the probability that starting from x, the state a is reached before the state
b. Then h.x/ is harmonic in the interior and has the same boundary values as ' , i.e.,
'.a/ D h.a/ D 1, and '.b/ D h.b/ D 0: Therefore both ' and h are solutions to the
Dirichlet problem for the Markov chain with the same boundary values. Hence ' D h:
Therefore, we have the following theorem.
Theorem 3.6.1 (Probabilistic interpretation of voltage)
When unit voltage is applied between a and b, i.e., '.a/ D 1 and '.b/ D 0; the
voltage'.x/equals the probability that a walker starting from the point x will return to a
before reaching b:
QED
For the probabilistic interpretation of current, we assume the walker begins at a and
ends at b. Let ux be the expected number of times that the walker visits x before reaching
b. Then for x 6D a;b;we have ux DPy uyPyx:Since dG.x/Pxy D dG.y/Pyx we have
ux D
X
y
uyPxydG.x/d
G.y/
;
or
ux
dG.x/ D
X
y
uy Pxyd
G.y/
:
89
This means that'.x/D uxd
G.x/
is harmonic for x 6D a;b;and'.x/is actually the voltage at
x when we put a battery from a to b to establish a voltage'.a/D uad
G.a/
at a and'.b/D 0
at b:Thus the current from x to y is
ixy D .'.x/ '.y//w.x;y/
D
 u
x
dG.x/  
uy
dG.y/

w.x;y/
D ux Pxy  uyPyx :
Now ux Pxy is the expected number of times our walker will go from x to y and uyPyx is
the expected number of times she will go from y to x:Thus the current ixy is the expected
value (not necessarily an integer) for the net number of times the walker crosses along the
edge from x to y. Hence, we have the following .
Theorem 3.6.2 (Probabilistic interpretation of currents)
When a unit current ows out of a into b, the current ixy owing through the edge
connecting x to y is equal to the expected net number of times that a walker, starting at a
and walking until he reaches b, will move along the branch from x to y. These currents are
proportional to the currents that arise when a unit voltage is applied between a and b, the
constant of proportionality being the effective resistance of the network.
QED
When we impose a voltage ' between points a and b; the voltage '.a/D ' is estab-
lished at a and '.b/ D 0: And a current ia D Px iax will ow out of a. The amount
of current that ows depends upon the overall resistance of the network which is called
90
the effective resistance REFF; dened by REFF D '.a/i
a
; where the reciprocal quantity
CEFF D 1R
EFF
D ia'.a/ the effective conductance. We can interpret the effective conduc-
tance as an escape probability. When'.a/D 1;The effective conductance equals the total
current ia owing out of a. This current is
ia D
X
y
.1 '.y//w.a;y/
D
X
y
.1 '.y//w.a;y/d
G.a/
dG.a/
D dG.a/.1 
X
y
Pay'.y//
D dG.a/Pescape ;
where Pescape is the probability that starting at a, the walker reaches b before returning to
a. Thus
CEFF D dG.a/Pescape;
and
Pescape D CEFFd
G.a/
:
The key element in nding the bound on the time it takes for the network to reach
a recurrent conguration is nding an upper bound on the effective resistance REFF :
Here, we use Rayleigh's Monotonicity Law [31] in nding the upper bound on REFF .
For completeness, we will prove the Rayleigh's Monotonicity Law using the probabilistic
interpretation of effective conductance.
91
Rayleigh's Monotonicity Law: If the resistances of a circuit are increased, the effec-
tive resistance REFF between any two points will increase. If they are decreased, it will
decrease.
As usual we have a network of conductances (streets) and a walker moves from point
x to point y with probability Pxy D w.x;y/d
G.x/
;wherew.x;y/is the conductance and dG.x/
D Pyw.x;y/: As we have done earlier, we choose two points a and b: The walker that
starts at a and walks until he reaches b:We say'.x/is the probability that the walker that
starts at x, reaches a before b. Then '.a/ D 1; and '.b/ D 0: And the function '.x/ is
harmonic at every point x 6D a;b:As before, we denote by Pescape the probability that the
walker , starting at a, reaches b before returning to a. Then Pescape D 1 Py Pay'.y/:As
we have seen already, the effective conductance between a and b is the product daPescape:
We wish to show that if one of the conductances w.r;s/ is increased then the effective
conductance increases. The case where r and s is either a or b is easy. Therefore, we
assume that r;s 6D a and r;s 6D b: Instead of increasing w.r;s/, we can think of it as
adding a new edge (bridge) of conductance between r and s. Intuitively, we can think of
it by adding a bridge, this opens up new possibilities of escaping. One might say, it also
opens up new possibilities of returning to the starting point. It turns out the walker will
cross the bridge more often in a good direction than a bad direction. Let rs be an edge
with endpoints neither a nor b. We assume that '.r/  '.s/: There is therefore a better
chance of escaping from s than r: A good direction means to cross the edge from r to s.
We will show that the walker will cross the edge fromr to s more often on the average than
from s to r.
Let ux be the expected number of times that the walker is at x, and uxy the expected
92
number of times he crosses the edge xy from x to y before he reaches b or returns to a.
As we have seen in the random walk interpretation of currents (see p. 90) that uxd
G.x/
is
harmonic for x 6D a;b with boundary conditions uad
G.a/
, 0 at a and b respectively : But
the function '.x/uad
G.a/
is also harmonic with the same boundary conditions as uxd
G.x/
. By the
uniqueness principle: uxd
G.x/
D '.x/uad
G.a/
. Now,
urs D ur Prs
D urw.r;s/d
G.r/
D '.r/w.r;s/uad
G.a/
;
and
usr D usPsr
D usw.s;r/d
G.s/
D '.s/w.s;r/uad
G.a/
:
Sincew.r;s/Dw.s;r/and by assumption'.r/'.s/;this means that urs  usr:
Recall that we are denoting the conductance of the bridge by:Let us putsuperscripts
on the quantities that refer to the walk on the graph with the bridge. Let E denotes the
expected net number of times the walker crosses the bridge from r to s: Therefore; we
have E D
 u
r
dG.r/C  
us
dG.s/C

:
Claim:
Pescape D Pescape C.'.r/ '.s//E:
93
Theaboveclaimisbestexplainedthroughagameinwhichyourfortuneis'.x/. Recallthat
'.x/istheprobabilityofreturningtoa beforereachingb. Thenyourexpectednalearning
is 1.1   Pescape/C 0.Pescape/ D 1   Pescape: So the amount you would expect to lose is
Pescape:The rst step you take away from a, you would expect to lose 1 Px Pax'.x/D
Pescape:Every time you step away from r;you would expect to lose an amount
'.r/ 
 X
x
'.x/ w.r;x/d
G.r/C
C'.s/ d
G.r/C
!
D.'.r/ '.s// d
G.r/C
:
Similarly, every time you step away from s you expect to lose an amount
.'.s/ '.r// d
G.s/C
:
Hence, the total amount you expect to lose equals (expected loss at rst step)+(expected
loss atr)(expect number of times atr)+(expected loss at s)(expected number of times at s).
Therefore,
Pescape D Pescape C..'.r/ '.s// d
G.r/C
ur C..'.s/ '.r// d
G.s/C
us
D Pescape C.'.r/ '.s//E:
This is exactly what we needed for the proof of Rayleigh's Monotonicity Law. From the
Rayleigh's Monotonicity Law, we conclude that REFF is increased if one removes an edge
from the graph. This is due to the fact that removal of an edge corresponds to replacing a
94
unit resistor by an innite resistor. Hence, REFF is bounded by the length of the minimal
path connecting a to b:Moreover, it is bounded by the diameter of the graph.
3.7 Upper Bound for Run-Time Estimates
We now give an upper bound estimate for the time it would take for a conguration to reach
a stable or recurrent conguration in the Dirichlet game and in the electrical network.
Theorem 3.7.1
(a) If r0, the starting conguration for an electrical network, is active then for all values
t  D k r0 kC;rt is a passive conguration, where k r0 kCDPv2S;r0.v/>0 r.v/:
(b) If r0, the starting conguration for electrical network, is passive then for all values
t  D k r0 k ;rt a recurrent conguration, where k r0 k D  Pv2S;r.v/<0 r.v/:
(c) For any t  D k r0 k;rt is the recurrent conguration, where
k r0 kDk r0 kC C k r0 k  :
Proof: By Theorem 3.5.2, If rt.v/ < 0 then rt.v/  rt0.v/  0 for all t0  t and
if rt.v/ > 0 then 0  rt0.v/  rt.v/ for all t0  t: This means that for t0  t; we
have fv : rt0.v/>0g  fv : rt.v/>0g and if rt.u/ > 0 and u =2 fv : rt0.v/>0g then
rt0.u/ D 0: According to the Theorem 3.5.6, for a given t, we can obtain a graph G0t
by contracting all active vertices into a vertex a0 and all passive vertices into a vertex p0
such that Pv2Var
t
drt.v/
dt D
dr0t.a0/
dt : Since the total electrical currents away from a0 to
the neighboring vertices is the effective conductance of the graph G0t, Pv2Var
t
drt.v/
dt D
 CEFF . By Rayleigh's Monotonicity Law, REFF  D0t, hence CEFF  1D0
t
, where
95
D0t is the diameter of the graph G0t. Since the diameter of the graph decreases after the
contraction we have CEFF  1D;where D is the diameter of the original graph G:Hence
P
v2Vart drt.v/=dt   
1
D for all t  0. Integrating both sides with respect to t; we nd
that
X
v2S;rt.v/>0
rt.v/ 
X
v2S;r0.v/>0
r0.v/  tD
D k r0 kC   tD:
Since for an active conguration, we must have Pv2S;rt.v/>0 rt.v/ > 0, it is impossible
for the conguration to be active for t  D k r0 kC :This proves part.a/.
Part .b/ follows the same argument. From the dynamics of the electrical network,
we have fv : rt0.v/<0g  fv : rt.v/<0g for all t0  t: And if rt.u/ < 0 and u =2
fv : rt0.v/>0g then rt0.u/ D 0: Since r0 is passive, the only active vertices must be the
boundary nodes of G for all t  0: Applying Theorem 3.5.6 again to the graph G0t for a
given t  0; we have Pv2V pr
t
drt.v/
dt D
dr0t.p0/
dt : As a consequence of Kirchhoff's law,
the total of this currents away from a0 into the neighboring vertices of a0 is equal to the
total of this currents into p0 from the neighboring vertices of p0:Hence dr
0t.p0/
dt D CEFF
orPv2V pr
t
drt.v/
dt DCEFF;where CEFF is the effective conductance of G
0t. Using the fact
CEFF  1D;we nd thatPv2V pr
t
drt.v/
dt 
1
D:Integrating both sides with respect to t, we
obtain
X
v2S;rt.v/<0
rt.v/ 
X
v2S;r0.v/<0
r0.v/C tD
96
D   k r0 k  C tD:
Since for a passive conguration we must havePv2S;rt.v/<0 rt.v/<0;it is impossible for
the conguration rt to be passive for t  D k r0 k  :Since r0 is a passive conguration rt
must be the recurrent conguration for t  D k r0 k  :
For part (c), supposer0 is not the recurrent conguration. Let t0 be the time at which the
conguration turns passive, then by part (b) for any t  t0 C D k rt0 k , rt is the recurrent
conguration. Hence, if t  D k r0 kC CD k rt0 k  then rt is the recurrent conguration.
By the dynamics of the electrical network, we have k rt0 k  k r0 k  :So if t  D k r0 k
then rt is the recurrent conguration. And if r0 is the recurrent conguration then rt is
recurrent for all t  0 . Hence rt is the recurrent conguration for t  D k r0 k:
Theorem 3.7.2
Given s0 an initial conguration of the Dirichlet game which is not a stable congura-
tion we have:
(a) for any integer t  D k s0 kC;st is a stable conguration,
(b)foranyintegert > D.k s0 k CPv2S dG.v/  j S j/C1;st isacriticalconguration,
where j S j is the number of vertices in S:
Proof:
Dener0 as in Theorem 3.5.5, k s0 kCDk r0 kC :According to the Theorem 3.7.1, rt is
a passive conguration for t  D k s0 kC :By Theorem 3.5.5, st is a stable conguration
for all integers t  D k s0 kC . This proves part (a).
For part (b), let t0 be the rst integer such that st0 is a stable conguration. Set
r0.v/D st0.v/ .dG.v/ 1/:According to the Theorem 3.7.1, for all t  D k r0 k , rt is
97
a recurrent conguration. Therefore by Theorem 3.5.4, st is a critical conguration for all
integers t  t0 C D k r0 k  :
We now nd an estimate for k r0 k  :If s0.v/<0 then s0.v/ st0.v/.dG.v/ 1/;
therefore,
0   r0.v/  s0.v/CdG.v/ 1: .1/
If s0.v/ 0;then st0.v/ 0. Therefore,
 r0.v/D  st0.v/C.dG.v/ 1/.dG.v/ 1/: .2/
Putting the two inequalities (1) and (2) together, we obtain:
k r0 k k s0 k  C
X
v2S
dG.v/  j S j;
where j S j is the number of vertices in S:By part (a), t0 < D k s0 kC C1:Therefore we
have that for all integers t such that
t > D k s0 kC C1C D k s0 k  CD
X
v2S
dG.v/  D j S j
D D.k s0 k C
X
v2S
dG.v/  j S j/C1;
st is a critical conguration.
QED
We now apply our result to the special case where our graph G D S [@S is simple and
connected with Chung and Ellis's version of the Dirichlet game. Their version is a special
98
case of our version where there are no negative number of chips in the interior of G and
the boundary nodes act only as processors. In other words, chips red from a vertex in S
to a vertex in@S are instantly processed and removed from the game. Thus a conguration
s of this version of the Dirichlet game is a vector s : V.G/ ! ZC [ f0g which satises
Dirichlet boundary condition s.q/ D 0 for all q 2 @S . A conguration s is stable, if
s.v/< dG.v/for allv in S:Starting from an initial conguration s0, we say that the game
terminateswhenitreachesastableconguration. Inourversion, thisisequivalenttosaying
that the game has reached the rst stable conguration. Let f.v/ be the number of times
the vertex v in S is red during the Dirichlet game and Pv2S f.v/ is the total number of
rings, which is nite by Theorem 3.1.1. Here, we call f the score vector of the game and
is uniquely dened by
Lw;S f D s0  se;
where se is the end conguration of the game or the rst stable conguration in our version.
We state without proof the following result of Chung and Ellis [17] which computes a
bound on the total number of rings Pv2S f.v/ during the Dirichlet game by using the
Dirichlet eigenvalues.
Chung and Ellis's result
Let f be the score vector of a chip-ring game with Dirichlet boundary conditions.
Then the total number of rings in the game is bounded as follows:
X
v2S
f.v/ D k s0 kj S j32
99
where k s0 k is the total number of chips initially, j S j is the number of interior vertices,
and D is the diameter of the graph.
We will improve the above bound on the total number rings using Theorem 3.7.2 (a).
For a real number a; let dae be the smallest integer greater than or equal to a. Now, for
each integer t less than the time of the rst stable conguration, there are at most j S j
vertex rings since the boundary nodes do not re during this time. And by Theorem 3.7.2
(a), for any integer t  D k s0 kC;st is a stable conguration. Let t0 be the time of the
rst stable conguration. Then there are at most j S j t0 vertex rings before the rst stable
conguration. Since t0  t;we nd that there are at most j S j D k s0 kCvertex rings
before the rst stable conguration. Using the fact that there are no vertices with negative
number of chips in the interior of G, we nd that k s0 kCD k s0 k:In the case of a simple
graph, we have j S j dD k s0 ke D D k s0 kj S j; since D is an integer: Hence the total
number of vertex rings in Chung and Ellis's version of the Dirichlet game is bounded by
D k s0 kj S j:
100
Chapter IV
4 Algebraic Aspects of the Dirichlet Game
The purpose of this chapter is to relate the Laplacian and the Green's function studied
in Chapters 1, 2 to our version of the chip ring game studied in Chapter 3. As one of
the applications of this relation is to obtain a bound on the total number of vertex rings
to achieve a critical conguration from an arbitrary conguration s independent of the
norm q s q of s: The idea is to consider a class of congurations that leads to a unique
critical conguration and choose a stable conguration in this class. In other words, given
a conguration s with an arbitrary large number of chips, we seek a stable conguration
s0 such that s and s0 belong to the same coset, i.e., s and s0 will lead to the same critical
conguration. This is done by rst applying the Green function on s;to produce a sequence
of legal rings that nds the stable conguration s0.
We will organize this chapter as follows. In section 1, we generalize the classical re-
sult of the matrix-tree theorem [13] to weighted graphs. Namely, we will prove that the
product of the eigenvalues of the Dirichlet Laplacian is the same as the number of spanning
weighted forest rooted in the boundary of the graph. In the second section, we will obtain
a bound on the total number of vertex rings to achieve a critical conguration from an
arbitrary conguration s independent of the norm of s; q s q; by using Green's function.
The last section discusses the fact that the of set of critical congurations has the same
cardinality as the set of spanning weighted forest rooted in the boundary of the graph by
introducing an algorithm to achieve this bijection.
101
4.1 The Determinant of the Dirichlet Laplacian
Recall from Chapter 1.1, the weighted combinatorial Laplacian is dened by
Lw.x;y/D
8
>>>
>>><
>>>
>>>
:
dG.x/ if x D y
 w.x;y/ if x is adjacent to y
0 otherwise:
For any function f : V ! R;we have
Lw f.x/D
X
y
.f.x/  f.y//w.x;y/:
We consider the subgraph G D .S;S0/ of G D .S;E/ where S D S [@S and S0 denotes
the set of all edges in E excluding those edges whose endpoints are in @S: And let Lw;S
be the submatrix of Lw restricted to columns and rows indexed by vertices in S. Next, we
consider the incidence matrix B with rows indexed by vertices in S and columns indexed
by edges S0 as follows:
Bw.x;e/D
8>
>>>
>><
>>>
>>>:
pw.x;y/ if e D fx;yg;x < y
 pw.x;y/ if e D fx;yg;x > y
0 otherwise
We note that Lw;S D BwBTw; where BTw denotes the transpose of Bw. We next dene a
weighted rooted spanning forest of S to be any subgraph F satisfying:
(1) F is an acyclic subgraph of G
102
(2) F has a vertex set S;
(3) Each connected component of F contains exactly one vertex in@S:
Let us now dene the weight of a rooted spanning forest of S. Each connected compo-
nent of this rooted forest is a tree with its only root is at a vertexv in the boundary@S;and
let Tv denote this tree in S:Recall that a tree is a connected subgraph with no cycles. Now,
we dene the weight of Tv as follows: For each edge e D fx;yg in the edge set E.Tv/;the
weight of this edge is dened asw.e/Dw.x;y/;and
w.Tv/D5e2E.Tv/w.e/:
We also dene
w.F/D5v2@Sw.Tv/;
and
.S/D
X
F
w.F/;
where the summation takes place over all possible rooted spanning forest F. We will now
give a brief sketch of the proof of the following theorem which is quite similar to the
original proof of the matrix-tree theorem [13].
Theorem 4.1.1
Foraninducedsubgraph S in G with@S 6D ?, thedeterminantoftheDirichletweighted
Laplacian Lw;S is
det Lw;S D5siD1i D.S/;
where s Dj S j;the number of vertices in S:
103
Proof: The product of the eigenvalues
5siD1i D det Lw;S
D det.BwBTw/
D
X
X
det Bw;X det BTw;X :
where X ranges over all possible choices of s edges and Bw;X denotes the square submatrix
of B whose s columns correspond to the edges in X:This expansion over X, known as the
Cauchy-Binet expansion, is described in [45].
Claim 1: If the subgraph with vertex set S and edge set X contains a cycle, then
det Bw;X D 0:
The proof is similar to that in the matrix-tree theorem [13, 22] and we just briey
mention that the columns restricted to those indexed by the cycle are dependent.
Claim 2 : If the subgraph formed by the edge set X contains a connected component
having two vertices in@S;then det Bw;X D 0:
Proof: Let Y denote a connected component of the subgraph formed by X. If Y
contains more than one vertex in @S; then Y has no more than jE.Y/j   1 vertices in
S. The submatrix formed by the columns corresponding to edges in Y has rank at most
jE.Y/j 1. Therefore, det Bw;X D 0:
From Claim 1 and Claim 2, we know that the edges of X form a forest and each con-
nected component contains exactly one vertex in@S:Therefore, There is a column indexed
104
by an edge with only one nonzero entry, say.x1;e1/with x1 2 S. Therefore,
j det Bw;X jD
p
w.e1/j det B.1/x1 j
where B.1/w;x1 denotes the submatrix with rows indexed by S fx1g and columns indexed by
X  fe1g:By removingw.e/edges and one vertex at a time, we eventually obtain :
j det Bw;X jD 5e2X
p
w.e/:
Combining the claims (1) and (2) , with the above result, we have:
5siD1i D det Lw;S
D
X
X
det Bw;X det BTw;X
D
X
X
5e2Xw.e/
D .S/:
QED
By the above discussion, the problem of evaluating the determinant or 5siD1i of the
Dirichlet eigenvalues is the same as enumerating rooted spanning weighted forests of an
induced subgraph which is known to be a difcult problem. But since the eigenvalues can
be computed in polynomial time, we can therefore say that there is a polynomial algorithm
to evaluate.S/:
105
4.2 Relation of Green's Function to Dirichlet Game
The objective of this section is to show how the Dirichlet Laplacian and its Green's func-
tion can be used to develop an algorithm which produces the critical conguration corre-
sponding to an arbitrary conguration. Let C0.SI Z/ and C1.S0I Z/ denote the Abelian
groups of integer valued functions dened on the vertices S and the edges S0 of the graph
G D .S;S0/respectively. Considering the elements of these spaces as column vectors, the
incidence matrix Bw and its transpose BTw can be regarded as homomorphisms
Bw : C1.S0I Z/! C0.SI Z/;
and
BTw : C0.SI Z/! C1.S0I Z/:
We can also consider Lw D BwBTw as a homomorphism C0.SI Z/ ! C0.SI Z/: Let the
function : C0.SI Z/! Z be dened by.f/DPx f.x/:Then we have the following
lemma and theorem due to Biggs [9]. For completeness, we state the proof with minor
variations.
Lemma 4.2.1
The image of Lw is a normal subgroup of the kernel of
Proof: Sinceeachcolumnof B hasonlytwonon-zeroentries,pw.x;y/and pw.x;y/
that add up to 0, it follows that B D 0: Furthermore, if x 2 Im Lw, say x D Lwy D
BwBTwy;then.x/D.BwBTwy/DBw.BTwy/D 0:So x 2 Ker :Hence the image of
Lw is a subgroup of Ker :Since the groups are abelian, it is a normal subgroup.
106
Denote the set of critical congurations on a graph G by K.G/:For each conguration
s there is a unique critical conguration.s/ 2 K.G/determined by Theorem 3.3.5. The
following theorem gives an abelian group structure to K.G/:
QED
Theorem 4.2.2
The set K.G/ of critical congurations on a connected graph G is in a one-to-one
correspondence with the Abelian group KerIm Lw :
Proof:First,weshowthatthereisacongurationrepresentinganelementof KerIm Lw :
Given a x 2 Ker  , let s be the conguration dened on vertices in the S by
s.v/D
8>
><
>>:
dG.v/ 1 if x.v/ 0
dG.v/ 1  x.v/ if x.v/<0
andthevalueofs ontheboundaryisdenedinsuchawaythatPq2@S s.q/D  Pv2S s.v/:
Let Dv1;:::;vn be a sequence that leads s to a stable conguration s0 then s0 D s Lw.
Let z D x Cs  s0:Then z D x C Lw;so [z] D [x] and
z.v/D x.v/Cs.v/ s0.v/ dG.v/ 1 s0.v/ 0:
Hence there is a conguration z representing the given coset [x]: We now show that the
mapping
h : KerIm Lw ! K.G/;
given by h.x/ D .s/, where s is any conguration in the coset [x]; is well-dened.
107
Suppose that s1 and s2 are congurations such that [s1] D [s2] D [x]: In this case s1   s2
D Lw f for some f 2 C0.SI Z/ . We can write f D f1   f2 where f1 and f2 are
nonnegative functions. Let s0 D s1   Lw f1 D s2   f2 . Then by Theorem 3.3.5, there is
a unique critical conguration c is reached by a legal sequence of rings applied to s0:So
c D .s0/. From the equation s0 D s1   Lw f1, we conclude that there is a legal sequence
of rings that leads from s1 to s0:Hence, there is a legal sequence of rings that leads from
s1 to c; which is a critical conguration. By Theorem 3.3.5, we must have .s1/ D c:
Using the same argument, we have .s2/ D c: Hence h is well-dened. To show h is
injective, suppose that h [s1] D h [s2]. Then.s1/ D .s2/ D c;where c can be reached
from s1 and from s2 by legal sequences of rings. So there are vectors x1 and x2 such that
c D s1  Lwx1 D s2  Lwx2 . Hence s1  s2 D Lw.x1  x2/ or [s1] D [s2]: It is easy
to see that h is surjective. Given a critical conguration c in K.G/ then .c/ D c and
h.[c]/D c:
QED
Since there is an Abelian group structure on KerIm Lw ; dened by [s1] C [s2] D
[s1 Cs2];we can translate this structure to K.S/by Theorem 4.2.2 under the operation ,
where h [s1]  h [s2] D h [s1 Cs2];that is.s1/.s2/ D .s1 C s2/:Equivalently, for
any two critical congurations c1 and c2 , we have
c1 c2 D.c1 Cc2/:
For a real number a, let bac be the oor of a, i.e., the largest integer smaller than or
equal to a. And for a vector a , let bac be the largest vector obtained by taking the oor of
108
every coefcient of a:For the conguration s on the induced subgraph GS dene
s0 D s   Lw;SGw;S.s/;
where Gw;S is the Green's function of the Dirichlet combinatorial Laplacian, i.e., Gw;S D
L 1w;S:Bytheaboveargument, sinceGw;S.s/2 ZjSj ands j@SD 0 wehave.s0/D.s/:
The following lemma, extended from the case of a standard graph [17] to a weighted one
describes how to obtain a conguration with a small number of chips from a conguration
with arbitrary large number of chips with the same corresponding critical conguration.
Lemma 4.2.3
Given a conguration s and the discrete Green's function Gw;S, the conguration s0
dened by
s0 D s   Lw;SGw;S.s/
satises
j s0.x/j<dG.x/:
Proof: Set t D Gw;S.s/ Gw;S.s/then 0  t.y/<1 for all y 2 S;and
Lw;S.t/ D Lw;SGw;S.s/  Lw;SGw;S.s/
D s   Lw;SGw;S.s/
D s0:
109
Since
Lw;S.t/D t.x/dG.x/ 
X
y
t.y/w.x;y/;
and 0  t.y/<1 for all y 2 S;we have j s0.x/j<dG.x/:
QED
Applying Lemma 4.2.3 to any conguration s with an arbitrary large number of chips,
we can obtain a conguration s0 such that j s0.x/ j< dG.x/ and .s0/ D .s/;i:e:; both
s and s0 will reach the same critical conguration. This is done at the cost of O.n!/
arithmetic operations for matrix inversion, where 2 ! 2:376:
For real number a, let [a] be the smallest integer greater than a. Since for each in-
teger t there are at most n rings, where n is the number of vertices in G. By the-
orem 3.7.2, there is at most nD.k s0 k CPx2S dG.x/  j S j/C1 number of rings
to reach a critical conguration. Since k s0 k < Px2S dG.x/, there will be at most
nD.2Px2S dG.x/  j S j/C1 rings to reach a critical conguration. This argument
yields the complexity of determining a critical conguration corresponding to an arbitrary
conguration, which we summarize in the following theorem.
Theorem 4.2.4
Given a conguration s in the Dirichlet game, computing the corresponding critical
conguration requires at most
n
"
D.2
X
x2S
dG.x/  j S j/C1
#
vertex rings and O.n!/arithmetic operations, where D is the diameter of G:
110
4.3 Critical Conguration and Rooted Spanning Weighted Forest
The set of critical congurations can be characterized as a set having the same cardinality
as the number of spanning weighted forests rooted in@S:A bijection between the two sets
is obtained algorithmically by playing a chip-ring game using a critical conguration as
an initial point. The idea is motivated by a theorem due to Biggs [9] which states that the
critical group K.G/ has order k , the number of spanning weighted tree in G rooted in a
distinguished vertex q. We will form a new graph G0 by connecting q to all the vertices
in the boundary @S such that the number of edges connecting q to each vertex u 2 @S
is exactly 1, then the set of a spanning weighted forest of G rooted in the boundary @S
has the same cardinality as the set of spanning weighted trees of G0 rooted in q such that
the number of edges connecting q to each vertex u 2 @S is one: This is due to our basic
assumption that w.x;y/ D 0 for all x;y 2 @S. Before, we state the next theorem which
draws a bijection between the set of critical congurations in G and the set of critical
congurations cq in G0 such that cq j@S .x/ D dG0   1, we will present the following
corollary which is a consequence of the Theorem 3.3.7:
Corollary 4.3.1
The conguration c is critical if and only if c Cc yields c under some ring sequence
which is a permutation of S;wherec is the conguration dened as follows:
c.v/D
X
u2@S
w.u;v/; for everyv 2 S :
Theorem 4.3.2
Given a critical conguration c in G, dene cq, a conguration in G0 with a single
111
boundary node fqg;by
cq.x/ D c.x/S C.dG0.x/ 1/@S:
Then cq is a critical conguration of G0 with a single boundary node fqg. Conversely, any
critical conguration cq in G0 with a single boundary node fqg such that
cq j@S .x/D dG0.x/ 1;
can be written in the above form for some critical conguration c in G .
Proof: It is easy to see that cq is a stable conguration in G0: Since c is a critical
conguration in G and the number of chips in the boundary nodes are at most dG0.x/  1:
Now, the conguration
.cq Ccq/.x/D c.x/S Ccq.x/;
will yield the conguration c.x/S C.dG0.x//@S after q is being red. Also once the
vertices in @S are red exactly once, we get the conguration .c.x/Cc.x//S: Since
c is a critical conguration, By Corollary 4.3.1 there is a sequence of rings which is a
permutation of S such that after applying it to the conguration cCc, we obtain c:Putting
it all together, we have a legal sequence of rings which is a permutation of S such that
it will lead the conguration cq Ccq to cq. Hence, by Corollary 4.3.1, cq is a critical
conguration of G0:
Conversely, given a critical conguration cq in G0 such that cq j@S .x/ D dG0.x/  1;
112
then by Corollary 4.3.1, there is a sequence of rings which is a permutation of S such that
it will lead cq Ccq to cq . Since the vertices in G are red only once after the vertex q
is activated by this sequence of rings, by applying Theorem 3.3.7, the conguration c D
cq jS which reappears would be a critical conguration. Furthermore, cq.x/D cq jS .x/S:
QED
Theorem 4.3.2 combined with the argument at the beginning of the previous paragraph
would imply that the set of critical congurations in G is in a one-to-one correspondence
with the set of spanning weighted forest rooted in the boundary@S:Now, we are ready to
present an algorithm to nd the spanning forest once a critical conguration in G is given.
The idea behind this algorithm lies in Corollary 4.3.1. Given a critical conguration, once
we activate the boundary nodes, the vertices are only red once. So we construct an edge
only when ring one vertex would make the adjacent vertex re. In this way, since the
vertices are only red once, we would avoid making a cycle in the construction. Hence, the
resulting construction is a tree. Since all the vertices are red, it is a spanning tree. Now,
give a critical conguration cq in G0 . Assign a total ordering of edges in G0:Add a chip
to every vertex in @S as if q were red. Then add the edges fq;ug to the tree which was
initially empty for each u adjacent to q: Fire the vertex u that is ready. If there are more
than one vertex that are ready, re the one that has a shortest path to q with respect to the
total ordering given to the edges initially. Add fu;vg to the tree if ring u causes v to be
ready to re. According to the number of chips;w.u;v/;thatvreceives add dG.v/ cq.v/
edges between u andv:Note that because cq is a critical conguration then we must have
113
dG.v/ cq.v/ 0:Now, since u causesv to re we have
dG.v/ cq.v/w.u;v/:
Hence the weight of the edge of the constructed tree is less than or equal to the original
weight. Repeat this process until all vertices are red. By Corollary 4.3.1, the construction
leads to a spanning weighted tree. If there are two critical congurations , cq and c0q such
that cq.v/ 6D c0q.v/ for some vertex v 2 S and ring a vertex u adjacent to v causes v to
re in both critical congurations cq and c0q , then the number of edges connecting u tovin
construction of the corresponding spanning trees to cq and c0q will be different. This shows
that the two different critical congurations yield two different spanning weighted trees.
Since the set of critical congurations has order k , the number of spanning tree in G0, this
algorithm is actually a bijection from the set of critical conguration of G0 to the set of
spanning tree in G0:Now, given a critical conguration c in G;we nd the corresponding
critical conguration cq in G0 such that cq j@S .x/ D dG0.x/  1: Once the corresponding
spanning weighted tree with respect to cq is constructed by the above algorithm , cut all
the edges that connect q to the vertices of @S. Then the resulting subgraph is a spanning
weighted forest rooted in@S that corresponds to the critical conguration c in G:From the
condition cq j@S .x/ D dG0.x/  1; it is readily seen that this algorithm draws a bijection
from the set of critical congurations in G to the set of spanning weighted forest rooted in
@S.
The chip-ring game can be used to model several aspects of Internet computing in
connection with routing and fault tolerance. For instance, one such model assumes that
114
chips are labeled by messages which they carry, and studies the propagation of messages in
termsofinformedanduninformednodesofthenetwork. Inthisregard, theabovealgorithm
shows a way to geometrically reconstruct the network by means of playing the chip-ring
game on the graph. Since, for a given critical conguration, the above algorithm constructs
the corresponding spanning weighted forest rooted in @S. In this way, we can nd out
which pairs of nodes are connected and what their conductivities are.
115
5 REFERENCES
[1] D. Aldous, Hitting Times for Random Walks on Vertex-Transitive Graphs, Math.
Proc. Cambridge Philos. Soc. 106(1) (1989), 179-191.
[2] N. Alon, Eigenvalues and Expanders, Combinatorica 6(2) (1986), 83-96.
[3] W. Anderson and D. Morley, Eigenvalues of the Laplacian of a Graph, Linear and
Multilinear Algebra 18(2) (1985), 141-145.
[4] P. Bak, How Nature Works, The science of Self-Organized Criticality;Copernicus,
New York, 1996.
[5] P. Bak, C. Tang, and W. Kurt, Self Organized Criticality, Phys. Rev. A(3) (1988),
364-374.
[6] C. A. Berenstein and S-Y Chung, Harmonic Functions and Inverse Conductivity
Problems on Networks, to appear in SIAM J. Appl. Math.
[7] N. L. Biggs, The Tutte Polynomial as a Growth Function, J. Algebraic Combin.
10(2) (1999), 115-133.
[8] N. L. Biggs and P. Winkler, Chip-Firing and the Chromatic Polynomial, CDAM
Research Report Series LSE-CDAM-97-03.
[9] N. L. Biggs, Chip-Firing and the Critical Group of the Graph, J. Algebraic Combin.
9(1) (1999), 25-45.
[10] N. L. Biggs, Algebraic Potential theory on graphs, Bull. London Math. Soc. 29(6)
(1997), 641-682.
[11] A. Bjorner and L. Lovasz, Chip-Firing Games on Directed Graphs, J. Algebraic
Combin. 1(4) (1992), 305-328.
116
[12] A. Bjorner, L. Lovasz, and P. Shor, Chip-Firing Games on Graphs, European J.
Combin. 12(4) (1991), 283-291.
[13] B. Bollabas, Modern Graph Theory, Springer-Verlag 1998.
[14] A. Bondy and R.L. Hemminger, Graph Reconstruction-A survey, J. Combin. Th.
1(4) (1997), 227-268.
[15] A.P. Calderon, On an Inverse Boundary Value Problem, Numerical Analysis and
its Applications to Continuum, Phys. Soc. Braz. Math., (1980), 65-73.
[16]E.T.Chen, B.A.Gong, andL.J.Guo, TheisospectralProbleminaGraphTheory,
Natur. Sci. J. Harbin Normal Univ. 5 (1989), 50-57.
[17] F. Chung and R. Ellis, A Chip-Firing Game and Dirichlet Eigenvalues, J. Discrete
Math. 257 (2002), 341-356.
[18] F. Chung, Spectral Graph Theory, AMS, 1997.
[19] F. Chung, Spanning Trees in Subgraphs of Lattice, Amer. Math. Soc., Providence,
RI, (1999), 201-219.
[20] F. Chung, V. Faber, and T. A. Manteeuffel, On the Diameter of a Graph from
Eigenvalues Associated with its Laplacian, S. J. Discrete Math. 7 (1994), 443-754.
[21] F. Chung, A. Grigorian, and S. T. Yau, Upper Bound for Eigenvalues of the Dis-
crete and Continuous Laplace Operator, Advances in Math. 117 (1996), 165-178.
[22] F. Chung and R.P. Langlands, A Combinatorial Laplacian with Vertex Weights,
Journal of Combinatorics Theory 75 (1996), 316-327.
[23] F. Chung, Discrete Green's Functions, Journal of Combinatorics Theory (A) 91
(2000), 191-214.
[24] F. Chung, Distance Realization Problem with Applications to Internet Tomogra-
117
phy, J. Computer and System Sciences 63(3) (2001), 432-448.
[25] D. Coopersmith, U. Feige, and A. Schrijver, Random Walks on Regular and Irreg-
ular Graph, Siam J. of Discrete Math. 9 (1996), 301-308.
[26] E. B. Curtis and J. A. Morrow, Inverse Problems for Electrical Networks, Series
on Applied Math. 13 (2000)
[27] E. B. Curtis and J. A. Morrow, The Dirichlet to Neumann Problem for a Resistor
Networks, AMS 1990.
[28] M. Doob, On Imbedding a Graph in an Isospectral Family, In Proceedings of the
Second Manitoba Conference on Numerical Mathematics ( Univ. Manitoba, Winnipeg,
Man.) (1972), 137-142.
[29] M. Doob, D. M. Dragosm, and H. Sachs, Spectra of Graphs, Johann Ambrosius
Barth, Heidelberg, 3rd edition 1995.
[30] J. L. Doob, Stochastic Processes, John Wiley & Sons, New York, 1953.
[31] P. Doyle and J. L. Snell, Random Walks and Electric Networks, AMS, 1984.
[32] J. O. Durand-Lose, Parallel Transient Time of One-Dimensional Sand-Pile, Theo-
ret. Comput. Sci. 1 (1998), 183-193.
[33] K. Eriksson, No Polynomial Bound for the Chip-Firing Game on Directed Graphs,
Proc. Amer. Math. Soc. 4 (1991), 1203-1205.
[34] R. P. Feynman, The Feynmann Lecture on Physics, Addison-Wesley, 1964.
[35] A. Gabrielov, Abelian Avalanches and Tutte Polynomial, Physics A (1993), 253-
254.
[36] E. Goles and M. A. Kiwi, Games on Line Graph and Sand Piles, Theoret. Comput.
Sci. 2 (1993), 121-134.
118
[37]E.GolesandM.Margenster, UniversalityoftheChip-FiringGame,Theoret. Com-
put. Sci. 1 (1997), 121-134.
[38] E. Dhoker and D.H. Phong, On Determinants of Laplacians on Riemann Surfaces,
Comm. Math. Phys. 104 (1986), 537-545.
[39]R.A.HornandC.R.Johnson, MatrixAnalysis, CambridgeUniversityPress, Cam-
bridge 1985.
[40] V. Isakov, Inverse Problem for Partial Differential Equations, Springer-Verlag,
New York, (1998).
[41] S. Kakutani, Markov Processes and the Dirichlet Problem, Proc. Jap. Acad. 21
(1945), 227-233.
[42] A. Kelmans and Y. Xuerong, On the Distribution of Eigenvalues of Graphs, Dis-
crete Math.199(1) (1999) 251-258.
[43] F. Kelly, Reversibility and Stochastic Networks, John Wiley & Sons, New York,
1979.
[44] M. Kiwi, A. R. Ndoundam, M. Tchuente, and E. Gelos, No Polynomial Bound for
the Period of the Parallel Chip-Firing Game on Graphs, Theoret. Comput. Sci. 2 (1994),
527-532.
[45] P. Lancaster, Theory of Matrices, Academic Press, New York, 1969.
[46] L. Lovasz and P. Winkler, Mixing of Random Walks and other Diffusions on a
Graph, surveys in Combinatorics, (1995), 119-154.
[47] C. Meerino, Chip-Firing and the Tutte Polynomial, Ann. Comb. 1 (1997), 253-
259.
[48] C. Meerino, The Chip-Firing Game and Matroid Complexes, Discrete Mathemat-
119
ics and Theoretical Computer Science Proceedings AA, (2001), 245-256.
[49] R. Merris, Degree Maximal Graphs are Laplacian Integral. Linear Algebra Appl.
197/198 (1994), 143-176.
[50]R.Merris, AsurveyofGraphLaplacians, LinearandMultilinearAppl. 199(1994),
381-389.
[51] B. Mohar, The Laplacian Spectrum of Graphs, Graph Theory, Combinatorics, and
Applications 2 (1991), 871-898.
[52] B. Mohar, Isoperimetric Numbers of Graphs, J. Combin. Theory Ser. B 47 (1989),
274-291.
[53] C. Moore and M. Nilson, The Computational Complexity of Sandpiles, J. Statist.
Phys. 96(1) (1999), 205-224.
[54] C. St. J. A. Nash-Williams, Random Walks and Electric Currents in Networks,
Proceedings of the Cambridge Philosophical Soc. 55 (1959), 181-194.
[55] G. Polya and G. Szego, Isoperimetric Inequalities of Mathematical Physics, Ann.
of Math. Studies no. 27 Princeton University Press, (1951).
[56] A. M. Polyakov, Quantum Geometry of Bosonic Strings, Phys. Letters B 103
(1981), 207-210.
[57] D. Ray and I. M. Singer, Analytic Torsion for Complex Manifolds, Ann. Math. 98
(1973), 154.
[58] M. Renardy and R. C. Rogers, An Introduction to Partial Differential Equations,
Springer-Verlag 1993.
[59] H. L. Royden, Harmonic Functions on Open Riemann Surfaces, Trans. Amer.
Math. Soc. 73 (1952), 40-94.
120
[60] P. Sarnak, Determinants of Laplacians, Comm. Math. Phys. 110 (1987), 113-120.
[61] R. Seidel, On the all-Pairs-shortest-path problem, Proc. Sym. Theo. on Comput-
ing, ACM (1992), 745-749.
[62] J. Sylvester and G. Uhlmann, A global Uniqueness Theorem for an Inverse Value
Problem, Ann. Math., 125 (1987), 153-169.
[63] G. Tardos, Polynomial Bound for a Chip-Firing Game on Graphs, Siam J. Discrete
Math. 1 (1988), 397-398.
121