A dart \(d\) in a graph \(G\) is an oriented edge, meaning it has a start point \(\mathrm{start}(d)\), and endpoint \(\mathrm{end}(d)\), is carried by an edge \(\mathrm{edge}(d)\), and, in the case where \(e\) is a loop, it has an additional information encoded in a boolean \(\in \{ 0, 1\} \) encoding an orientation.

We denote as \(D(G)\) the set of darts on \(G\).

To each dart \(d\) we associate a reverse dart \(\mathrm{rev}(d)\) such that:

• \(\mathrm{start}(\mathrm{rev}(d)) = \mathrm{end}(d)\);

• \(\mathrm{end}(\mathrm{rev}(d)) = \mathrm{start}(d)\);

• \(\mathrm{edge}(\mathrm{rev}(d)) = \mathrm{edge}(d)\);

• if \(\mathrm{edge}(d)\) is a loop then the orientation of \(\mathrm{rev}(d)\) is the negation of the orientation of \(d\).

Let \(x \in V(G)\). The dartset of \(x\) is the set

Let \(x\), \(y \in V(G)\). We define the dartset of \((x,y)\) as

Let \(V\) be a set. A dart-like structure on \(V\) is the data of a set of darts \(D\), together with maps \(\mathrm{start}, \mathrm{end}: D \rightarrow V\) and \(\mathrm{rev}: D \rightarrow D\) satisfying the following:

• \(\mathrm{start}\circ \mathrm{rev}= \mathrm{end}\) and \(\mathrm{end}\circ \mathrm{rev}= \mathrm{start}\);

• \(\mathrm{rev}\) is an involution with no fixed point.

Let \(V\) be a set and \(D\), \(\mathrm{start}, \mathrm{end}, \mathrm{rev}\) be a dart-like structure. We define a relation on \(D\) by:

Let \(V\) be a set and \(D\), \(\mathrm{start}, \mathrm{end}, \mathrm{rev}\) be a dart-like structure. We define a graph \(G\) associated to this structure by taking:

• \(V(G) := V\) as the vertex set;

• \(E(G) := D(G) \diagup \sim \) as the edge set;

• for \(e \in E(G)\), if \(d \in D(G)\) is a representant of \(e\), then \(e\) links \(\mathrm{start}(d)\) and \(\mathrm{end}(d)\).

A subgraph \(H\) of \(G\) is a graph (of the same type as \(G\)) defined by:

• a vertex set \(V(H)\) included in the vextex set of \(G\)

• an edge set \(E(H)\) included in the edge set of \(H\)

• the same \(\mathrm{IsLink}\) relation, i.e. if \(e\) links \(x\) and \(y\) in \(H\) then it also links \(x\) and \(y\) in \(G\).

We define the union \(H_1 \cup H_2\) of two subgraphs by taking the union of their respective vertex sets and edge sets, and the intersection \(H_1 \cap H_2\) by taking their intersection.

A subgraph \(H\) of \(G\) is induced if, for any \(x, y \in V(H)\), for any \(e \in E(G)\), if \(e\) links \(x\) and \(y\) in \(G\), then \(e \in E(H)\).

Let \(U\) be a subset of \(V(G)\). Then we define a subgraph \(H\) induced by \(U\) by letting:

• \(V(H) := U\);

• \(E(H) := \{ e \in E(G) : \text{ both endpoints of }e \text{ lie in } U\} \).

A graph \(G\) is finite if \(V(G)\) and \(E(G)\) are both finite sets.

Let \(x \in V(G)\). We say \(G\) is locally finite at \(x\) if \(\mathrm{dartSet}(x)\) is finite. The graph \(G\) is locally finite if it is locally finite at every vertex.

Let \(x\) be a vertex of \(G\). The edegree of \(x\) is defined as \(\mathrm{edeg}(x) = \# \mathrm{dartSet}(x)\), which is an element of \(\mathbb {N} \cup \{ \infty \} \). The degree of \(x\) is the natural-number projection of the edegree.

Let \(\delta \) be a non-negative integer. We say \(G\) is regular of degree \(\delta \) if it is not empty, locally finite and, for every \(x \in V(G)\), \(\deg (x) = \delta \).

We say \(G\) is locally bounded if it is locally finite and there exists a constant \(D\) such that, for all \(x \in V(G)\), \(\deg (x) \leq D\).

The graph \(G\) is bipartite if there exists a partition \(U_1\), \(U_2\) of \(V(G)\) such that, for all \(e \in E(G)\), \(e\) links an element of \(U_1\) and an element of \(U_2\).

Let \(x, y \in V(G)\). A dartwalk from \(x\) to \(y\) on \(G\) is given by a finite list \((d_1, \ldots , d_m)\) of darts, satisfying the following:

• \(\mathrm{start}(d_1)=x\) and \(\mathrm{end}(d_m)=y\);

• for any \(i \in \{ 1, \ldots , m-1\} \), \(\mathrm{end}(d_{i+1}) = \mathrm{start}(d_i)\).

The length of a walk is its number of darts.

The support of the dartwalk \((d_i)_{1 \leq i \leq m}\) is the list \((x_i)_{0 \leq i \leq m}\) with \(x_0=\mathrm{start}(d_1)\) and \(x_i = \mathrm{end}(d_i)\) for \(1 \leq i \leq m\).

Let \(w = (d_i)_{1 \leq i \leq m}\) be a dartwalk from \(x\) to \(y\) and \(w' = (d_i')_{1 \leq i \leq m'}\) be a dartwalk from \(y\) to \(z\). We define the concatenation \(w \cdot w'\) to be the dartwalk \((d_i'')_{1 \leq i \leq m+m'}\) where \(d_i''=d_i\) for \(i \leq m\) and \(d_{i-m}'\) for \(i {\gt} m\).

We define a binary relation on \(V(G)\) by: \(x \sim y\) if there exists a dartwalk from \(x\) to \(y\) on \(G\). We then say \(x\) and \(y\) are reachable.

A dartwalk \((d_i)_{1 \leq i \leq m}\) is called a path if for all \(1 \leq i,j \leq m\), \(\mathrm{start}(d_i) = \mathrm{start}(d_j) \Rightarrow i=j\).

The graph \(G\) is a tree if, for all \(x\), \(y \in V(G)\), there exists a unique path from \(x\) to \(y\).

A graph is preconnected if any pair of vertices is reachable.

The graph \(G\) is connected if it is preconnected and \(V(G)\) is not empty.

A connected component of \(G\) is an equivalence class of \(V(G)\) for the relation reachable.

For any vertex \(x\), we define \(\mathrm{cc}(x)\) to be the unique connected component of \(G\) containing \(x\).

We denote as \(\mathrm{ConnComp}(G)\) the set of connected components of \(G\).

A function \(f : G_1 \rightarrow G_2\) is a pair of functions \(f_V : V(G_1) \rightarrow V(G_2)\) and \(f_E : E(G_1) \rightarrow E(G_2)\). We will denote \(f_V(x)=f(x)\) for \(x \in V(G_1)\) and \(f_E(e)=f(e)\) for \(e \in E(G_1)\), i.e. view \(f\) as a function from \(V(G_1) \cup E(G_1)\) to \(V(G_2) \cup E(G_2)\) sending vertices on vertices and edges on edges.

A morphism \(f : G_1 \rightarrow G_2\) is a function \(f : G_1 \rightarrow G_2\) such that for all \(x, y \in V(G_1)\), \(e \in E(G_1)\), if \(e\) links \(x\) and \(y\) in \(G_1\), then \(f(e)\) links \(f(x)\) and \(f(y)\) in \(G_2\).

A morphism \(f : G_1 \rightarrow G_2\) is an isomorphism if there exist a morphism \(g : G_2 \rightarrow G_1\) which is the inverse of \(f\). In this case we denote \(f^{-1}\) this inverse.

A morphism \(f : G_1 \rightarrow G_2\) is a local isomorphism if for all \(x \in V(G_1)\), the restriction of \(f\) to \(\mathrm{incidenceSet}(x)\) is a bijection onto \(\mathrm{incidenceSet}(f(x))\).

A morphism \(f : G_1 \rightarrow G_2\) is a covering map if it is surjective and a local isomorphism.

A graph \(G_2\) is a covering graph of a graph \(G_1\) if there exists a covering map \(\pi : G_2 \rightarrow G_1\).

A rooted graph is a graph \(G\) with a distinguished vertex \(r\), its root.

Let \((G,r)\) be a rooted graph. Let \(x \in V(G)\). A vertex \(y \in V(G)\) is a parent of \(x\) if \(y\) is adjacent to \(x\) and \(\mathrm{dist}(r,y) = \mathrm{dist}(r,x)-1\).

Let \((G,r)\) be a rooted graph. A child of \(x \in V(G)\) is an adjacent vertice which is not a parent.

A rooted tree is a rooted graph \((G,r)\) which is a tree.

A dartwalk \((d_i)_{1 \leq i \leq m}\) is called non-backtracking if for all \(1 \leq i {\lt} m\), \(d_{i+1} \neq \mathrm{rev}(d_{i})\).

Let \(w = (d_i)_{1 \leq i \leq m}\) be a dartwalk. We say \(w\) admits a reduction if there exists \(1 \leq j {\lt} m\) such that \(d_{j+1} = \mathrm{rev}(d_j)\). In this case, we call the dartwalk \(w'=(d_i')_{1 \leq i \leq m-2}\) obtained by letting \(d_i'=d_i\) for \(i{\lt}j\) and \(d_i'=d_{i+2}\) for \(i \geq j\) a reduction of \(w\).

Let \(x, y \in V(G)\). Two dartwalks \(w = (d_i)_{1 \leq i \leq m}\) and \(w' = (d_i')_{1 \leq i \leq m'}\) from \(x\) to \(y\) are said to be homotopic if there exists a finite sequence \((w_j)_{1 \leq j \leq n}\) such that:

• for all \(1 \leq j \leq n\), \(w_j\) is a dartwalk from \(x\) to \(y\);

• \(w_1=w\) and \(w_n=w'\);

• for any \(1 \leq j {\lt} n\), either \(w_j\) is a reduction of \(w_{j+1}\) or \(w_{j+1}\) is a reduction of \(w_j\).

We define the universal cover \(\hat{G}\) of \((G,r)\), which is a rooted graph, by letting:

• \(V(\hat G)\) be the set of non-backtracking dartwalks on \(G\) starting at \(r\);

• the dartset \(D(\hat{G})\) is defined as the set of pairs \((w,d)\) where \(w\) is a non-backtracking dartwalk (\(w \in V(\hat{G})\)) and \(d \in D(G)\) is a dart on \(G\) starting at the endpoint of \(w\);

• for \((w,d) \in D(\hat{G})\), \(\mathrm{start}_{\hat{G}}(w,d) = w\), \(\mathrm{end}_{\hat{G}}(d) = (w \cdot d)_{\mathrm{nb}}\) and \(\mathrm{rev}_{\hat{G}}(w,d) = ((w \cdot d)_{\mathrm{nb}},\mathrm{rev}_G(d))\);

• the root \(\hat{r}\) is the empty walk from \(r\) to \(r\).

Let \(x, y \in V(G)\). The extended distance \(\mathrm{edist}(x,y)\) between \(x\) and \(y\) is the length of the shortest dartwalk from \(x\) to \(y\) (with value in \(\mathbb {N}\cup \{ \infty \} \)).

The distance between \(x\) and \(y\) is \(\mathrm{dist}(x,y) = \mathrm{edist}(x,y).\mathrm{toNat}\).

Let \(x \in V(G)\) and \(r \in \mathbb {N}\). We define the ball \(B_r(x)\) of radius \(r\) centered at \(x\) as the set of vertices \(y \in V(G)\) such that \(\mathrm{edist}(x,y)\leq r\).

The extended diameter of a graph \(G\) is \(\mathrm{ediam}(G) := \sup _{x,y \in V(G)} \mathrm{edist}(x,y)\).

The diameter of \(G\) is \(\mathrm{diam}(G) = \mathrm{ediam}(G).\mathrm{toNat}\).

A function \(V(G) \rightarrow \mathbb {C}\) is constant if, for all \(x, y \in V(G)\), \(f(x)=f(y)\).

The constant function equal to \(1\) is defined by

Let \(U\) be a subset of \(V(G)\). We define the indicator function \(\mathbf{1}_U : V(G) \rightarrow \mathbb {C}\) by

A function \(f : V(G) \rightarrow \mathbb {C}\) is said to be locally constant if, for all \(x,y \in V(G)\), if \(x\) is adjacent to \(y\), then \(f(x)=f(y)\).

We define the adjacency operator \(a\) as the linear operator acting on the space of functions \(f : V(G) \rightarrow \mathbb {C}\) by

Let \(V\) be a set. An operator \(a : V^{\mathbb {C}} \rightarrow V^{\mathbb {C}}\) is adjacency-like if it satisfies the following properties:

• for all \(x \in V\), \(a \mathbf{1}_{\{ x\} } \in \ell ^2(G)\);

• for all \(x, y \in V\), \(a_{x,y} := \langle a \mathbf{1}_{\{ x\} }, \mathbf{1}_{\{ y\} } \rangle \) is a non-negative integer;

• for all \(x, y \in V\), \(a_{x,y}=a_{y,x}\);

• for all \(x \in V\), \(a_{x,x}\) is even.

Let \(V\) be a set and \(a\) be an adjacency-like operator on \(V\). We define a dart-like structure on \(V\) by taking:

• \(D\) is the set of \((x,y,i)\) where \(x \in V\), \(y \in V\), and \(i\) is an integer such that

  • if \(x \neq y\) then \(1 \leq i \leq a_{x,y}\);

  • if \(x=y\) then \(1 \leq |i| \leq a_{x,x}\).

• for any \((x,y,i) \in D\), we let \(\mathrm{start}(x,y,i)=x\), \(\mathrm{end}(x,y,i)=y\) and

  \begin{equation*} \mathrm{rev}(x,y,i) := \begin{cases} \mathrm{rev}(y,x,i) & \text{if } x \neq y \\ \mathrm{rev}(x,y,-i) & \text{if } x = y. \end{cases}\end{equation*}

Let \(a\) be a adjacency-like operator on \(V\). We define the graph associated to \(a\) by taking the graph associated to the dartlike structure associated to \(a\).