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\)).

\(\{w \in S: w \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 Paths

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\).

Paths in a graph will be fundamentally important in our study of abstract reliability.

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

If the vertices are distinct, the sequence is a simple path.
If \(x_1 = x_{n+1}\) the sequence is a closed path.
If the vertices are distinct except that \(x_1 = x_{n+1}\), the sequence is a simple closed path.

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 path is sequence of adjacent vertices in the graph. Often the term walk is used instead of path and cycle instead of closed path. There are other terms (trail for example) and in fact the terminology is not completely standard. Our choice of terminology is made to avoid using several separate terms. Of course, we can also have infinite paths. If \(x_i \in S\) for \(i \in \N_+\) and \(x_1 \rta x_2 \rta \cdots\) then \((x_1, x_2, \ldots)\) is an infinite path in \((S, \rta)\) starting in \(x_1\).

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 path 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 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 last result 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 and Topology

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. On the other hand, there is a natural \(\sigma\)-algebra associated with a graph:

Suppose that \((S, \rta)\) is a graph, and let \(A_x = \{y \in S: x \rta y\}\) denote the set of right neighbors of \(x \in S\).

\(\ms A = \sigma\{A_x: x \in S\}\) is the \(\sigma\)-algebra associated with \((S, \rta)\).
If \((S, \rta)\) is measurable with respect to \((S, \ms S)\) then \(\ms A \subseteq \ms S\).

Details:

For part (b), the set \(A = \{(x, y) \in S^2: x \rta y\} \in \ms S^2\). The set \(A_x\) of right neighbors of \(x \in S\) is simply the cross section of \(A\) at \(x\), and hence \(A_x \in \ms S\).

So the \(\sigma\)-algebra associated with a graph is simply the \(\sigma\)-algebra generated by the collection of right neighbors. The reason for using right neighbors, as opposed to left neighbors or other possible sets, will be clear when we study probability on graphs in Section 3. 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. When the graph is measurable, the case \(\ms A = \ms S\) is of considerable interest. 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\).

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. Various collections of paths are measurable:

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 paths 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 paths of length \(n\).
For \(y \in S\), this is the cross section on the right at \(y\) of the set of paths 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 paths of length \(n + 1\).

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

Details:

For \(x \in S\), the right neighbor set of \((S, \not \rta)\) at \(x\) is the complement of the right neighbor set of \((S, \rta)\) at \(x\).

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.

A \(\sigma\)-finite measure \(\lambda\) on \((S, \ms S)\) is (right) supported by the graph \((S, \rta)\) if \[\lambda\{y \in S: x \rta y\} \gt 0, \quad x \in S\]

That is, the measure of the set of right neighbors of \(x\) is positive for each \(x \in S\). The reason for this particular definition of support (as with definition ) will be clear when we study probability on graphs in Section 3. 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 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 kernel, 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\). Powers of the adjacency kernel give information about the measure of paths 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 the middle parts of paths of length \(n\) from \(x\) to \(y\). If \(n \in \N_+\) then \((\bs 1 L^n)(x)\) is the measure of the set of the initial parts of paths of length \(n + 1\) that terminate in \(x\), while \((L^n \bs 1)(x)\) is the measure of the terminal parts of paths of length \(n + 1\) that start in \(x\). The first of these will play an important role and is formalized in definition .

Suppose again that \((S, \rta)\) is a graph with adjacency kernel \(L\). For \(n \in \N\), the (left) path function of order \(n\) for \((S, \rta)\) is the function \(\gamma_n = \bs 1 L^n: S \to [0, \infty]\), so that \(\gamma_0(x) = 1\) for \(x \in S\), and for \(n \in \N_+\), \[\gamma_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\]

Note that \(\gamma_n\) is measurable for \(n \in \N\). We often abbreviate \(\gamma_1\) by \(\gamma\) so that \(\gamma(x) = \lambda\{u \in S: u \rta x\}\) for \(x \in S\), the measure of the set of left neighbors \(x\). In the discrete case, \(\gamma(x)\) is the number of left neighbors of \(x\). We can rephrase the definition in a recursive way:

The path functions are defined recursively by \(\gamma_0(x) = 1\) for \(x \in S\) and for \(n \in \N\), \[\gamma_{n + 1}(x) = \int_{y \rta x} \gamma_n(y) \, d\lambda(y), \quad x \in S\]

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 \(\{u \in S: u \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\)). 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.

A graph \((S, \rta)\) is left finite if \(\gamma(x) = \lambda\{u \in S: u \rta x\} \lt \infty\) for almost every \(x \in S\).

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

Details:

The statement is true for \(n = 0\) by definition. Suppose the statement is true for a given \(n \in \N\). Since \(\rta\) is transitive, \(y \rta x\) implies \(\{u \in S: u \rta y\} \subseteq \{u \in S: u \rta x\}\) and so \(\gamma(y) \le \gamma(x)\) almost always when \(y \rta x\). Hence by the induction hypothesis, for almost all \(x \in S\), \[\gamma_{n+1}(x) = \int_{y \rta x} \gamma_n(y) \, d\lambda(y) \le \int_{y \rta x} \gamma^n(y) \, d\lambda(y) \le \int_{y \rta x} \gamma^n(x) \, d\lambda(y) = \gamma^{n+1}(x)\]

So for a transitive, left-finite graph, \(\gamma_n(x) \lt \infty\) for almost all \(x \in S\) and all \(n \in \N\). Our next definition is the generating function associated with the sequence of path functions.

The (left) path generating function \(\Gamma\) of the graph \((S, \rta)\) is defined by \[\Gamma(x, t) = \sum_{n = 0}^\infty \gamma_n(x) t^n; \quad x \in S, \; |t| \lt \rho(x) \] where \(\rho(x)\) is the radius of convergence of the power series at \(x\).

For fixed \(x \in S\), \(t \mapsto \Gamma(x, t)\) is the generating function (in the combinatorial sense) of the sequence of path functions \(\left(\gamma_n(x): n \in \N\right)\). So, assuming that \(\rho(x) > 0\), the mapping \(t \mapsto \Gamma(x, t)\) determines \(\left(\gamma_n(x): n \in \N\right)\). The path generating function satisfies a simple integral equation.

Suppose that \((S, \rta)\) is a graph with path generating function \(\Gamma\). Then \[\Gamma(x, t) = 1 + t \int_{y \rta x} \Gamma(y, t) \, d\lambda(y), \quad x \in S, \, |t| \le \rho(x)\]

Details:

The result follows easily from the recursive definition of the path functions. For \(x \in S\) and \(|t| \lt \rho(x)\) , \begin{align*} 1 + t \int_{y \rta x} \Gamma(y, t) \, d\lambda(y) &= 1 + t \int_{y \rta x} \sum_{n=0}^\infty \gamma_n(y) t^n \, d\lambda(y) \\ &= 1 + t \sum_{n=0}^\infty t^n \int_{y \rta x} \gamma_n(y) \, d\lambda(y) = 1 + \sum_{n=0}^\infty \gamma_{n+1}(x) t^{n+1} = \Gamma(x, t) \end{align*}

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

\((S, \rta)\) is right regular of degree \(k\) if \(\lambda\{y \in S: x \rta y\} = k\) for all \(x \in S\).
\((S, \rta)\) is left regular of degree \(k\) if \(\lambda\{w \in S: w \rta 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 that \((S, \rta)\) is a left regular graph of degree \(k \in (0, \infty)\). Then

\(\gamma_n(x) = k^n\) for \(n \in \N\) and \(x \in S\)
\(\Gamma(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 paths (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 path 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

Standard Graphs

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 path function \(\gamma_n\) of order \(n \in \N\) is given by \[\gamma_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) = \gamma_{n - 1}(y - x) = \frac{(y - x)^{n - 1}}{(n - 1)!}, \quad x, \, y \in [0, \infty), \, x \le y\]
The path generating function \(\Gamma\) is given by \(\Gamma(x, t) = e^{t x}\) for \(x \in [0, \infty)\) and \(t \in \R\).
The associated \(\sigma\) algebra is the reference \(\sigma\)-algebra \(\ms B\).

Details:

A path 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 paths 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), \[\Gamma(x, t) = \sum_{n = 0}^\infty \frac{x^n} {n!} t^n = e^{t x}, \quad x \in [0, \infty), \, t \in \R\].
Note that the neighbor set at \(x \in [0, \infty)\) is \([x, \infty)\). It follows that \([a, b)\) is in the associated \(\sigma\)-algebra for each \(a, \, b \in [0, \infty)\) with \(a \le b\). This collection of intervals generates \(\ms B\).

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 path function \(\gamma_n\) for order \(n \in \N\) is given by \[\gamma_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) = \gamma_{n - 1}(y - x) = \binom{y - x + n - 1}{n - 1}, \quad x, \, y \in \N, \, x \le y\]
The path generating function \(\Gamma\) is given by \[\Gamma(x, t) = \frac{1}{(1 - t)^{x + 1}}, \quad x \in \N, \, t \in (-1, 1)\]
The associated \(\sigma\)-algebra the reference \(\sigma\)-algebra \(\ms P(\N)\).

Details:

A path 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 paths 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), \[\Gamma(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)\]
Note that the neighbor set at \(x \in \N\) is \(\{x, x + 1, x + 2, \ldots\}\) so it follows that \(\{x\}\) is in the associated \(\sigma\)-algebra for each \(x \in \N\).

Three Simple Graphs

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 adjacency matrix \(L\).
The eigenvalues and corresponding eigenvectors of \(L\).
The path function \(\gamma_n\) of order \(n \in \N\).
The path generating function \(\Gamma\).
The associated \(\sigma\)-algebra.

Details:

\[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*} \gamma_n(1) = \gamma_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 \\ \gamma_n(2) = \gamma_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*} \Gamma(1, t) = \Gamma(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}} \\ \Gamma(2, t) = \Gamma(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*}
\(\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 adjacency matrix \(L\).
The real eigenvalues and corresponding eigenvectors of \(L\).
The path function \(\gamma_n\) of order \(n \in \N\).
The path generating function \(\Gamma\).
The associated \(\sigma\)-algebra.

Details:

\[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)\).
\begin{align*} \gamma_n &= \left(2^{n/3}, 2^{n/3}, 2^{n/3}, 2^{n/3}\right), \quad n = 0 \mod 3 \\ \gamma_n &= \left(2^{(n-1)/3}, 2^{(n-1)/3}, 2^{(n-1)/3}, 2^{(n+2)/3}\right), \quad n = 1 \mod 3 \\ \gamma_n &= \left(2^{(n+1)/3}, 2^{(n-2)/3}, 2^{(n-2)/3}, 2^{(n+1)/3}\right), \quad n = 2 \mod 3 \end{align*}
\begin{align*} \Gamma(1, t) &= \frac{1 + t + 2 t^2}{1 - 2 t^3}, \quad |t| \lt \frac{1}{2^{1/3}} \\ \Gamma(2, t) = \Gamma(3, t) &= \frac{1 + t + t^2}{1 - 2 t^3}, \quad |t| \lt \frac{1}{2^{1/3}} \\ \Gamma(4, t) &= \frac{1 + 2 t + 2 t^2}{1 - 2 t^3}, \quad |t| \lt \frac{1}{2^{1/3}} \end{align*}
\(\sigma\{\{1\}, \{4\}, \{2, 3\}\} = \{\emptyset, \{1\}, \{4\}, \{1, 4\}, \{2, 3\}, \{1, 2, 3\}, \{2, 3, 4\}, S\}\)

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 adjacency matrix \(L\).
The eigenvalues and corresponding eigenvectors of \(L\).
The path function \(\gamma_n\) of order \(n \in \N\).
The path generating function \(\Gamma\).
The associated \(\sigma\)-algebra.

Details:

\[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*} \gamma_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} \\ \gamma_n(2) = \gamma_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 \\ \gamma_n(4) = \gamma_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*} \Gamma(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}}\\ \Gamma(2, t) = \Gamma(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}} \\ \Gamma(4, t) = \Gamma(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 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 nad is regular with degree \(a = \lambda(S)\), so the path functions and generating function are given in with \(k = a\). 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\}) = b\) for all \(x \in S\) then \((S, \ne)\) is regular with degree \(b\) so the path functions and generating functions are given in with \(k = b\). 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\).

Cylces, Stars, and Wheels

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 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 path functions and generating function are given in with \(k = 2\).

Let \(\ms A\) denote the \(\sigma\)-algebra associated with the cycle \((S, \lfrta)\) of order \(k \in \{3, 4, \ldots\}\).

If \(k = 4\) then \(\ms A = \{\emptyset, \{1, 3\}, \{2, 4\}, S\}\).
If \(k \ne 4\) then \(\ms A = \ms P(S)\).

Details:

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\}\). 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\}\).

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 graph is a tree, and is alos an example of a complete bipartite graph. 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.

Suppose that \((S, \lfrta)\) is the star of order \(k \in \{3, 4, \ldots\}\).

The path functions are given as follows: \begin{align*} & \gamma_{2 n}(0) = \gamma_{2 n}(x) = \gamma_{2 n + 1}(x) = k^n, \quad n \in \N, \; x \in \{1, 2, \ldots, k\} \\ & \gamma_{2 n - 1}(0) = k^n, \quad n \in \N_+ \end{align*}
The path generating function are given by \begin{align*} \Gamma(0, t) & = \frac{1 + k t}{1 - k t^2}, \quad |t| \lt \frac{1}{\sqrt{k}} \\ \Gamma(x, t) & = \frac{1 + t}{1 - k t^2}, \quad |t| \lt \frac{1}{\sqrt{k}}, \; x \in \{1, 2, \ldots, k\} \end{align*}
The associated \(\sigma\)-algebra is \(\{\emptyset, \{0\}, S \setminus \{0\}, S\}\), the \(\sigma\)-algebra generated by the singleton \(\{0\}\)

Details:

Note that the neighbor sets are \(A_0 = \{1, 2, \ldots, k\}\) and \(A_x = \{0\}\) for \(x \in \{1, 2, \ldots, k\}\).

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.

Let \((S, \lfrta)\) be the wheel of order \(k \in \{3, 4, \ldots\}\). The path functions are given by \begin{align*} \gamma_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} \\ \gamma_n(x) & = \left(\frac{1}{2} + \frac{1}{\sqrt{k + 1}}\right)\left(1 + \sqrt{k + 1}\right)^k + \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*}

Details:

Let \(x\) be a point on the rim and recall that 0 is the center. Let \(a_n = \gamma_n(0)\). By symmetry, \(\gamma_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 path must be on the rim. Starting at a vertex on the rim, the next vertex on a path 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\).

Let \(\ms A\) denote the \(\sigma\)-algebra associated with the wheel \((S, \lfrta)\) of order \(k \in \{3, 4, \ldots\}\).

If \(k = 4\) then \(\ms A = \{\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)\).

Details:

Note 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.