An Introduction to Analytic Graph Theory



Let $\cS$ be a set of graphs or a set of objects associated with some specific graph such that there is a symmetric adjacency relation defined on $\cS$. Two elements $S$ and $S'$ of $S$ are connected in $\cS$ if there exists a sequence $S = S_0, S_1, S_2, \cdots , S_k = S'$ of elements of $\cS$ such that $S_i$ and $S_{i+1}$ are adjacent for $i = 0, 1, \cdots , k - 1$. The minimum $k$ for which such a sequence exists is the distance $d(S, S')$ between $S$ and $S'$. If every pair of elements of $\cS$ are connected, then $\cS$ is connected. If $\cS$ is connected, then $(\cS, d)$ is a metric space. A nonnegative integer-valued function $f$ defined on $\cS$ is defined to be continuous on $\cS$ if $|f(S) - f(S')| \leq 1$ for every two adjacent elements $S$ and $S'$ of $\cS$. We consider various functions, continuous and noncontinuous, defined on such metric spaces. For each such metric space $(\cS, d)$, there is an associated metric graph whose vertices are the elements of the metric space and where two vertices of the metric graph are adjacent if and only if the corresponding elements are adjacent. These metric graphs are studied as well.