We extend the definition of a general graph to that of a weighted graph by defining a weight function over its edges.

with the condition that

We also add an arbitray orientation for undirected edges.

In a graph G, let \(d_v\) denote the degree (number of incident edges) of vertex \(v\).

For \(k \in \mathbb {N}\), a graph is said to be \(k\)-regular if every vertex \(v\) has degree \(d_v = k\).

The volume of a graph is defined as the sum of the degrees of its vertices.

A vertex v is said to be isolated if \(d_v = 0\).

A graph is said to be nontrivial if it contains at least one edge.

The adjacency matrix of a graph \(G\), denoted \(A\) is defined as follows,

Consider the matrix L, defined as follows

Consider the matrix \(\mathcal{L}\), defined as follows

Let \(T\) denote the diagonal matrix with the \((u,v)\)-th entry having value \(d_v\).

We also define \(T^{-1/2}\) with the convention that \(T^{-1/2} = 0\) when \(d_v = 0\).

The Laplacian of a graph can be viewed as an operator on the space of functions \(g : V(G) \rightarrow \mathbb {R}\).

The Laplacian Operator satisfies

Let \(S\) denote the matrix whose rows are indexed by the vertices and whose columns are indexed by the edges of G. Each column corresponding to an edge \(e = \{ u, v\} \) has an entry \(1/\sqrt{d_u}\) in the row corresponding to \(u\), an entry \(−1/\sqrt{d_v}\) in the row corresponding to \(v\), and has zero entries elsewhere.

Following 19, the eigenvalues of \(\mathcal{L}\) are all real and non-negative.

The Dirichlet sum of a graph \(G\) for a function \(f : \alpha \to \mathbb {R}\) is defined as

Let \(\tau \) denote the constant function which assigns the value \(1\) on each vertex.