Graph Basics

\(\newcommand{\R}{\mathbb{R}}\) \(\newcommand{\N}{\mathbb{N}}\) \(\newcommand{\ms}{\mathscr}\) \(\newcommand{\rta}{\rightarrow}\) \(\newcommand{\lfa}{\leftarrow}\) \(\newcommand{\upa}{\uparrow}\) \(\newcommand{\dna}{\downarrow}\) \(\newcommand{\lfrta}{\leftrightarrow}\) \(\newcommand{\nea}{\nearrow}\) \(\newcommand{\sea}{\searrow}\) \(\newcommand{\nwa}{\nwarrow}\) \(\newcommand{\swa}{\swarrow}\) \(\newcommand{\Rta}{\Rightarrow}\) \(\newcommand{\bs}{\boldsymbol}\)

Algebra

A graph \((S, \rta)\) consists of a nonempty base set \(S\) and a binary relation \(\rta\) on \(S\) (so that \(\rta\) is a subset of \(S^2\)).

\(\{y \in S: y \rta x\}\) is the set of left neighbors of \(x \in S\).
\(\{y \in S: x \rta y\}\) is the set of right neighbors of \(x \in S\).

In the discrete case (when \(S\) is countable), \((S, \rta)\) is a graph in the usual combinatorial sense, with \(S\) as the set of vertices and \(\rta\) as the set of edges (so in general, such a graph may be directed and may have loops, but not multiple edges). The general use of the term graph in this text is not common, but makes sense. Not only does it include ordinary discrete graphs but also, for example, the graph of a function \(f\) from \(S\) into \(S\), defined by the relation \(x \mapsto f(x)\). For a comprehensive treatment of relations see the book by Herbert Toth. Keeping with graph terminology, when \(x \rta y\) we say that \((x, y)\) is an edge in the graph. Note also that we use symbols that are more appropriate for relations (various arrows and other special symbols) rather than the set notation that is often used.

A kernel function of the graph \((S, \rta)\) is a function \(K: S^2 \to \R\) with the property that \(K(x, y) = 0\) if \(x \not \rta y\). The adjacency kernel \(L\) of \((S, \rta)\) is the indicator function of \(\rta\) (as a set of ordered pairs), so that \(L(x, y) = \bs 1(x \rta y)\) for \((x, y) \in S^2\).

If \(J, \, K\) are kernel functions of a graph \((S, \rta)\) and if \(a \in \R\) then \(J + K\) and \(a K\) are also kernel functions of \((S, \rta)\).

Details:

The operations are pointwise of course. That is \((J + K)(x, y) = J(x, y) + K(x, y)\) and \((a K)(x, y) = a K(x, y)\) for \((x, y) \in S^2\).

Special Properties

A graph \((S, \rta)\) is

Reflexive if \(x \rta x\) for all \(x \in S\).
Irreflexive if no \(x \in S\) satisfies \(x \rta x\).
Symmetric if \(x \rta y\) implies \(y \rta x\) for all \(x, \, y \in S\).
Asymmetric if no \(x, \, y \in S\) satisfies \(x \rta y\) and \(y \rta x\).
Antisymmetric if \(x \rta y\) and \(y \rta x\) imply \(x = y\) for all \(x, \, y \in S\).
Transitive if \(x \rta y\) and \(y \rta z\) imply \(x \rta z\) for all \(x, \, y, \, z \in S\).
Anti-transitive if no \(x, \, y, \, z \in S\) satisfies \(x \rta y\), \(y \rta z\), and \(x \rta z\).

We use the same terminology for the relation \(\rta\). So in the discrete case, a symmetric, irreflexive graph is an unordered graph in the usual combinatorial sense. Here are some other important special cases:

Special types of relations:

A reflexive, antisymmetric, transitive relation is a partial order.
A reflexive, transitive relation is a pre order.
An irreflexive, transitive relation is a strict partial order.
A reflexive, symmetric, transitive relation is an equivalence relation.
A reflexive, symmetric relation is a tolerance relation.

Some of these special relations will be studied in more detail in later sections, but the following definition gives some very basic graphs.

Suppose that \(S\) is a nonempty set.

\((S, =)\) is the equality graph.
\((S, \ne)\) is the complete irreflexive graph.
\((S, \equiv)\) is the complete reflexive graph where \(x \equiv y\) for every \(x, \, y \in S\)

In ordinary combinatorial graph theory, the term complete graph usually refers to the complete irreflexive graph. Of course, \(=\) and \(\equiv\) are equivalence relations on \(S\).

Set Operations

We can form new graphs from given ones using the standard set operatiions. The following definitions give the most important cases of this.

Suppose that \((S, \rta)\) is a graph. If \(R\) is a nonempty subset of \(S\), and \(\upa\) is a binary relation on \(R\) with the property that \(x \upa y\) implies \(x \rta y\) for \(x, \, y \in R\) then \((R, \upa)\) is a subgraph of \((S, \rta)\).

So to rephrase, \(R\) is a subset of \(S\) and as sets of ordered pairs, \(\upa\) is a subset of \(\rta\). In the discrete case, subgraph has its usual meaning: the vertices and edges in the subgraph are also vertices and edges in the parent graph. The most common and important special case of definition is when the relation \(\upa\) is simply \(\rta\) restricted to \(R^2\). In this case, we use the same symbol \(\rta\) for the relation on \(R\). So to emphasize, every \(R \subseteq S\) induces a subraph \((R, \rta)\) of \((S, \rta)\).

Suppose that \((S, \rta)\) is a graph.

The graph \((S, \lfa)\) where \(x \lfa y\) if and only if \(y \rta x\) is the inverse or converse of \((S, \rta)\).
The graph \((S, \not \rta)\) where \(x \not \rta y\) if and only if it is not true that \(x \rta y\) is the complement of \((S, \rta)\).

Suppose that \(I\) is a nonempty index set and that \(\{(S, \rta_i): i \in I\}\) is a collection of graphs with the same base set \(S\).

The graph \((S, \upa)\) where \(x \upa y\) if and only if \(x \rta_i y\) for some \(i \in I\) is the union of the collection.
The graph \((S, \dna)\) where \(x \dna y\) if and only if \(x \rta_i y\) for every \(i \in I\) is the intersection of the collection.

Trivially, most special graph properties are preserved under intersection. Here are the most important:

Suppose again that \(\{(S, \rta_i): i \in I\}\) is a collection of graphs with the same base set \(S\), and let \((S, \dna)\) denote the interesection of the collection.

If \((S, \rta_i)\) is reflexive for each \(i \in I\) then \((S, \dna)\) is refexive.
If \((S, \rta_i)\) is symmetric for each \(i \in I\) then \((S, \dna)\) is symmetric.
If \((S, \rta_i)\) is antisymmetric for each \(i \in I\) then \((S, \dna)\) is antisymmetric.
If \((S, \rta_i)\) is transitive for each \(i \in I\) then \((S, \dna)\) is transitive.

Suppose that \((S, \rta)\) and \((S, \upa)\) are graphs with the same base set \(S\). The graph \((S, \sea)\) where \(x \sea y\) if and only if \(x \rta y\) but not \(x \upa y\) is the difference between \((S, \rta)\) and \((S, \upa)\).

In particular, the following constructions will turn out to be useful for our study of reliability concepts, especially for discrete graphs.

Suppose that \((S, \rta)\) is a graph.

The union of \((S, \rta)\) and \((S, =)\) is the reflexive closure of \((S, \rta)\). It is the smallest reflexive graph that contains \((S, \rta)\) as a subgraph.
The set difference between \((S, \rta)\) and \((S, =)\) is the irreflexive reduction of \((S, \rta)\). It is the largest irreflexive subgraph of \((S, \rta)\).

Details:

Smallest and largest are with respect to the subgraph relation.

So the reflexive closure of \((S, \rta)\) is a reflexive supergraph of \((S, \rta)\), and any other reflexive supergraph of \((S, \rta)\) must have the reflexive closure as a subgraph.
Similarly, the irreflexive reduction of \((S, \rta)\) is an irreflexive subgraph of \((S, \rta)\), and any other irreflexive subgraph of \((S, \rta)\) must be a subgraph of the irreflexive reduction.

The reflexive closure of \((S, \rta)\) could also be constructed as the intersection of of all reflexive graphs with base set \(S\) that have \((S, \rta)\) as a subgraph. The reflexive closure of irreflexive discrete graphs is studied in more detail in Section 6. There are other closure types that can be obtained in this way. Here is one of the most important:

The transitive closure of a graph \((S, \rta)\) is the intersection of all transitive graphs with base set \(S\) that have \((S, \rta)\) as a subgraph.

Details:

The definition makes sense since the intersection is over a nonempty collection. The complete graph \((S, \equiv)\) is transitive and has \((S, \rta)\) as a subgraph.

Composition and Walks

Suppose again that \((S, \rta)\) and \((S, \upa)\) are graphs with the same base set \(S\). The graph \((S, \Rta)\) where \(x \Rta y\) if and only if there exists \(z \in S\) with \(x \rta z\) and \(z \upa y\) is the composition of \((S, \rta)\) with \((S, \upa)\).

Properties of composition.

Composition is associative.
The equality relation \(=\) is the identity with respect to composition.

Details:

For the proofs, we use set notation for the relations and product notation for composition.

Suppose that \(R_1, \, R_2, \, R_3\) are relations on \(S\). From the definition, it's straightforward to see that \(x[R_1 (R_2 R_3)]y\) if and only if \(x[(R_1 R_2) R_3]y\) if and only if there exist \(u, \, v \in S\) with \(x R_1 u\), \(u R_2 v\), and \(v R_3 y\).
Suppose that \(R\) is a relation on \(S\) and denote the equality realtion by \(E\). Then \(x (E R) y\) if and only if there exists \(u \in S\) with \(x = u\) and \(u R y\) if and only if \(x R y\). Similarly, \(x (R E) y\) if and only if \(x R y\).

Walks in a graph will be fundamentally important in our study of abstract reliability, particularly since we will be interested in random walks, the topic of Section 4.

Suppose that \((S, \rta)\) is a graph and that \(n \in \N_+\) and \((x_0, x_1, \ldots, x_n) \in S^{n + 1}\). The notation \[x_0 \rta x_2 \rta \cdots \rta x_n\] means that \(x_i \rta x_{i + 1}\) for each \(i \in \{0, 1, \ldots, n - 1\}\) and in this case, the sequence is a walk of length \(n\) in the graph from \(x_0\) to \(x_n\).

If the vertices are distinct, the sequence is a simple walk or a path.
If \(x_0 = x_n\) the sequence is a closed walk.
If the vertices are distinct except that \(x_0 = x_n\), the sequence is a simple closed walk or a cycle.

In the notation above, it's important to keep in mind that the relation \(\rta\) is not necessarily transitive. So, for example, \(x \rta y \rta z\) does not imply \(x \rta z\). In the discrete setting, the terms have their usual meanings from graph theory: a walk is sequence of adjacent vertices in the graph. There are other terms that are sometimes used (trail for example) and in fact the terminology is not completely standard. Our choice of terminology is made to minimize the number of separate terms. Of course, we can also have infinite walks. If \(x_i \in S\) for \(i \in \N\) and \(x_0 \rta x_1 \rta \cdots\) then \((x_0, x_1, \ldots)\) is an infinite walk in \((S, \rta)\) starting in \(x_0\).

For \(n \in \N_+\), let \(\rta^n\) denote the \(n\)-fold composition power of \(\rta\). Then \(x \rta^n y\) if and only if there exists a walk for length \(n\) in \((S, \rta)\) from \(x\) to \(y\).

A graph \((S, \rta)\) is strongly connected if for every \((x, y) \in S^2\), there exists a finite path from \(x\) to \(y\).

Suppose that \((S, \rta)\) is a discrete graph and that \(x \in S\).

The period \(d(x)\) of \(x\) is the greatest common divisor of the set of \(n \in \N_+\) such that there exists a walk of length \(n\) from \(x\) to \(x\).
If \(d(x) = 1\), then \(x\) is aperiodic; otherwise \(x\) is periodic.

Details:

If there are no walks from \(x\) to \(x\) then \(d(x) = \infty\).

Suppose again that \((S, \rta)\) is a discrete graph, and that \(x, \, y \in S\). If there exists a walk from \(x\) to \(y\) and a walk from \(y\) to \(x\) then \(d(x) = d(y)\). In particular, if \((S, \rta)\) is strongly connected then all \(x \in S\) have the same period, and the common value is the period of the graph.

Details:

The result is trivial if \(x = y\) so assume that \(x \ne y\). By assumption, there exists a walk of length \(j \in \N_+\) from \(x\) to \(y\) and a walk of length \(k \in \N_+\) from \(y \to x\). Hence there is a walk of length \(j + k\) from \(x\) to \(x\) so \(d(x) \mid j + k\). Suppose now that there is a walk of length \(n \in \N_+\) from \(y\) to \(y\). Then there is a walk of length \(j + n + k\) from \(x\) to \(x\) so \(d(x) \mid j + k + n\). It then follows that \(d(x) \mid n\) and so \(d(y) \mid d(x)\). By a symmetric argument, \(d(x) \mid d(y)\) and so \(d(x) = d(y)\).

The term period has various meanings in combinatorial graph theory. Definition is the standard term for period when applied to the adjacency matrix \(L\) and is appropriate for our purposes, particularly in the context of the random walks that we will study in Section 4.

Suppose that \((S, \rta)\) is a transitive graph. Then \((S, \rta^n)\) is a subgraph of \((S, \rta)\) for every \(n \in \N_+\).

Details:

Of course, \((S, \rta^1)\) is simply \((S, \rta)\). Suppose that \(n \in \{2, 3, \ldots\}\) and that \(x \rta^n y\) for \(x, \, y \in S\). Then there exists \((u_1, u_2, \ldots, u_{n-1}) \in S^n\) with \(x \rta u_1 \rta \cdots \rta u_{n-1} \rta y\). By the transitive property, \(x \rta y\).

The result in points the way to a simple construction of the transition closure of a graph.

Suppose that \((S, \rta)\) is a graph and let \((S, \upa)\) denote the union of \(\{(S, \rta^n): n \in \N_+\}\). Then \((S, \upa)\) is the transitive closure of \((S, \rta)\).

Details:

Suppose that \(x, \, y, \, z \in S\) and that \(x \upa y\) and \(y \upa z\). Then \(x \rta^m y\) and \(y \rta^n z\) for some \(m, \, n \in \N_+\). But then \(x \rta^{m + n} z\) and hence \(x \upa z\). So \((S, \upa)\) is transitive and has \((S, \rta)\) as a subgraph. Moreover, any other transitive graph that has \((S, \rta)\) as a subgraph must have \((S, \rta^n)\) as a subgraph for each \(n \in \N_+\) and hence \((S, \upa)\) as a subgraph.

Measure

Measurable Graphs

Suppose now \((S, \ms S)\) is a measurable space. Recall that \(S^n\) is given the product \(\sigma\)-algebra \(\ms S^n\) for \(n \in \N_+\).

A graph \((S, \rta)\) is a measurable graph, relative to \((S, \ms S)\), if the binary relation \(\rta\) is measurable. That is, \[\{(x, y) \in S^2: x \rta y\} \in \ms S^2\]

Often the underlying \(\sigma\)-algebra on \(S\) is understood, so we don't need to reference it when we speak of a measurable graph. Going forward, we will define a number of algebraic and probabilistic objects for the graph \((S, \rta)\). In general, these objects come in pairs—a left object defined in terms of the mapping that takes \(x \in S\) to \(\{y \in S: y \rta x\}\), the set of left neighbors of \(x\), and a right object defined in terms of the mapping that takes \(x \in S\) to \(\{y \in S: x \rta y\}\), the set of right neigbors of \(x\) (as defined in ). All right objects of \((S, \rta)\) are left objects of the inverse graph \((S, \lfa)\). Since our relation \(\rta\) is arbitrary, there would be no loss in generality in defining just one type of object. However, it is often the relationship between the left and right objects that is the most interesting. So our primary definitions, which we will give explicitly, will sometimes be left objects and sometimes right object, depending on the context. Of course, if the graph is symmetric, the right and left objects are the same and we can drop the adjective. Our first example of the left-right dichotomy is a natural \(\sigma\)-algebra associated with a graph:

Suppose that \((S, \rta)\) is a graph. The right \(\sigma\)-algebra associated with \((S, \rta)\) is \(\ms A = \sigma\{A_x: x \in S\}\) where \(A_x = \{y \in S: x \rta y\}\) is the set of right neighbors of \(x \in S\).

Similarly, the left \(\sigma\)-algebra associated with \((S, \rta)\) is \(\ms B = \sigma\{B_x: x \in S\}\) where \(B_x = \{y \in S: y \rta x\}\) is the set of left neighbors of \(x \in S\). But the right \(\sigma\)-algebra will be our main interest, as will be clear when we study probability on graphs in Section 3.

If \((S, \rta)\) is measurable with respect to \((S, \ms S)\) then \(\ms A \subseteq \ms S\) where \(\ms A\) is the right \(\sigma\)-algebras associated with \((S, \rta)\).

Details:

The set \(C = \{(x, y) \in S^2: x \rta y\} \in \ms S^2\). The set \(A_x\) of right neighbors of \(x \in S\) is the cross section of \(C\) at the first coordinate \(x\). This cross section is in \(\ms S\) by a basic result from measure theory.

The case where \(\ms A = \ms S\) will be of considerable interest. Similarly, \(\ms B \subseteq \ms S\) where \(\ms B\) is the left \(\sigma\)-algebra associated with the graph.

Suppose that \((S, \rta)\) is a graph. The right \(\sigma\)-algebra associated with \((S, \not \rta)\) is the same as the right \(\sigma\)-algebra associated with \((S, \rta)\).

Details:

The right neighbor sets of \((S, \not \rta)\) at \(x \in S\) is the complements of the right neighbor sets of \((S, \rta)\) at \(x\).

Suppose that \((S, \rta)\) is a discrete graph. Let \(\ms A_n\) denote the right \(\sigma\)-algebra associated with \((S, \rta^n)\) for \(n \in \N_+\). Then \(\ms A_{n + 1} \subseteq \ms A_n\) for \(n \in \N_+\). In particular, \(\ms A_n \subseteq \ms A = \ms B_1\)for \(n \in \N_+\).

Details:

For \(x, \, y \in S\) and \(n \in \N_+\) recall that \(x \rta^n y\) if and only if there exists a path of length \(n\) from \(x\) to \(y\). So for \(n \in \N_+\), the right neighbor set \(A^{(n)}_x\) of \(x \in S\) for \((S, \rta^n)\) is the set of \(u \in S\) such that there is a path of length \(n\) from \(x\) to \(y\). It follows that \(A^{(n + 1)}_x = \bigcup_{y \in A_x} A^{(n)}_y\) where as usual, \(A_x = A^{(1)}_x\) is the right neighbor set of \(x \in S\) for \((S, \rta)\). But \(A^{(n)}_y \in \ms A_n\) for \(y \in A_x\), and of course \(A_x\) is countable, so \(A^{(n + 1)}_x \in \ms A_n\) for \(x \in S\).

An analogous result holds for the left \(\sigma\)-algebras. We will usually assume that our graphs are measurable relative to an underlying measurable space. After all, we want to study measures, and particularly probability measures on the graph. Here is one very important and basic application of definition :

If the graph \((S, =)\) is measurable then the measure space \((S, \ms S)\) has a measurable diagonal. That is \(\{(x, x): x \in S\} \in \ms S^2\).

The importance of a space with a measurable diagonal is discussed in the Preface, and of course, \((S, =)\) is the most basic of graphs.

If \((S, \rta)\) is a measruable graph, then a subgraph \((R, \upa)\) is also required to be measurable. That is, \(R \in \ms S\) and \(\{(x, y) \in R^2: x \upa y\} \in \ms S^2\).

That is, \(R \in \ms S\) and \(\upa\) (as a set of ordered pairs) is in \(\ms S^2\).

Suppose that \((S, \rta)\) is a measurable graph. Then the following are also measurable graphs:

\((S, \lfa)\), the inverse of \((S, \rta)\)
\((S, \not \rta)\), the complement of \((S, \rta)\).

Details:

By assumption, \(\rta\) as a subset of \(S^2\) is in \(\ms S^2\).

The function \(\varphi: S^2 \to S^2\) defined by \(\varphi(x, y) = (y, x)\) is measurable, since it has measurable coordinate functions. As a subset of \(S^2\), \(\lfa\) is the inverse image of \(\rta\) under \(\varphi\), and hence is in \(\ms S^2\).
As a subset of \(S^2\), \(\not \rta\) is the complement of \(\rta\) and hence is in \(\ms S^2\).

The complete reflexive graph \((S, \equiv)\) defined in is always measurable since \(\{(x, y) \in S^2: x \equiv y\} = S^2 \in \ms S^2\). If \((S, =)\) is measurable, then by , the complete irreflexive graph \((S, \ne)\) is also measurable.

Suppose that \((S, \rta)\) is a measurable, reflexive, antisymmetric graph. Then \((S, =)\) is measurable, so \((S, \ms S)\) has a measurable diagonal.

Details:

As sets of ordered pairs, \(\rta\) and the inverse \(\lfa\) are measurable. Since the graph is reflexive and antisymmetric, \(=\) is the intersection of \(\rta\) and \(\lfa\).

Suppose that \(\{(S, \rta_i): i \in I\}\) is a countable collection of measurable graphs. Then the following are also measurable:

The union \((S, \upa)\) of the collection.
The intersection \((S, \dna)\) of the collection.

Details:

As a set of ordered pairs, \(\rta_i\) is in \(\ms S^2\) for each \(i \in I\). Since \(I\) is countable, the union and interesection are in \(\ms S^2\).

Suppose that \((S, \rta)\) and \((S, \upa)\) are measurable graphs. Then \((S, \sea)\), the difference between \((S, \rta)\) and \((S, \upa)\), is also measurable.

Details:

By assumption, \(\rta\) and \(\upa\) as subsets of \(S^2\) are in \(\ms S^2\). Hence the set difference of \(\rta\) and \(\upa\) is in \(\ms S^2\).

Suppose that \((S, =)\), \((S, \rta)\), and \((S, \upa)\) are measurable graphs. Then \((S, \Rta)\), the composition of \((S, \rta)\) with \((S, \upa)\), is also measurable.

Details:

By assumption \(\{(x, u) \in S^2: x \rta u\} \in \ms S^2\) and \(\{(v, y) \in S^2: v \upa y\} \in \ms S^2\). Hence \[\{(x, u, v, y) \in S^4: x \rta u, \, v \upa y\} \in \ms S^4\] By the assumption of a measurable diagonal, \(\{(x, z, z, y): x, \, y, \, z \in S\} \in \ms S^4\). Intersecting the two sets we have \[\{(x, z, z, y) \in S^4: x \rta z, \, z \upa y\} \in \ms S^4\] The projection of this set onto the first and last coordinates is measurable. That is, \[\{(x, y) \in S^2: x \Rta y\} = \{(x, y) \in S^2: \text{ there exists } z \in S \text{ with } x \rta z, \, z \upa y\} \in \ms S^2\]

In particular, the two types of closure that we have studied preserve measurability.

Suppose that \((S, =)\) and \((S, \rta)\) are measurable graphs. Then the following are also measurable:

The reflexive closure of \((S, \rta)\)
The transitive closure of \((S, \rta)\)

Details:

The reflexive closure of \((S, \rta)\) is the union of \((S, \rta)\) and \((S, =)\), both of which are measurable.
The transitive closure of \((S, \rta)\) is the union of \(\{(S, \rta^n): n \in \N_+\}\), a countable collection of measurable graphs.

A kernel function of a measurable graph \((S, \rta)\) is also required to be measurable. Note that the adjacency kernel \(L\) is measurable by the very definition of a measurable graph.

Suppose that \((S, \rta)\) is a measurable graph, and let \(n \in \N_+\) and \(x, \, y \in S\). Then

\(\{(x_1, x_2, \ldots, x_{n + 1}) \in S^{n + 1}: x_1 \rta x_2 \rta \cdots \rta x_{n + 1}\} \in \ms S^{n + 1}\).
\(\{(x_1, x_2, \ldots, x_n) \in S^n: x \rta x_1 \rta \cdots \rta x_n\} \in \ms S^n\).
\(\{(x_1, x_2, \ldots, x_n) \in S^n: x_1 \rta \cdots \rta x_n \rta y\} \in \ms S^n\).
\(\{(x_1, x_2, \ldots, x_n) \in S^n: x \rta x_1 \rta \cdots \rta x_n \rta y\} \in \ms S^n\).

Details:

Let \(L\) denote the adjacency kernel of \((S, \rta)\) and let \(n \in \N_+\). Recall that cross sections of measurable sets are measurable by standard results in measure theory.

This is the set of all walks of length \(n \in \N_+\). The indicator function of this set is the function on \(S^{n+1}\) given by
For \(x \in S\), this is the cross section on the left at \(x\) of the set of walks of length \(n\).
For \(y \in S\), this is the cross section on the right at \(y\) of the set of walks of length \(n\).
For \(x, \, y \in S\), \((x, y) \in S^2\), this the cross section at \(x\) on the left and \(y\) on the right of the set of walks of length \(n + 1\).

Positive Measures

There are always measures of interest on the space \((S, \ms S)\), probability measures certainly, but also usually a fixed reference measure such as counting measure on discrete spaces and Lebesgue measure on Euclidean spaces. The graphs in this subsection are assumed to be measurable and for the remainder of this subsection, we assume that \(\lambda\) is a fixed \(\sigma\)-finite reference measure on \((S, \ms S)\). If \(K\) is a kernel for the graph \((S, \rta)\) then the domains of integration for the left and right operators associated with \(K\) are reduced.

If \(f: S \to \R\) is measurable then, assuming that the integrals exist, \begin{align*} (K f)(x) &= \int_{x \rta y} K(x, y) f(y) \, d\lambda(y), \quad x \in S \\ (f K)(y) &= \int_{x \rta y} f(x) K(x, y) \, d\lambda(x), \quad y \in S \end{align*}

If \(f: S \to \R\) is integrable then \begin{align*} (L f)(x) &= \int_{x \rta y} f(y) \, d\lambda(y), \quad x \in S \\ (f L)(y) &= \int_{x \rta y} f(x) \, d\lambda(x), \quad y \in S \end{align*}

If \(f, \, g : S \to \R\) are measurable and \((x, y) \mapsto f(x) g(y)\) is integrable (with respect to \((S^2, \ms S^2, \lambda^2)\)) then the self-adjoint property of the adjacency kernel \(L\) is \[\langle f L, g \rangle = \langle f, L g \rangle = \int_{x \rta y} f(x) g(y) \, d\lambda^2(x, y)\]

Our next definition reviews the product of two kernels, analogous to matrix multiplication in the discrete case.

If \(J, \, K\) are kernels of \((S, \rta)\) then \[(J K)(x, y) = \int_{x \rta t \rta y} J(x, t) K(t, y) \, d\lambda(t), \quad (x, y) \in S^2\]

Note that \(J K\) is a kernel of \((S, \rta^2)\), the composition power of \(\rta\) of order \(2\).

Walks

Powers of the adjacency kernel give information about the measure of walks in the graph.

Suppose that \((S, \rta)\) is a graph with adjacency kernel \(L\).

\(L^n(x, y) = \lambda^{n - 1}\{(x_1, x_2, \ldots, x_{n - 1}) \in S^{n - 1}: x \rta x_1 \rta \cdots \rta x_{n - 1} \rta y\}\) for \(n \in \{2, 3, \ldots\}\) and \((x, y) \in S^2\).
\((\bs 1 L^n)(x) = \lambda^n\{(x_1, \ldots, x_n) \in S^n: x_1 \rta \cdots \rta x_n \rta x\}\) for \(n \in \N_+\), and \(x \in S \).
\((L^n \bs 1)(x) = \lambda^n\{(x_1, \ldots, x_n) \in S^n: x \rta x_1 \rta \cdots \rta x_n\}\) for \(n \in \N_+\) and \( x \in S\).

So if \(n \in \{2, 3, \ldots\}\) then \(L^n(x, y)\) is the measure of the set of walks of length \(n\) from \(x\) to \(y\). If \(n \in \N_+\) then \((\bs 1 L^n)(x)\) is the measure of the set of walks of length \(n\) that terminate in \(x\), while \((L^n \bs 1)(x)\) is the measure of the set of walks of length \(n\) that start in \(x\). Walk functions will play an important role and are formalized in definition .

Suppose again that \((S, \rta)\) is a graph.

The left walk function of order \(n\) for \((S, \rta)\) is the function \(u_n: S \to [0, \infty]\) defined as follows: \(u_0(x) = 1\) for \(x \in S\), and for \(n \in \N_+\), \[u_n(x) = \lambda^n\{(x_1, \ldots, x_n) \in S^n: x_1 \rta \cdots \rta x_n \rta x\}, \quad x \in S\]
The right walk function of order \(n\) for \((S, \rta)\) is the function \(v_n: S \to [0, \infty]\), defined as follows: \(v_0(x) = 1\) for \(x \in S\), and for \(n \in \N_+\), \[v_n(x) = \lambda^n\{(x_1, \ldots, x_n) \in S^n: x \rta x_1 \rta \cdots \rta x_n\}, \quad x \in S\]
The total walk parameter of order \(n \in \N\) is defined as follows: \(w_0 = \lambda(S)\) amd for \(n \in \N_+\), \[w_n = \lambda^{n + 1}\{(x_1, x_2, \ldots, x_{n + 1}) \in S^{n + 1}: x_1 \rta x_2 \rta \cdots \rta x_{n + 1}\}\]

So once again, if \(n \in \N_+\) then \(u_n(x)\) is the measure of the set of walks of length \(n\) that terminate in \(x \in S\) while \(v_n(x)\) is the measure of the set of walks of length \(n\) that start in \(x\), and \(w_n\) is the measure of the set of all walks of length \(n\). When \(n = 1\) we will sometimes drop the subscript, so \(u(x) = \lambda(\{y \in S: y \rta x\})\) is the measure of the set of left neighbors \(x \in S\) while \(v(x) = \lambda(\{y \in S: x \rta y\})\) is the measure of the set of right nieghbors of \(x \in S\) and \(w = \lambda^2\{(x, y) \in S^2: x \rta y\}\) is the measure of the set of edges, or equivalently, the measure of \(\rta\) as a set of ordered pairs. For a discrete graph, \(w_0\) is the number of vertices and \(w_1\) the number of edges. The left walk functions will be our primary interest, but the right walk functions and the total walk parameters will also be important for finite graphs. Note that the walk functions are measurable. We can rephrase the definitions of the walk functions in a recursive way:

The walk functions are defined recursively by \(u_0(x) = v_0(x) = 1\) for \(x \in S\) and for \(n \in \N\), \begin{align*} u_{n + 1}(x) & = \int_{y \rta x} u_n(y) \, d\lambda(y), \quad x \in S\\ v_{n + 1}(x) & = \int_{x \rta y} v_n(y) \, d\lambda(y), \quad x \in S \end{align*}

For \(n \in \N\), \[w_n = \int_S u_n(x) \, d\lambda(x) = \int_S v_n(x) \, d\lambda(x),\]

For \(j, \, k \in \N\), \[ w_{j + k} = \int_S v_j(x) u_k(x) \, d\lambda(x)\]

Details:

The simple combinatorial argument is that a path of length \(j + k\) consists of a path of length \(j\) that terminates in some \(x \in S\) concatenated with a path of length \(k\) starting at \(x\).

In particular, if the graph is symmetric then for \(j, \, k \in \N\), \[ w_{j + k} = \int_S u_j(x) u_k(x) \, d\lambda(x)\]

Suppose that \((S, \rta)\) is a graph and that \(k \in (0, \infty)\).

\((S, \rta)\) is left regular of degree \(k\) if \(u(x) = k\) for all \(x \in S\).
\((S, \rta)\) is right regular of degree \(k\) if \(v(x) = k\) for all \(x \in S\).
\((S, \rta)\) is regular of degree \(k\) if it is both left and right regular of degree \(k\).

Definition has its usual meaning for discrete, symmetric graphs: for \(k \in \N_+\), the graph is regular of degreee \(k\) if every vertex has \(k\) neighbors.

Suppose again that \((S, \rta)\) is a graph.

\((S, \rta)\) is left finite if \(u(x) \lt \infty\) for almost every \(x \in S\).
\((S, \rta)\) is right finite if \(v(x) \lt \infty\) for almost every \(x \in S\).
\((S, \rta)\) is locally finite if it is both left finite and right finite.

The graph \((S, \rta)\) is finite if \(\lambda(S) \lt \infty\). Trivially in this case, the graph is locally finite as well.

Suppose again that \((S, \rta)\) is a graph.

\((S, \rta)\) is left positive if \(u(x) \gt 0\) for almost every \(x \in S\).
\((S, \rta)\) is right positive if \(v(x) \gt 0\) for almost every \(x \in S\).

Our primary interest will be in graphs that are left finite and right positive, relative to the reference measure \(\lambda\). Hopefully, the reasons will become clear when we study probability on graphs in Section 3

Suppose that \((S, \rta)\) is a transitive graph. Then for \(n \in \N\), \(u_n(x) \le u^n(x)\) for almost all \(x \in S\).

Details:

Let \(A_x = \{t \in S: t \rta x\}\) denote the set of left neighbors of \(x \in S\). Suppose that \(x, \, y \in S\) and \(y \rta x\). If \(t \in A_y\) then \(t \rta y\) and hence by transitivity \(t \rta x\) and so \(t \in A_x\). That is, \(y \rta x\) implies \(A_y \subseteq A_x\) and so \(u(y) \le u(x)\). Now, the statement in the theorem is true for \(n = 0\) by definition. Suppose the statement is true for a given \(n \in \N\). Then by the induction hypothesis, for almost all \(x \in S\), \[u_{n + 1}(x) = \int_{A_x} u_n(y) \, d\lambda(y) \le \int_{A_x} u^n(y) \, d\lambda(y) \le \int_{A_x} u^n(x) \, d\lambda(y) = u^n(x) \lambda(A_x) = u^{n + 1}(x)\]

So if the transitive graph \((S, \rta)\) is left finite then \(u_n(x) \lt \infty\) for almost all \(x \in S\) and all \(n \in \N\). Analogous results hold for the right walk functions.

If the graph \((S, \rta)\) is right positive, then for \(n \in \N\), \(v_n(x) \gt 0\) for almost all \(x \in S\).

Details:

Trivially, \(v_0(x) \gt 0\) for \(x \in S\). Suppose that for some \(n \in \N\) we have \(v_n(x) \gt 0\) for almost all \(x \in S\). Recall that \[v_{n + 1}(x) = \int_{B_x} u_n(y) \, d\lambda(y), \quad x \in S \] where \(B_x = \{y \in S: x \rta y\}\) is the set of right neighbors of \(x \in S\). The integrand is positive for almost all \(x \in S\) by the induction hypothesis, and the domain of integration has positive measure: \(v(x) = \lambda(B_x) \gt 0\) for almost all \(x \in S\).

An analogous result hold for a left positive graph. Our last definition gives the generating functions associated with the sequence of walk functions.

The left generating functions for the graph \((S, \rta)\) is the formal power series defined by \[U(x, t) = \sum_{n = 0}^\infty u_n(x) t^n, \quad x \in S \] where \(u_n\) is the left walk function of order \(n \in \N\), given in .

Similarly, the right generating function and the walk generating function are respectively \begin{align*} V(x, t) & = \sum_{n = 0}^\infty v_n(x) t^n, \quad x \in S \\ W(t) & = \sum_{n = 0}^\infty w_n t^n \end{align*} where \(v_n\) and \(w_n\) are the right walk function and walk parameter of order \(n \in \N\). As our primary interest is in the left walk functions, so our primary interest is also in the left generating function. Assuming a positive radius of convergence at \(x \in S\), the generating function \(t \mapsto U(x, t)\) uniquely determines the corresponding sequence of left walk functions \((u_n(x): n \in \N)\). The left generating function satisfy simple integral equations.

Suppose that \((S, \rta)\) is a graph. Then \[U(x, t) = 1 + t \int_{y \rta x} U(y, t) \, d\lambda(y), \quad x \in S\]

Details:

The results follows easily from the recursive definition of the walk functions in . If \(x \in S\) then \begin{align*} 1 + t \int_{y \rta x} U(y, t) \, d\lambda(y) &= 1 + t \int_{y \rta x} \sum_{n = 0}^\infty a_n(y) t^n \, d\lambda(y) \\ &= 1 + t \sum_{n = 0}^\infty t^n \int_{y \rta x} a_n(y) \, d\lambda(y) = 1 + \sum_{n = 0}^\infty a_{n + 1}(x) t^{n + 1} = U(x, t) \end{align*}

Suppose that \((S, \rta)\) is a left regular graph of degree \(k \in (0, \infty)\). Then

\(u_n(x) = k^n\) for \(n \in \N\) and \(x \in S\)
\(U(x, t) = 1 / (1 - k t)\) for \(x \in S\) and \(|t| \lt 1 / k\)

Details:

These follow immediately from definitions and .

Topology

Suppose now that \(S\) has an LCCB topology, and that \(\ms S\) is the corresponding Borel \(\sigma\)-algebra (the \(\sigma\)-algebra generated by the topology). The product set \(S^n\) is given the product topology and the corresponding Borel \(\sigma\)-algebra for \(n \in \N_+\), which as noted in the Preface, is the product \(\sigma\)-algebra, \(\ms S^n\). So the topological setting here is consistent with the measure-theoretic setting in the previous subsections. A measurable graph \((S, \rta)\) in this setting might be referred to as a topological graph. Our interest is in the topological properties of \(\rta\) (as a subset of \(S^2\)) or the the topological properties of a set of walks (on the appropriate product set with the product topology). These sets might be open, closed, compact, etc. If \(\lambda\) is a reference measure, then the continuity properties of the walk functions are also of interest. We might also want to study graphs that have particular topological properties, for example a graph \((S, \rta)\) whose reflexive closure is topologically closed and whose irreflexive reduction is topologically open.

Examples

The Standard Continuous Graph

The interval \([0, \infty)\) is given the collection of Borel measurable subsets \(\ms B\) as the reference \(\sigma\)-algebra, and Lebesgue measure \(\lambda\) as the reference measure. With this structure, the measurable graph \(([0, \infty), \le) \) is the standard continuous graph.

For the standard continuous graph \(([0, \infty), \le)\),

The left walk function \(u_n\) of order \(n \in \N\) is given by \[u_n(x) = \frac{x^n}{n!}, \quad x \in [0, \infty)\]
The power of order \(n \in \N_+\) of the adjacency kernel \(L\) is given by \[L^n(x, y) = u_{n - 1}(y - x) = \frac{(y - x)^{n - 1}}{(n - 1)!}, \quad x, \, y \in [0, \infty), \, x \le y\]
The left generating function \(U\) is given by \(U(x, t) = e^{t x}\) for \(x \in [0, \infty)\) and \(t \in \R\).
The right \(\sigma\)-algebra is the reference \(\sigma\)-algebra \(\ms B\).

Details:

A walk of length \(n \in \N\) terminating in \(x \in [0, \infty)\) for the graph has the form \(0 \le x_1 \le x_2 \le \cdots \le x_n \le x\). The measure of this set of walks is \(x^n / n!\).
\(L(x, y) = \bs{1} (x \le y)\) for \(x, \, y \in [0, \infty)\) so the result follows from repeated integration.
From (a), \[U(x, t) = \sum_{n = 0}^\infty \frac{x^n} {n!} t^n = e^{t x}, \quad x \in [0, \infty), \, t \in \R\].
The right neighbor set at \(x \in [0, \infty)\) is \([x, \infty)\). This collections of intervals generates \(\ms B\).

Note that the right walk functions are infinite, so the graph is left finite and right positive, but not right finite. The associated left \(\sigma\)-algebra is also the reference \(\sigma\)-algebra \(\ms B\). The standard continuous graph is studied in detail in Chapter 3.

The Standard Discrete Graph

As with all countable sets, \(\N\) is given the \(\sigma\)-algebra \(\ms P(\N)\) of all subsets, with counting measure \(\#\) as the reference measure. With this structure, \((\N, \le)\) is the standard discrete graph.

For the standard discrete space \((\N, \le)\),

The left walk function \(u_n\) for order \(n \in \N\) is given by \[u_n(x) = \binom{x + n}{n}, \quad x \in \N\]
The power of order \(n \in \N_+\) of the adjacency kernel \(L\) is \[L^n(x, y) = u_{n - 1}(y - x) = \binom{y - x + n - 1}{n - 1}, \quad x, \, y \in \N, \, x \le y\]
The left generating function \(U\) is given by \[U(x, t) = \frac{1}{(1 - t)^{x + 1}}, \quad x \in \N, \, t \in (-1, 1)\]
The right \(\sigma\)-algebra is the reference \(\sigma\)-algebra \(\ms P(\N)\).

Details:

A walk of order \(n \in \N\) terminating in \(x \in \N\) for the graph has the form \(0 \le x_1 \le x_2 \le \cdots \le x_n \le x\). The number of such walks is \(\binom{x + n}{n}\).
\(L(x, y) = \bs{1}(x \le y)\) for \(x, \, y \in \N\) so the result follows from repeated sums.
From (a), \[U(x, t) = \sum_{n = 0}^\infty \binom{x + n}{n} t^n = \frac{1}{(1 - t)^{x + 1}}, \quad x \in \N, \, t \in (-1, 1)\]
The right neighbor set at \(x \in \N\) is \(A_x = \{x, x + 1, x + 2, \ldots\}\). So \(\{x\} = A_x - A_{x + 1} \in \ms A\) for \(x \in \N\).

Once again, the right walk functions are infinite so the graph is left finite and right positive, but not right finite. The associated left \(\sigma\)-algebra is also \(\ms P(\N)\). The standard discrete graph is studied in detail in Chapter 4.

A Triangle Graph

The trianlge graph defined in this subsection is useful for counterexamples and because the computations are easy.

Let \(S = \{1, 2, 3\}\) and define the relation \(\rta\) on \(S\) by \(1 \rta 2\), \(2 \rta 1\), \(2 \rta 2\), \(2 \rta 3\), \(3 \rta 1\) and \(3 \rta 3\). The adjacency matrix is \[ L = \left[\begin{matrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{matrix}\right]\]

So the graph \((S, \rta)\) is strongly connected and is not symmetric. It has a bi-directional edge between 1 and 2, directed edges from 2 to 3 and from 3 to 1, and loops at 2 and 3.

For the triangle graph \((S, \rta)\) define in ,

Find the period.
Discuss the regularity.
Find the right \(\sigma\)-algebra \(\ms A\) and the left \(\sigma\)-algebra \(\ms B\).
Find the eigenvalues and the corresponding eigenvectors.
Is \(L\) diagonalizable?
Find \(L^n\) for \(n \in \{2, 3, \ldots\}\).
Find the walk functions \(u_n\), \(v_n\), \(w_n\) of order \(n \in \N\).

Details:

The graph is aperiodic, since there are loops at vertices 2 and 3.
The graph is left regular of degree 2, but is not right regular.
The right neighbor sets are \(A_1 = \{2\}\), \(A_2 = S\), \(A_3 = \{1, 3\}\), so \(\ms A = \sigma(\{2\}) = \{\emptyset, \{2\}, \{1, 3\}, S\}\). The left neighbor sets are \(B_1 = \{2, 3\}\), \(B_2 = \{1, 2\}\), \(B_3 = \{2, 3\}\), so \(\ms B = \ms P(S)\).
2 is a simple eigenvalue and 0 is an eigenvalue of multiplicity 2. An eigenvector corresponding to 2 is \((1, 2, 1)\), and 0 has a one-dimensional eigenspace generated by \((1, 0, -1)\).
\(L\) is not diagonalizable since there is not a set of 3 linearly independent eigenvectors.
For \(n \in \{2, 3, \ldots\}\), \[L^n = \left[\begin{matrix} 2^{n - 2} & 2^{n - 2} & 2^{n - 2} \\ 2^{n - 1} & 2^{n - 1} & 2^{n - 1} \\ 2^{n - 2} & 2^{n - 2} & 2^{n - 2} \end{matrix} \right]\]
In vector form, \(u_n = (2^n, 2^n, 2^n)\) for \(n \in \N\). Similarly, \(v_0 = (1, 1, 1)\), \(v_1 = (1, 3, 2)\) and \(v_n = 3 \cdot (2^{n - 2}, 2^{n - 1}, 2^{n - 2})\) for \(n \in \{2, 3, \ldots\}\). Finallly, \(w_n = 3 \cdot 2^n\) for \(n \in \N\).

Diamond Graphs

The diamond graphs that we consider are simple graphs that are useful for examples and small enough for hand calculations.

Let \(S = \{1, 2, 3, 4\}\).

Define the symmetric relation \(\lfrta\) on \(S\) by \(1 \lfrta 2\), \(1 \lfrta 4\), \(2 \lfrta 3\), \(2 \lfrta 4\), \(3 \lfrta 4\). The undirected graph \((S, \lfrta)\) is known as the diamond graph. It is also an abstract version of the Wheatstone bridge graph.
Define the relation \(\rta\) on \(S\) by \(1 \rta 2\), \(1 \rta 3\), \(2 \rta 4\), \(3 \rta 4\), \(4 \rta 1\). We will refer to \((S, \rta)\) as the directed diamond graph.

For the diamond graph \((S, \lfrta)\), find each of the following:

The period of the graph.
The adjacency matrix \(L\).
The eigenvalues and corresponding eigenvectors of \(L\).
The walk function \(u_n\) of order \(n \in \N\).
The generating function \(U\).
The associated \(\sigma\)-algebra \(\ms A\).

Details:

\((S, \lfrta)\) is aperiodic.
\[L = \left[\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix} \right]\]
The eigenvalues of \(L\) are \(\frac 1 2 (1 + \sqrt{17})\), \(\frac 1 2 (1 - \sqrt{17})\), \(-1\), \(0\), with corresponding eigenvectors \[\left(\frac{\sqrt{17} - 1}{4}, 1, \frac{\sqrt{17} - 1}{4}, 1\right), \; \left(\frac{-\sqrt{17} - 1}{4}, 1, \frac{-\sqrt{17} - 1}{4}, 1\right), \; (0, -1, 0, 1), \; (-1, 0, 1, 0)\]
\begin{align*} u_n(1) = u_n(4) & = \frac{\sqrt{17} - 5}{2 \sqrt{17}} \left(\frac{1 - \sqrt{17}}{2}\right)^n + \frac{\sqrt{17} + 5}{2 \sqrt{17}} \left(\frac{1 + \sqrt{17}}{2}\right)^n \\ u_n(2) = u_n(3) &= \frac{\sqrt{17} - 3}{2 \sqrt{17}} \left(\frac{1 - \sqrt{17}}{2}\right)^n + \frac{\sqrt{17} + 3}{2 \sqrt{17}} \left(\frac{1 + \sqrt{17}}{2}\right)^n \end{align*}
\begin{align*} U(1, t) = U(4, t) &= \frac{\sqrt{17} - 5}{\sqrt{17}} \frac{1}{2 - t(1 - \sqrt{17})} + \frac{\sqrt{17} + 5}{\sqrt{17}} \frac{1}{2 - t(1 + \sqrt{17})}, \quad |t| \lt \frac{2}{1 + \sqrt{17}} \\ U(2, t) = U(3, t) &= \frac{\sqrt{17} - 3}{\sqrt{17}} \frac{1}{2 - t(1 - \sqrt{17})} + \frac{\sqrt{17} + 3}{\sqrt{17}} \frac{1}{2 - t(1 + \sqrt{17})}, \quad |t| \lt \frac{2}{1 + \sqrt{17}} \end{align*}
\(\ms A = \sigma\{\{1\}, \{4\}, \{2, 3\}\} = \{\emptyset, \{1\}, \{4\}, \{1, 4\}, \{2, 3\}, \{1, 2, 3\}, \{2, 3, 4\}, S\}\)

For the directed diamond graph \((S, \rta)\), find each of the following:

The period of the graph.
The adjacency matrix \(L\).
The real eigenvalues and corresponding eigenvectors of \(L\).
The left walk function \(u_n\) of order \(n \in \N\).
The left generating function \(U\).
The associated right \(\sigma\)-algebra \(\ms A\).

Details:

\((S, \rta)\) is periodic with period 3.
\[L = \left[\begin{matrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{matrix}\right]\]
Eigenvalue \(2^{1/3}\) has eigenvector \(\left(2^{1/3}, 2^{-1/3}, 2^{-1/3}, 1\right)\). Eigenvalue \(0\) has eigenvector \((0, -1, 1, 0)\). There is also a pair of conjugate complex eigenvalues: \(2^{-2/3}\left(-1 \pm \sqrt 3 i \right)\).
- If \(n = 0 \bmod 3\) then \(u_n(x) = 2^{n / 3}\) for \(x \in \{1, 2, 3, 4\}\).
- If \(n = 1 \bmod 3\) then \(u_n(x) = 2^{(n - 1) / 3}\) for \(x \in \{1, 2, 3\}\) and \(u_n(4) = 2 \cdot 2^{(n - 1) / 3}\).
- If \(n = 2 \bmod 3\) then \(u_n(x) = 2 \cdot 2^{(n - 2) / 3}\) for \(x \in \{1, 4\}\) and \(u_n(x) = 2^{(n - 2) / 3}\) for \(x \in \{2, 3\}\).
\begin{align*} U(1, t) &= \frac{1 + t + 2 t^2}{1 - 2 t^3}, \quad |t| \lt \frac{1}{2^{1/3}} \\ U(2, t) = U(3, t) &= \frac{1 + t + t^2}{1 - 2 t^3}, \quad |t| \lt \frac{1}{2^{1/3}} \\ U(4, t) &= \frac{1 + 2 t + 2 t^2}{1 - 2 t^3}, \quad |t| \lt \frac{1}{2^{1/3}} \end{align*}
\(\ms A = \sigma\{\{1\}, \{4\}, \{2, 3\}\} = \{\emptyset, \{1\}, \{4\}, \{1, 4\}, \{2, 3\}, \{1, 2, 3\}, \{2, 3, 4\}, S\}\)

Note that the reverse graph \((S, \lfa)\) is isomporhpic to the graph \((S, \rta)\) itself, under the mapping \(1 \mapsto 4\), \(2 \mapsto 2\), \(3 \mapsto 3\), \(4 \mapsto 1\). So if follows that the right walk function \(v_n\) of order \(n \in \N\) satisfies \(v_n(1) = u_n(4)\), \(v_n(4) = u_n(1)\) and \(v_n(x) = u_n(x)\) for \(x \in \{2, 3\}\). It also follows that the left \(\sigma\)-algebra \(\ms B\) is the same as the right \(\sigma\)-algebra \(\ms A\).

The Bull Graph

Let \(S = \{1, 2, 3, 4, 5\}\) and define the symmetric relation \(\lfrta\) on \(S\) by \(1 \lfrta 2\), \(1, \lfrta 3\), \(2 \lfrta 3\), \(2 \lfrta 4\), \(3 \lfrta 5\). The undirected graph \((S, \lfrta)\) is known as the bull graph and is shown in the figure below.

For the bull graph, find each of the following:

The period of the graph.
The adjacency matrix \(L\).
The eigenvalues and corresponding eigenvectors of \(L\).
The walk function \(u_n\) of order \(n \in \N\).
The generating function \(U\).
The associated \(\sigma\)-algebra \(\ms A\).

Details:

\((S, \lfrta)\) is aperiodic.
\[L = \left[\begin{matrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 &1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{matrix} \right]\]
The eigenvalues of \(L\) are \(\frac 1 2 (1 + \sqrt{13})\), \(\frac 1 2 (1 - \sqrt{13})\), \(\frac 1 2 (-1 + \sqrt{5})\), \(\frac{1}{2}(-1 - \sqrt{5})\), \(0\) with corresponding eigenvectors \begin{align*} & \left(2, \frac{1 + \sqrt{13}}{2}, \frac{1 + \sqrt{13}}{2}, 1, 1\right), \; \left(0, \frac{1 + \sqrt{5}}{2}, \frac{-1 - \sqrt{5}}{2}, -1, -1\right), \\ &\left(2, \frac{1 - \sqrt{13}}{2}, \frac{1 - \sqrt{13}}{2}, 1, 1\right),\; \left(0, \frac{1 - \sqrt{5}}{2}, \frac{-1 + \sqrt{5}}{2}, -1, 1\right), \; (-1, 0, 0, 1, 1) \end{align*}
\begin{align*} u_n(1) &= \frac{\sqrt{13} - 5}{\sqrt{13}} \left(\frac{1 - \sqrt{13}}{2}\right)^{n-1} + \frac{\sqrt{13} + 5}{\sqrt{13}} \left(\frac{1 + \sqrt{13}}{2}\right)^{n-1} \\ u_n(2) = u_n(3) &= \frac{\sqrt{13} - 5}{2 \sqrt{13}}\left(\frac{1 - \sqrt{13}}{2}\right)^n + \frac{\sqrt{13} + 5}{2 \sqrt{13}} \left(\frac{1 + \sqrt{13}}{2}\right)^n \\ u_n(4) = u_n(5) &= \frac{\sqrt{13} - 5}{2 \sqrt{13}} \left(\frac{1 - \sqrt{13}}{2}\right)^{n-1} + \frac{\sqrt{13} + 5}{2 \sqrt{13}} \left(\frac{1 + \sqrt{13}}{2}\right)^{n-1} \end{align*}
\begin{align*} U(1, t) &= 1 + \frac{\sqrt{13}-5}{\sqrt{13}} \frac{t (1 - \sqrt{13})}{2 - t(1 - \sqrt{13})} + \frac{\sqrt{13}+5}{\sqrt{13}} \frac{t (1 + \sqrt{13})}{2 - t(1 + \sqrt{13})}, \quad |t| \lt \frac{2}{1 + \sqrt{13}}\\ U(2, t) = U(3, t) &= \frac{\sqrt{13}-5}{\sqrt{13}} \frac{1}{2 - t(1 - \sqrt{13})} + \frac{\sqrt{13}+5}{\sqrt{13}} \frac{1}{2 - t(1 + \sqrt{13})}, \quad |t| \lt \frac{2}{1 + \sqrt{13}} \\ U(4, t) = U(5, t) &= 1 + \frac{\sqrt{13}-5}{2 \sqrt{13}} \frac{t (1 - \sqrt{13})}{2 - t(1 - \sqrt{13})} + \frac{\sqrt{13}+5}{2 \sqrt{13}} \frac{t (1 + \sqrt{13})}{2 - t(1 + \sqrt{13})}, \quad |t| \lt \frac{2}{1 + \sqrt{13}} \end{align*}
\(\ms A = \ms P(S)\), the collection of all subsets of \(S\).

Complete and Equality Graphs

Suppose \(S\) is a nonempty set.

The \(\sigma\)-algebra associated with the complete reflexive graph \((S, \equiv)\) is the trivial \(\sigma\)-algebra \(\{S, \emptyset\}\).
For the equality graph \((S, =)\), and the complete irreflexive graph \((S, \ne)\), the associated \(\sigma\)-algebra is the \(\sigma\)-algebra of countable and co-countable sets: \[\ms C = \{A \subseteq S: A \text{ is countable or } A^c \text{ is countable}\}\]

Details:

The neighbor set of \(x \in S\) is \(S\).
The neighbor set of \(x \in S\) for the graph \((S, =)\) is \(\{x\}\) so the associated \(\sigma\)-algebra is \(\sigma\{\{x\}: x \in S\} = \ms C\). The \(\sigma\)-algebra associated with \((S, \ne)\) is also \(\ms C\) by .

So if \(S\) is countable, then the \(\sigma\)-algebra associated with \((S, =)\) and with \((S \ne)\) is \(\ms P(S)\), the reference \(\sigma\)-algebra.

Suppose that \(S\) is an uncoutable set. Then \((S, =)\) is not measurable with respect to its associated \(\sigma\)-algebra.

Details:

The \(\sigma\)-algebra associated with \((S, =)\) is \(\ms C\), the collection of countable and co-countable sets, defined in . If \(S\) is uncountable, it's well known that \(\{(x, x): x \in S\}\) is not in \(\ms C^2\).

Suppose now that \((S, \ms S, \lambda)\) is a finite measure space. Then the complete reflexive graph \((S, \equiv)\) is measuable and is regular with degree \(k = \lambda(S)\), so the walk functions and generating function are given in . On the other hand, supposse that \((S, =)\) is measurable so that the complete irreflexive graph \((S, \ne)\) is also measurable. If \(\lambda(S \setminus \{x\}) = k\) for all \(x \in S\) then \((S, \ne)\) is regular with degree \(k\) so the walk functions and generating functions are given in . In particular, if \(S\) is a set with \(n \in \N_+\) elements, then \((S, \equiv)\) is regular of degree \(n\) and \((S, \ne)\) is regular of degree \(n - 1\).

The Cycle Graph

Let \(S = \{1, 2, \ldots, k\}\) where \(k \in \{3, 4, \ldots\}\). Define the relation \(\lfrta\) on \(S\) by \(x \lfrta x + 1\) and \(x \lfrta x - 1\) for \(x \in \{1, 2, \ldots, k\}\) where we interpret the addition and subtraction so that \(k + 1 = 1\) and \(1 - 1 = k\). The graph \((S, \lfrta)\) is the cycle graph of order \(k\). The cycle is shown below; the order \(k\) can be varied with the scrollbar.

The cycle is regular of degree 2, so the walk functions and generating function are given in with \(k = 2\).

For the cycle graph \((S, \lfrta)\) of order \(k \in \{3, 4, \ldots\}\), find each of the following:

The period.
The associated \(\sigma\)-algebra \(\ms A\).

Details:

If \(k\) is odd, the graph is aperiodic. If \(k\) is even the period is 2.
Let \(A_x\) denote the neighbor set of \(x \in S\).
- If \(k = 3\) the cycle is also the complete irreflexive graph on \(S\) so \(\ms A = \ms P(S)\) by .
- The case \(k = 4\) is exceptional. The neighbor sets are \(A_1 = A_3 = \{2, 4\}\) and \(A_2 = A_4 = \{1, 3\}\). So \(\ms A = \sigma(\{1, 3\}) = \{\emptyset, \{1, 3\}, \{2, 4\}, S\}\).
- If \(k \ge 5\) then \(A_2 \cap A_k = \{1\}\), \(A_1 \cap A_{k - 1} = \{k\}\), and \(A_{x - 1} \cap A_{x + 1} = \{x\}\) for \(x \in \{3, 4, \ldots, k - 2\}\). Hence \(\ms A = \ms P(S)\).

The Star Graph

Let \(S = \{0, 1, \ldots, k\}\) where \(k \in \{3, 4, \ldots\}\). Define the relation \(\lfrta\) on \(S\) by \(0 \lfrta x\) and \(x \lfrta 0\) for \(x \in \{1, 2, \ldots, k\}\). The graph \((S, \lfrta)\) is the star graph of order \(k\). Vertex \(0\) is the center and the vertices \(\{1, 2, \ldots, k\}\) are endponts. The star is shown below; the order \(k\) can be varied with the scrollbar.

The star is an example of a tree and is also an example of a complete bipartite graph. Both of these classes of graphs will be studied in later sections.

For the star graph \((S, \lfrta)\) of order \(k \in \{3, 4, \ldots\}\), find each of the following:

The period of the graph.
The walk functions.
The generating function.
The associated \(\sigma\)-algebra.

Details:

The graph is periodic with period 2.
The walk functions are given as follows: \begin{align*} & u_{2 n}(0) = k^n, \, u_{2 n + 1}(0) = k^{n + 1}, \quad n \in \N \\ & u_{2 n}(x) = u_{2 n + 1}(x) = k^n, \quad x \in \{1, 2, \ldots, k\}, \, n \in \N_+ \end{align*}
The generating function is given by \begin{align*} U(0, t) & = \frac{1 + k t}{1 - k t^2}, \quad |t| \lt \frac{1}{\sqrt{k}} \\ U(x, t) & = \frac{1 + t}{1 - k t^2}, \quad |t| \lt \frac{1}{\sqrt{k}}, \; x \in \{1, 2, \ldots, k\} \end{align*}
Note that the neighbor sets are \(A_0 = \{1, 2, \ldots, k\}\) and \(A_x = \{0\}\) for \(x \in \{1, 2, \ldots, k\}\). So the associated \(\sigma\)-algebra is \(\ms A = \sigma(\{0\}) = \{\emptyset, \{0\}, S \setminus \{0\}, S\}\).

The Wheel Graph

For \(k \in \{3, 4, \ldots\}\), the wheel graph of order \(k\) is the union of the cycle in and the star in . Vertex \(0\) is the center and the vertices \(\{1, 2, \ldots, k\}\) form a cycle on the rim of the wheel. The wheel graph is shown below; the order \(k\) can be varied with the scrollbar.

For the wheel graph \((S, \lfrta)\) of order \(k \in \{3, 4, \ldots\}\), find each of the following:

The period.
The walk functions.
The associated \(\sigma\)-algebra.

Details:

The graph is aperiodic.
The walk functions are given by \begin{align*} u_n(0) & = \left(\frac{1}{2} + \frac{1}{\sqrt{k + 1}}\right) k \left(1 + \sqrt{k + 1}\right)^{n-1} + \left(\frac{1}{2} - \frac{1}{\sqrt{k + 1}}\right) k \left(1 - \sqrt{k + 1}\right)^{n-1} \\ u_n(x) & = \left(\frac{1}{2} + \frac{1}{\sqrt{k + 1}}\right)\left(1 + \sqrt{k + 1}\right)^n + \left(\frac{1}{2} - \frac{1}{\sqrt{k + 1}}\right) \left(1 - \sqrt{k + 1}\right)^n, \quad x \in \{1, 2, \ldots, k\} \end{align*} To see this, let \(x\) be a point on the rim and recall that 0 is the center. Let \(a_n = u_n(0)\). By symmetry, \(u_n\) is constant on the points on the rim, so let \(b_n\) denote the common value. Starting at \(0\), the next vertex on a walk must be on the rim. Starting at a vertex on the rim, the next vertex on a walk must be one of the neighbors on the rim or the center. Thus \(a_{n + 1} = k b_n\) and \(b_{n + 1} = 2 b_n + a_n\) for \(n \in \N\), subject to the initial conditions \(a_0 = b_0 = 1\). Substituting we get the second order difference equation \[b_{n + 1} = 2 b_n + k b_{n - 1}, \quad n \in \N_+\] subject to the initial conditions \(b_0 = 1\), \(b_1 = 3\). The characteristic equation is \(r^2 - 2 r - k = 0\) with solutions \(r = 1 \pm \sqrt{k + 1}\). So the general solution is \[b_n = c_1\left(1 + \sqrt{k + 1}\right)^n + c_2 \left(1 - \sqrt{k + 1}\right)^n, \quad n \in \N\] Applying the initial conditions gives the expression for \(b_n\). Then returning to \(a_n = k b_{n - 1}\) for \(n \in \N_+\) gives the expression for \(a_n\).
Just as with the cycle graph in , the case \(k = 4\) is exceptional.
- If \(k = 4\) then \(\ms A = \sigma(\{0\}, \{1, 3\}) = \{\emptyset, \{0\}, \{1, 3\}, \{2, 4\}, \{0, 1, 3\}, \{0, 2, 4\}, \{1, 2, 3, 4\}, S\}\).
- If \(k \ne 4\) then \(\ms A = \ms P(S)\).
Note also that the wheel of order 3 is also the complete irreflexive graph on 4 vertices.

For both the star graph and the wheel graph, 0 is a universal point since it is connected to all of the other vertices. Universal points are studied in more detail in Section 7.