DISCRETE INVERSE CONDUCTIVITY PROBLEMS ON NETWORKS

Abstract

The purpose of this dissertation is to present a mathematical model of network tomography 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 define a variant of the chip-firing game (a discrete balancing process) in which chips are added to the game from the boundary nodes and removed from the game if they are fired into the boundary of the graph. We find 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 configurations of the chips.