Izvestiya: Mathematics
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Guidelines for authors Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

 Izvestiya: Mathematics, 2024, Volume 88, Issue 3, Pages 542–589DOI: https://doi.org/10.4213/im9408e (Mi im9408)

On adjacency operators of locally finite graphs

V. I. Trofimovabc

a N.N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
c Ural Mathematical Center

### § 1. Introduction

In what follows, by a graph we will mean an undirected graph without loops and without multiple edges. Given a graph $\Gamma$, by $V(\Gamma)$ and $E(\Gamma)$ we denote its vertex set and edge set, respectively. For $x \in V(\Gamma)$, by $\Gamma(x)$ we denote the set of all its adjacent vertices in the graph $\Gamma$ (so, $|\Gamma(x)|$ is the degree of the vertex $x$). A graph $\Gamma$ is called locally finite if the degree of each vertex of $\Gamma$ is finite.

Let $\Gamma$ be a locally finite graph, $F$ be a field, and $F^{V(\Gamma)}$ be the vector space over $F$ consisting of all functions $V(\Gamma) \to F$ (with natural componentwise operations of addition and multiplication by scalar). Let the linear mapping $A^{({\mathrm{alg}})}_{\Gamma,F}: F^{V(\Gamma)} \to F^{V(\Gamma)}$, be defined, for all $f \in F^{V(\Gamma)}$ and $v \in V(\Gamma)$, by

$$\begin{equation*} \bigl(A^{(\mathrm{alg})}_{\Gamma,F}(f)\bigr)(v) := \sum_{u \in \Gamma(v)}f(u). \end{equation*} \notag$$
The primary purpose of the present paper is to study the eigenvalues and eigenvectors (that is, eigenfunctions from $F^{V(\Gamma)}$) of the linear mapping $A^{({\mathrm{alg}})}_{\Gamma,F}$.

Even though the eigenvalues and eigenvectors of the so-defined linear mapping $A^{({\mathrm{alg}})}_{\Gamma,F}$ are independent of the topologies on $F$ and $F^{V(\Gamma)}$, it will be convenient for us to assume without loss of generality that the field $F$ is equipped with some (possibly trivial) absolute value $|\,{\cdot}\,|_\mathrm{v}$, which makes $F$ a metric space (see, for example, Ch. XII, § 1 in [1]); we also assume that $F^{V(\Gamma)}$ is equipped with the corresponding product topology, which makes $F^{V(\Gamma)}$ a topological vector space. As a result, the linear mapping $A^{({\mathrm{alg}})}_{\Gamma,F}$ becomes a continuous linear operator on the topological vector space $F^{V(\Gamma)}$, which will be denoted by $A_{\Gamma,F}$ and called the adjacency operator of the graph $\Gamma$ over the field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$.

In the case of a finite graph $\Gamma$, the mapping $A^{({\mathrm{alg}})}_{\Gamma,F}$ is the well-known operator generated by the adjacency matrix of the graph $\Gamma$ (over $F$), and the theory of spectra of such operators is well developed (at least, in the case $F = \mathbb{C}$); see, for example, [2] and [3]. There have been interesting attempts to construct a spectral theory of arbitrary locally finite graphs on the basis of their adjacency matrices (the countability of the vertex sets and even connectedness of the graphs are not too restrictive conditions here, because, in essence, it suffices to consider connected components of graphs). The theory from [4] and [5] seems to be the most famous in this respect. Here it is worth mentioning that our definition of the adjacency operator $A_{\Gamma,F}$ (even for an at most countable graph $\Gamma$ and $F = \mathbb{C}$ with the usual absolute value) differs substantially from that of the adjacency operator for an at most countable locally finite graph from [4] and [5], where the adjacency operator of such a graph is called the restriction of the above operator $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$ to the Hilbert space $l_2(V(\Gamma))$ of square-summable functions, in the case of uniformly bounded degrees of vertices of $\Gamma$, while in the general case, the adjacency operator is the operator in $l_2(V(\Gamma))$, which is the closure of the restriction of $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$ to the space of finitely supported functions. It is not surprising, therefore, that we have a radically different theory for eigenvalues and eigenfunctions. (To make it clear, for an arbitrary infinite locally finite connected graph $\Gamma$, the operator $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$ or, equivalently, the operator $A_{\Gamma,\mathbb{C}}$ with an arbitrary absolute value on $\mathbb{C}$, has eigenfunctions corresponding to all, except not more than countably many, complex numbers (see Theorem 6.1), but in the case, where the degrees of the vertices of $\Gamma$ are majorized by some $d \in \mathbb{Z}_{\geqslant 1}$, the space $l_2(V(\Gamma))$ may contain only those of these functions which correspond to numbers from $\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d}$ (see Remark 6.8). To make it more transparent: For the “infinite chain” $\Gamma$ with $V(\Gamma) = \{v_i \colon i \in \mathbb{Z}\}$, $E(\Gamma) = \{ \{v_i,v_{i+1}\} \colon i \in \mathbb{Z}\}$, for each $\lambda \in \mathbb{C}$, the operator $A_{\Gamma,\mathbb{C}}$ has the eigenfunctions $f_{c_1,c_2} \in \mathbb{C}^{V(\Gamma)}$ corresponding to the eigenvalue $\lambda$. For $\lambda \notin \{-2,+2\}$, these eigenfunctions are defined by the equality $f_{c_1,c_2}(v_i) := c_1 a^i + c_2 b^i$ for all $i \in \mathbb{Z}$, where $a, b$ are the complex roots of the equation $x^2 - \lambda x + 1 = 0$, $c_1, c_2$ are arbitrary complex numbers which are not simultaneously zero, and, for $\lambda = \varepsilon 2$, $\varepsilon \in \{-1,+1\}$, they are defined by $f_{c_1,c_2}(v_i) := \varepsilon^i(c_1 + c_2 i)$ for all $i \in \mathbb{Z}$, where $c_1, c_2$ are arbitrary complex numbers which are not simultaneously zero. Nevertheless, for any $\lambda \in \mathbb{C}$ the operator $A_{\Gamma,\mathbb{C}}$ has no eigenfunctions in the space of square-summable functions $l^2(V(\Gamma))$.) By the author’s opinion, even in the case where the degrees of the vertices of a connected graph $\Gamma$ are uniformly bounded and $F = \mathbb{C}$, it frequently happens that the space of square-summable functions $l_2(V(\Gamma))$ is too narrow to include all eigenfunctions of interest of the operator $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$ (see, however, the later part of the introduction related to § 6). Qualitatively, the baseline implemented in the present paper can be characterized as finding eigenvalues and eigenfunctions of the adjacency operators $A^{({\mathrm{alg}})}_{\Gamma,F}$ in the maximally broad spaces $F^{V(\Gamma)}$ (with their possible further analysis for a membership in some or other relevant subset of the space $F^{V(\Gamma)}$). In a forthcoming research, the author of the present paper proposes to give, at least in the case where $\Gamma$ is a connected graph with uniformly bounded degrees of vertices and $F = \mathbb{C}$, an $A_{\Gamma,F}$-invariant subspace of the space $F^{V(\Gamma)}$ which is much narrower than $F^{V(\Gamma)}$ and is deprived of the above drawback of the subspace $l_2(V(\Gamma))$.

The problems considered in the present paper are related to some well-developed fields of research in mathematics — in addition to the theory of spectra of graphs (see above), we mention analysis on graphs, including results on Laplacians on locally finite graphs, theory of topological vector spaces and functional analysis, theory of infinite systems of linear equations and infinite matrices, theory of linear cellular automata, as well as theory of difference equations and theory of scalar fields on graphs. However, due to quite special properties of $F^{V(\Gamma)}$ and $A_{\Gamma,F}$ (with infinite $\Gamma$) considered in the present study, only few results from the these fields can be directly (and with sufficient generality) used when dealing with the problems under consideration. An important exclusion here is the Toeplitz theorem (see [6], and also [7], [8], Ch. 2, § 1.4), which (in one of its equivalent reformulations) asserts that a system of linear equations over a field is solvable if so is each finite subsystem of this system. In addition, the arguments from the proof of Theorem 5.2 are close to those from the proof of Theorem 3 in [9]; some well-known results are used in § 6. In all, the present paper can be considered as a piece of research in algebraic graph theory. The results obtained are partially stimulated by the results of [10] and Problem 15.89 in [11].

Let us briefly describe the contents of the paper. Of course, here it is worth pointing out that our results on connected locally finite graphs also apply to connected components of arbitrary locally finite graphs.

So, let $\Gamma$ be a locally finite graph and $F$ be a field with some (possibly trivial) absolute value $|\,{\cdot}\,|_\mathrm{v}$.

In § 2, some important auxiliary results are given. In particular, we formulate the Toeplitz theorem, derive some corollaries of this theorem, and show that, for each $\lambda \in F$, the operator $A_{\Gamma,F} - \lambda E$ (where $E$ is the identity operator on $F^{V(\Gamma)}$) maps closed subspaces of the topological vector space $F^{V(\Gamma)}$ to closed subspaces (see Corollary 2.1).

In § 3, we establish several general properties of eigenfunctions of the operator $A_{\Gamma,F}$. In particular, we show (see Propositions 3.3, 3.4 and Remark 3.3) that, for given $\lambda \in F$, and $v \in V(\Gamma)$, the support of an eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ which contains $v$, contains an inclusion-minimal support of an eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ which contains $v$, and this eigenfunction can be chosen to assume values only from $F_0(\lambda)$, where $F_0$ is the prime subfield of the field $F$. Moreover, this minimal support is connected in the graph $\Gamma^2$ (where $\Gamma^2$ is the graph with $V(\Gamma^2) = V(\Gamma)$ and whose edges connect all different vertices lying at distance $\leqslant 2$ from each other in $\Gamma$).

In § 4, for $\lambda \in F$ and $v \in V(\Gamma)$, we define an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to $v$ as a function $f \in F^{V(\Gamma)}$ such that $(A_{\Gamma,F} - \lambda E)(f) = \delta_v$, where $\delta_v(u) = 0$ for all $u \in V(\Gamma) \setminus \{v\}$ and $\delta_v(v) = 1$. (An $(F,\lambda)$-propagator of $\Gamma$ relative to $v$ is effectively a Green function (or a fundamental solution) with respect to $v$ of the operator $A_{\Gamma,F} - \lambda E$.) In what follows, $(F,\lambda)$-propagators play a key role. In § 4, general properties of $(F,\lambda)$-propagators are established. It is shown, in particular (see Theorems 4.1 and 4.2) that the graph $\Gamma$ has no $(F,\lambda)$-propagator relative to a vertex $v$ if and only if $v$ lies in the support of some finitely supported eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$; in addition, the graph $\Gamma$ has a finitely supported $(F,\lambda)$-propagator relative to $v$ if and only if there is no eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ and whose support contains $v$. As a corollary of the first result (see Corollary 4.2), we get that a graph $\Gamma$ may fail to have an $(F,\lambda)$-propagator relative to a vertex $v$ only for quite special $\lambda$’s (which, in particular, should be eigenvalues of the adjacency matrix over $F$ associated with a finite subgraph of the graph $\Gamma$; as a corollary, such $\lambda$’s are algebraic over the prime subfield of the field $F$, and real in the case $F = \mathbb{C}$).

In § 5, a number of important properties (including some spectral ones) of the operator $A_{\Gamma,F}$ are shown as being equivalent to certain properties of the propagators of the graph $\Gamma$. These results will be used in what follows. We show, in particular (see Theorem 5.3) that an element $\lambda \in F$ is not an eigenvalue of the operator $A_{\Gamma,F}$ (in other words, $A_{\Gamma,F} - \lambda E$ is injective) if and only if the graph $\Gamma$ has a finitely supported $(F,\lambda)$-propagator relative to each vertex $v$. Note that the surjectivity of $A_{\Gamma,F} - \lambda E$ is equivalent to the existence of an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to each vertex $v$ (see Theorem 5.1). We also show (see Theorem 5.2) that the existence of an infinitely supported $(F,\lambda)$-propagator of the graph $\Gamma$ relative to some vertex implies that $A_{\Gamma,F}$ has an infinitely supported eigenfunction corresponding to the eigenvalue $\lambda$.

In the present paper, propagators play an important role because, first, in terms of propagators one can express and study important properties of the adjacency operator of the graph (see § 4 and § 5), and, second, they (unlike the eigenfunctions of the adjacency operators) can be constructively realized using certain sums over paths of the graph, and (in the case of a connected graph with uniformly bounded degrees of vertices and $F = \mathbb{C}$) the restriction of $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$ to the space of square-summable functions. These constructive realizations of propagators are considered in § 6. The advantage of using certain sums over paths of the graph for construction of propagators in combination with pervious results of the present paper is that (see Theorem 6.1), in the case of an infinite locally finite connected graph $\Gamma$ and a field $F$ of characteristic 0, each element $\lambda \in F$ which is transcendental over the prime subfield of the field $F$ is an eigenvalue of the operator $A_{\Gamma,F}$. In addition, in the case, where the degrees of vertices of an infinite connected graph $\Gamma$ are majorized by some $d \in \mathbb{Z}_{\geqslant 1}$ and $F = \mathbb{C}$, by using the restriction of $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$ to the space of square-summable functions it makes possible (see assertion 2) of Theorem 6.2), for each vertex $v$ of the graph $\Gamma$ and each $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, to find a square-summable $(\mathbb{C},\lambda)$-propagator of the graph $\Gamma$ relative to the vertex $v$, and this propagator is uniquely defined by this property. As a corollary of this uniqueness, for each $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, any eigenfunction of the operator $A_{\Gamma, \mathbb{C}}$ corresponding to $\lambda$ is not a square-summable function (even though by Theorem 6.1 there exist eigenfunctions of $A_{\Gamma, \mathbb{C}}$ corresponding to $\lambda$, at least for all complex $\lambda$ which are transcendental over $\mathbb{Q}$). In this regard, it is worth pointing out that (in the case of an infinite connected graph $\Gamma$ with degrees of vertices majorized by $d$), for all $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, the space of square-summable functions can be used, in a remarkable way, for realizations of $(\mathbb{C},\lambda)$-propagators, but, at the same time, this space is too narrow for realizations of the eigenfunctions of the operator $A_{\Gamma, \mathbb{C}}$ corresponding to these $\lambda$’s (nevertheless, such eigenfunctions can be studied with the help of the above square-summable propagators and already obtained results of the paper).

In § 7, as a corollary of the previously obtained results of the paper, we show that, for a locally finite graph $\Gamma$ and $\lambda \in F$, the situation where there exist $(F,\lambda)$-propagators relative to all vertices of the graph (in other words, the situation where $A_{\Gamma,F} - \lambda E$ is surjective) is “generic” in a sense. On the other hand, in the case of an infinite locally finite connected graph $\Gamma$ and of a field $F$ of characteristic $0$, it is shown that, for $\lambda \in F$, the situation where $\lambda$ is not an eigenvalue of $A_{\Gamma,F}$ (in other words, see above, the situation where $\Gamma$ has a finitely supported $(F,\lambda)$-propagator relative to each vertex of the graph) is “exceptional” in a sense. In addition, we show (see Propositions 7.3 and 7.2) that, for an infinite locally finite connected graph $\Gamma$ and for a field $F$ of characteristic $0$, the situation where $\Gamma$ has a finitely supported $(F,\lambda)$-propagator relative to at least one vertex is “exceptional” in a sense for $\lambda \in F$.

In § 8, we give examples of infinite locally finite connected graphs $\Gamma$ and fields $F$ in which the operators $A_{\Gamma,F}$ feature certain interesting properties for our study.

Our notation for the graphs is mostly standard. For a graph $\Gamma$, by $d_{\Gamma}(.,.)$ we denote the usual distance between vertices (which is $\infty$ for vertices from different connected components of the graph); for $u \in V(\Gamma)$ and $r \in \mathbb{R}_{\geqslant 0}$, by $B_{\Gamma}(u,r)$ we denote the set of vertices of the graph $\Gamma$ which lie at distance $\leqslant r$ from $u$. If $\Gamma$ is a graph and $\varnothing \neq X \subseteq V(\Gamma)$, then $\langle X \rangle_{\Gamma}$ is the subgraph of the graph $\Gamma$ generated by $X$. $\operatorname{Aut(}\Gamma)$ is the group of automorphisms of the graph $\Gamma$ (considered as a permutation group on $V(\Gamma)$).

For a field $F$ and non-empty sets $X$, $Y$, by $M_{X\times Y}(F)$ we denote the vector space over $F$ of all matrices with elements from $F$ whose rows are indexed by the elements of the set $X$, and the columns, by the elements of the set $Y$. By $M^{\mathrm{rf}}_{X\times Y}(F)$ we denote the subset (vector subspace) of $M_{X\times Y}(F)$ consisting of all matrices from $M_{X\times Y}(F)$ for which each row has only a finite number of non-zero elements; by $M^{\mathrm{cf}}_{X\times Y}(F)$ we denote the subset (vector subspace) of $M_{X\times Y}(F)$ consisting of all matrices from $M_{X\times Y}(F)$ for which each column contains only a finite number of non-zero elements; $M^{\mathrm{rcf}}_{X\times Y}(F) := M^{\mathrm{rf}}_{X\times Y}(F) \cap M^{\mathrm{cf}}_{X\times Y}(F)$. If $F$ is a field and $X$, $Y$, $Z$ are non-empty sets, then, for each matrix from $M_{Y\times Z}(F)$, the (natural) left multiplication by any matrix from $M^{\mathrm{rf}}_{X\times Y}(F)$ is defined, and, for each matrix from $M_{X\times Y}(F)$, the (natural) right multiplication by any matrix from $M^{\mathrm{cf}}_{Y\times Z}(F)$ is defined. It is also plain that, for a field $F$ and a non-empty set $X$, the vector subspaces $M^{\mathrm{rf}}_{X\times X}(F)$, $M^{\mathrm{cf}}_{X\times X}(F)$ and $M^{\mathrm{rcf}}_{X\times X}(F)$ of the vector space $M_{X\times X}(F)$ are (relative to the natural operations) associative $F$-algebras. For a field $F$, non-empty sets $X$, $Y$, and an arbitrary matrix $\mathbf{M}\in M_{X\times Y}(F)$, by $\mathbf{M}^\top$ we denote the transposition of $\mathbf{M}$ from $M_{Y\times X}(F)$ (which is defined in the standard way).

For a graph $\Gamma$ and a field $F$, by $\mathbf{A}_{\Gamma,F}$ we denote the matrix from $M_{V(\Gamma)\times V(\Gamma)}(F)$ such that, for arbitrary $u,v \in V(\Gamma)$, the element for the row corresponding to $u$ and the column corresponding to $v$ is $1$ for $\{u,v\} \in E(\Gamma)$ and is $0$ for $\{u,v\} \notin E(\Gamma)$. It is clear that $\mathbf{A}_{\Gamma,F}^\top = \mathbf{A}_{\Gamma,F}$. It is also clear that $\Gamma$ is locally finite if and only if $\mathbf{A}_{\Gamma,F} \in M^{\mathrm{rcf}}_{V(\Gamma)\times V(\Gamma)}(F)$.

If $\Gamma$ is a locally finite graph and $F$ is a field, then the vector space (over $F$) of the functions from $F^{V(\Gamma)}$ can be naturally identified with the vector space (over $F$) of the column matrices $M_{V(\Gamma)\times \{1\}}(F)$ by associating with each function $f \in F^{V(\Gamma)}$ the column $\mathbf{f} \in M_{V(\Gamma)\times \{1\}}(F)$ such that the element for the row corresponding to the vertex $u$ is $f(u)$ for all $u \in V(\Gamma)$. It is clear that, under this association, for all $\lambda \in F$ and $f \in F^{V(\Gamma)}$, the column $(\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E})(\mathbf{f}) \in M_{V(\Gamma)\times \{1\}}(F)$ is associated with the function $(A^{({\mathrm{alg}})}_{\Gamma,F} - \lambda E)(f) \in F^{V(\Gamma)}$ (where $\mathbf{E}$ is the identity matrix from $M_{V(\Gamma)\times V(\Gamma)}(F)$).

### § 2. Terminology and auxiliary results

In this section, which contains auxiliary results, it is assumed that $\Gamma$ is a locally finite graph, and $F$ is a field with (possibly trivial) absolute value $|\,{\cdot}\,|_\mathrm{v}$. It is also assumed (see Introduction) that the field $F$ is equipped with the topology (metric) defined by $|\,{\cdot}\,|_\mathrm{v}$, and the vector space $F^X$, for an arbitrary $\varnothing \neq X \subseteq V(\Gamma)$, is equipped with the corresponding produce topology. In the case of a connected (and, more generally, at most countable) graph $\Gamma$, it is well known that this product topology on $F^{V(\Gamma)}$ can be induced by the metric $\rho$ defined as follows: we arbitrary enumerate all vertices of the graph $\Gamma$, which gives $V(\Gamma) = \{v_n \mid n \in \mathcal N \}$, where $\mathcal N = \{ 1,\dotsc,|V(\Gamma)|\}$ if $\Gamma$ is finite, and $\mathcal N = \mathbb{Z}_{\geqslant 1}$ otherwise, after which, for arbitrary $f_1, f_2 \in F^{V(\Gamma)}$, we set

$$\begin{equation*} \rho(f_1,f_2)=\sum_{n \in \mathcal N} \biggl( \frac{1}{2^n}\, \frac{|f_1(v_n) - f_2(v_n)|_{\mathrm{v}}}{1+|f_1(v_n) - f_2(v_n)|_{\mathrm{v}}}\biggr). \end{equation*} \notag$$

It is worth pointing out that, in many results that follow, the above topology on $F$ (and on $F^{V(\Gamma)}$) plays only an auxiliary role. In this regard, we recall that both the property of an element $\lambda \in F$ to be an eigenvalue of the operator $A_{\Gamma,F}$, and the property of a function $f \in F^{V(\Gamma)}$ to be an eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda \in F$, are independent of the choice of the absolute value $|\,{\cdot}\,|_\mathrm{v}$. (However, singling out an absolute value $|\,{\cdot}\,|_\mathrm{v}$ on the field $F$ may prove useful, for example, for finding an eigenfunction of $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ or an $(F,\lambda)$-propagator, because in this case topological arguments may be invoked (see Remark 3.1 and § 6 in this regard).)

Below, unless otherwise stated, a subfield of the field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$ is assumed to be endowed with the absolute value, which is the restriction onto this subfield of the absolute value $|\,{\cdot}\,|_\mathrm{v}$. We also assume, unless otherwise stipulated, that the vector subspace of the vector space $F^{V(\Gamma)}$ is endowed with the induced topology.

Vector subspaces of the topological vector space $F^{V(\Gamma)}$ are not assumed to be closed. By $\operatorname{Cl}$ we denote the closure operation in $F^{V(\Gamma)}$. For an arbitrary $\lambda \in F$, it is clear that $A_{\Gamma,F} - \lambda E$ is an (everywhere defined) continuous linear operator from $F^{V(\Gamma)}$ into $F^{V(\Gamma)}$. If $X \subseteq V(\Gamma)$, then, for $f \in F^{V(\Gamma)}$ and $\mathcal F \subseteq F^{V(\Gamma)}$, by $f|_X$ and $\mathcal F |_X$ we denote, respectively, the restrictions of $f$ and $\mathcal F$ to $X$ (that is, the images of $f$ and $\mathcal F$ under the natural projection $F^{V(\Gamma)} \to F^X$). For an arbitrary $\varnothing \neq X \subseteq V(\Gamma)$, we set $\Gamma(X) := \bigcup_{u \in X}\Gamma(u)$, and by $(A_{\Gamma,F} - \lambda E)_X$ for $\lambda \in F$ we denote the linear operator from $F^{X \cup \Gamma(X)}$ into $F^X$ which maps a function $f \in F^{X \cup \Gamma(X)}$ to the function from $F^X$ whose value at an arbitrary vertex $u \in X$ is $(\sum_{u' \in \Gamma(u)}f(u')) - \lambda f(u)$.

By $F^{V(\Gamma)*}$ we denote the subspace of the vector space $F^{V(\Gamma)}$ consisting of all functions with finite supports. For $v \in V(\Gamma)$, by $\delta_v$ we denote (as already mentioned in Introduction) the function from $F^{V(\Gamma)}$ such that $\delta_v(u) = 0$ for all $u \in V(\Gamma) \setminus \{v\}$ and $\delta_v(v) = 1$. In addition, for $v \in V(\Gamma)$, we set

$$\begin{equation*} \alpha_v := \sum_{v' \in \Gamma(v)} \delta_{v'} - \lambda \delta_v. \end{equation*} \notag$$
So, $\alpha_v = (A_{\Gamma,F} - \lambda E)(\delta_v)$ for all $v \in V(\Gamma)$, and $(A_{\Gamma,F} - \lambda E)(F^{V(\Gamma)*})$ coincides with the linear hull in $F^{V(\Gamma)}$ of the set $\{\alpha_v \colon v \in V(\Gamma)\}$.

Below, it will sometimes be convenient to work with the terminology used for (systems) of linear equations. As usual, for a field $F$, a linear equation over $F$ with unknowns $x_j$, $j \in J \neq \varnothing,$ is an equation

$$\begin{equation*} \sum_{j \in J} c_j x_j=a, \end{equation*} \notag$$
where $a \in F$ and $c_j \in F$ for each $j \in J$, and the set $\{j \in J \colon c_{j} \neq 0\}$ is finite. Solutions in $F$ of this equation are understood in the standard way. We also use the standard terminology when dealing with systems (not necessarily finite) of linear equations over $F$, with their solutions in $F$, and also with their solvability in $F$ (the existence of a solution in $F$).

In what follows, an important role will be played by the following Toeplitz theorem (see [6], and also [8], Ch. 2, § 1.4).

Proposition 2.1. Let $F$ be a field, $I$ and $J$ be sets (not necessarily finite), where $J \neq \varnothing$. For arbitrary $i \in I$ and $j \in J$, let $c_{i,j} \in F$, and let, for each $i \in I$, the set $\{j \in J \colon c_{i,j} \neq 0\}$ be finite. Assume also that $a_i \in F$ for each $i \in I$. Then the system of linear equations

$$\begin{equation*} \sum_{j \in J} c_{i,j} x_j=a_i,\qquad i \in I, \end{equation*} \notag$$
with unknowns $x_j$, $j \in J$, is solvable over $F$ if and only if, for an arbitrary finite subset $I'$ of $I$ and arbitrary $b_{i'} \in F$, $i' \in I'$, the condition
$$\begin{equation*} \sum_{i' \in I'}b_{i'}c_{i',j} = 0 \ \ \textit{for each}\ j \in J \end{equation*} \notag$$
implies that
$$\begin{equation*} \sum_{i' \in I'}b_{i'}a_{i'}=0. \end{equation*} \notag$$

The Toeplitz theorem will be frequently useful in the following form (see [8], Ch. 2, § 1.4, and also [7]; here, we use, in addition, that a finite system of linear equations over a field is solvable if it is solvable over some extension of this field).

Proposition 2.2. A system (not necessarily finite) of linear equations over a field $F$ is solvable over $F$ if and only if each finite subsystem of this system is solvable over some extension of the field $F$.

The next result follows from the Toeplitz theorem (in the above form).

Proposition 2.3. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then, for $f \in F^{V(\Gamma)}$, the inclusion $f \in (A_{\Gamma,F} - \lambda E)(F^{V(\Gamma)})$ is equivalent to the inclusions $f|_X \in (A_{\Gamma,F} - \lambda E)_X(F^{X \cup \Gamma(X)})$ for all finite non-empty subsets $X$ of $V(\Gamma)$.

The following proposition demonstrates some useful “technical” capabilities of the Toeplitz theorem.

Proposition 2.4. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Next, let $U \subseteq V(\Gamma)$, and, for each vertex $u \in U$, let $c_u \in F$. Assume, in addition, that $U'$ is a finite subset of the set $V(\Gamma)$, $I$ is some set, and, for each $i \in I$, we are given $u_i \in U'$, $c'_{i} \in F$, $q_{i} \in \mathbb{R}_{\geqslant 0}$. Also let $\tau_{i}$ be one of the binary relations $\neq ,<,\leqslant,\geqslant,>$ on $\mathbb{R}$. Then the following conditions (i) and (ii) are equivalent.

(i) There exists $f \in F^{V(\Gamma)}$ such that $(A_{\Gamma,F} - \lambda E)(f) = 0$, $f(u) = c_u$ for each vertex $u \in U$ and $|f(u_i) - c'_{i}|_\mathrm{v} \tau_{i} q_{i}$ for each $i \in I$;

(ii) For each finite subset $X$ of the set $V(\Gamma)$, there exists $f_X \in F^{V(\Gamma)}$ such that $((A_{\Gamma,F} - \lambda E)(f_X))|_X = 0$, $f_X(u) = c_u$ for each vertex $u \in U \cap X$ and $|f_X(u_i) - c'_{i}|_\mathrm{v} \tau_{i} q_{i}$ for each $i \in I$.

Proof. Let us show that (ii) implies (i). The restriction to $U'$ of the set of functions $f \in F^{V(\Gamma)}$ such that $(A_{\Gamma,F} - \lambda E)(f) = 0$ and $f(u) = c_u$ for each vertex $u \in U$ is either empty or has the form $h + W$, where $h \in F^{U'}$, and $W$ is a subspace of the (finite-dimensional) vector space $F^{U'}$. But then the Toeplitz theorem (see Proposition 2.2) implies that this restriction coincides, for some finite subset $X$ of $V(\Gamma)$, with the restriction to $U'$ of the set of functions $f \in F^{V(\Gamma)}$ such that $(A_{\Gamma,F} - \lambda E)(f)|_X = 0$ and $f(u) = c_u$ for each vertex $u \in U \cap X$. (Indeed, for each finite subset $X'$ of $V(\Gamma)$, the restriction to $U'$ of the set of functions $f \in F^{V(\Gamma)}$ such that $(A_{\Gamma,F} - \lambda E)(f)|_{X'} = 0$ and $f(u) = c_u$, for each vertex $u \in U \cap X'$, has the form $h + W_{X'}$, where $W_{X'}$ is a subspace of the space $F^{U'}$ containing $W$. By the Toeplitz theorem, the intersection of all $W_{X'}$ over all finite subsets $X' \subseteq V(\Gamma)$ coincides with $W$, and since the vector space $F^{U'}$ is finite-dimensional, it follows that, for some finite set $X_1,\dotsc,X_k$ of finite subsets of $V(\Gamma)$, we have $W = \bigcap_{1 \leqslant j \leqslant k}W_{X_j}$. It remains to note that $W_{X_1 \cup \cdots\cup X_k} = \bigcap_{1 \leqslant j \leqslant k}W_{X_j}$, and, therefore, as $X$ one may take the set $X_1 \cup \cdots\cup X_k$.) Now (i) follows from (ii).

The implication (i) $\Rightarrow$ (ii) is trivial. Proposition 2.4 is proved.

In the concluding part of this section, we will show that, for a locally finite graph $\Gamma$, a field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$, the operator $A_{\Gamma,F} - \lambda E$ maps closed vector subspaces of the topological vector space $F^{V(\Gamma)}$ to closed subspaces (see Corollary 2.1). To this end we will require Proposition 2.5, whose proof depends on standard arguments involving projective limits and closedness of an arbitrary vector subspace of the vector space $F^X$ with the product topology, where $F$ is a field with topology defined by some absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $X$ is a finite non-empty set. (That any vector subspace in this vector space $F^X$ is closed follows from its representation as the set of all $f \in F^X$ such that $\sum_{u \in X}c_{i,u}f(u) = 0$, $i = 1,\dotsc,|X|$, for some fixed (for this subspace) elements $c_{i,u}$ of the field $F$, $1 \leqslant i \leqslant |X|$, $u \in X$.)

Proposition 2.5. Let $\Gamma$ be a locally finite connected graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Let, in addition, $(f_i)_{i \in \mathbb{Z}_{\geqslant 1}}$ be a sequence of vectors from $F^{V(\Gamma)}$ such that the sequence $((A_{\Gamma,F} - \lambda E)(f_i))_{i \in \mathbb{Z}_{\geqslant 1}}$ converges to some $f \in F^{V(\Gamma)}$. Then there exists a vector $f'$ which lies in the closure in $F^{V(\Gamma)}$ of the vector subspace generated by the set of vectors $\{f_i \colon i \in \mathbb{Z}_{\geqslant 1}\}$ and such that $(A_{\Gamma,F} - \lambda E)(f') = f$.

Proof. Let $v \in V(\Gamma)$ and $B_i := B_{\Gamma}(v,i)$ for all $i \in \mathbb{Z}_{\geqslant 0}$. Let, in addition, $W$ be the vector subspace of the space $F^{V(\Gamma)}$ generated by the set of vectors $\{f_i \colon i \in \mathbb{Z}_{\geqslant 1}\}$. By the assumption, $f \in \operatorname{Cl}((A_{\Gamma,F} - \lambda E)(W))$, and hence $f|_{B_i} \in (\mathrm{Cl}((A_{\Gamma,F} - \lambda E)(W)))|_{B_i}$ for each $i \in \mathbb{Z}_{\geqslant 0}$. Next, since $(\operatorname{Cl}((A_{\Gamma,F} - \lambda E)(W)))|_{B_i} = ((A_{\Gamma,F} - \lambda E)(W))|_{B_i}$, because the vector subspace $((A_{\Gamma,F} - \lambda E)(W))|_{B_i}$ is closed in the topological vector space $F^{B_i}$ (see the remark preceding Proposition 2.5), it follows that there exists $\widetilde f_i \in W$ such that $((A_{\Gamma,F} - \lambda E)(\widetilde f_{i}))|_{B_{i}} = f|_{B_i}$.

For each $i \in \mathbb{Z}_{\geqslant 0}$, we set $L_i := (A_{\Gamma,F} - \lambda E)_{B_i}$ and $\mathcal F _i := W|_{B_{i+1}} \cap (L_i)^{-1}(f|_{B_i})$ (where $(L_i)^{-1}(f|_{B_i})$ is the set of all functions from $F^{B_{i+1}}$ which are mapped under $L_i$ to $f|_{B_i}$). Note that $\mathcal F _i$ is a non-empty (since $\widetilde f_{i+1}|_{B_{i+1}} \in \mathcal F _i$) affine subspace of the affine space associated with the vector space $F^{B_{i+1}}$. In addition, for arbitrary non-negative integers $i_1 \leqslant i_2$, the restriction mapping $F^{B_{i_2+1}} \to F^{B_{i_1+1}}$ induces an affine mapping $\pi_{i_1,i_2}: \mathcal F _{i_2} \to \mathcal F _{i_1}$. The resulting projective system of sets $\mathcal F _i$, $i \in \mathbb{Z}_{\geqslant 0}$, and mappings $\pi_{i_1,i_2}$, $i_1,i_2 \in \mathbb{Z}_{\geqslant 0}$, $i_2 \geqslant i_1$, has a projective limit, since it has the Mittag–Leffler property: for each $i \in \mathbb{Z}_{\geqslant 0}$, the sequence $(\pi_{i,i+j}(\mathcal F _{i+j}))_{j \in \mathbb{Z}_{\geqslant 0}}$ stabilizes. Each element of this projective limit can be interpreted as a vector $f' \in F^{V(\Gamma)}$ such that, for each $i \in \mathbb{Z}_{\geqslant 1}$, there exists a vector $f'_i \in W$ such that $f'_i|_{B_i} \in \mathcal F _{i-1}$ and $f'_i|_{B_i} = f'|_{B_i}$. It is clear that the sequence $(f'_i)_{i \in \mathbb{Z}_{\geqslant 1}}$ of vectors from $W$ converges to the vector $f'$ (which hence lies in $\operatorname{Cl}(W)$) and $(A_{\Gamma,F} - \lambda E)(f') = f$.

Corollary 2.1. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. If $W$ is a subspace of the vector space $F^{V(\Gamma)}$, then

$$\begin{equation*} \operatorname{Cl}\bigl((A_{\Gamma,F} - \lambda E)(W)\bigr)=(A_{\Gamma,F} - \lambda E)(\operatorname{Cl}(W)). \end{equation*} \notag$$
In other words, $A_{\Gamma,F} - \lambda E$ maps closed subspaces of the vector space $F^{V(\Gamma)}$ to closed subspaces.

Proof. The inclusion
$$\begin{equation*} (A_{\Gamma,F} - \lambda E)(\operatorname{Cl}(W)) \subseteq \operatorname{Cl}\bigl((A_{\Gamma,F} - \lambda E)(W)\bigr)) \end{equation*} \notag$$
follows from continuity of $A_{\Gamma,F} - \lambda E$. The converse inclusion is obtained by applying Proposition 2.5 to connected components of the graph $\Gamma$.

Remark 2.1. The result of the corollary does not hold in general for a subset $W$ of the vector space $F^{V(\Gamma)}$ which is not a vector subspace.

### § 3. Some general properties of the eigenfunctions of the adjacency operators of locally finite graphs

In this section, we give a preliminary analysis of eigenfunctions of the adjacency operators of locally finite graphs. The results obtained are general but somehow technical.

Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. As already noted, the property of a function from $V(\Gamma)$ to $F$ to be an eigenfunction of the adjacency operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ is independent of the choice of $|\,{\cdot}\,|_\mathrm{v}$. In addition, from Proposition 2.2 it easily follows that the existence of an eigenfunction of the adjacency operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ is equivalent to the existence of an eigenfunction of the adjacency operator $A_{\Gamma,F'}$ corresponding to the eigenvalue $\lambda$ for some extension $F'$ of the field $F_0(\lambda)$, where $F_0$ is the prime subfield of the field $F$. We formalize these facts (which can be used, for construction of eigenfunctions, via convenient variations of fields and equipment of these fields with appropriate absolute values) in a slightly refined way in the following result.

Proposition 3.1. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, $F_0$ be the prime subfield of the field $F$, and $\lambda \in F$. Then the following assertions hold.

$1)$ If $\varphi$ is an embedding of the field $F$ into some field $F'$ with arbitrary absolute value $|\,{\cdot}\,|_{\mathrm{v}'}$ and $f$ is an eigenfunction of the adjacency operator $A_{\Gamma,F'}$ corresponding to the eigenvalue $\varphi(\lambda)$ such that $f(u) \in \varphi(F)$ for all $u \in V(\Gamma)$, then $\varphi^{-1} f$, if considered as an element of $F^{V(\Gamma)}$, is an eigenfunction of the adjacency operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$.

$2)$ If $f$ is an eigenfunction of the adjacency operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$, and $v$ is a vertex of the graph $\Gamma$ lying in the support of $f$, then there exists an eigenfunction of the adjacency operator $A_{\Gamma,F_0(\lambda)}$ corresponding to the eigenvalue $\lambda$ whose support lies in the support of $f$ and contains $v$.

Proof. Assertion $1)$ is clear. For a proof of assertion $2)$, we consider the following system of linear equations over $F$ with unknowns $x_u$, where $u \in V(\Gamma)$: by definition, the system consists, first, of the equations $(\sum_{u' \in \Gamma(u)}x_{u'}) - \lambda x_u = 0$ for all $u \in V(\Gamma)$, second, of the equations $x_u = 0$ for all vertices $u$ of the graph $\Gamma$ not lying in the support of $f$, and, third, of the equation $x_v = 1$. Note that all the coefficients of this system lie in $F_0(\lambda)$. In addition, the existence of $f$ implies that this system is consistent over $F$. By Proposition 2.2, this system is consistent also over $F_0(\lambda)$. Let $x'_u \in F_0(\lambda)$, where $u$ varies over the set $V(\Gamma)$, be some its solution over $F_0(\lambda)$ (in the sense that if $x_u$ is replaced by $x'_u$ for all $u \in V(\Gamma)$, then each equation of the system becomes an equality in $F_0(\lambda)$). It is now clear that the function from $F_0(\lambda)^{V(\Gamma)}$ assuming the value $x'_u$ at each vertex $u \in V(\Gamma)$ is a required eigenfunction of the adjacency operator $A_{\Gamma,F_0(\lambda)}$ corresponding to the eigenvalue $\lambda$ whose support lies in the support of $f$ and contains $v$.

Remark 3.1. Let us indicate some possible applications of Proposition 3.1. Under the hypotheses of Proposition 3.1, let $\Gamma$ be infinite and connected, and let the characteristic of the field $F$ be $0$ (that is, $F_0 = \mathbb{Q}$). We are interested in whether $\lambda$ is an eigenvalue of the adjacency operator $A_{\Gamma,F}$. In Theorem 6.1 it will be shown that this is so if $\lambda$ is transcendental over $\mathbb{Q}$. So, let us assume that $\lambda$ is algebraic over $\mathbb{Q}$. From Proposition 3.1 it follows that the existence of an eigenfunction of the adjacency operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ is equivalent to that for the operator $A_{\Gamma,\widetilde F}$, where as $\widetilde F$ one may take any extension of the field $\mathbb{Q}(\lambda)$. For example, as $\widetilde F$ one may consider any of the fields: $\mathbb{Q}(\lambda)$ (with arbitrary absolute value), $\mathbb{C}$ (considered as an extension of $\mathbb{Q}(\lambda)$, with arbitrary absolute value, and, in particular, with the usual absolute value on $\mathbb{C}$ (in this way, the eigenfunctions of interest can be constructed by analytic methods; see § 6)), $\Omega_l$ for a prime number $l$ ($l$-adic completion of the algebraic closure of the field of $l$-adic numbers $\mathbb{Q}_l$, which is considered as an extension of $\mathbb{Q}(\lambda)$, with arbitrary absolute value, and, in particular, with an extension of the $l$-adic absolute value $|\,{\cdot}\,|_l$ on $\mathbb{Q}$ (in this setting, analytic methods are also useful for construction of eigenfunctions)). In addition, when dealing, for example, with the case $\widetilde F = \mathbb{C}$ with the usual absolute value, there is a possibility (in view of assertion 1) of Proposition 3.1) to appropriately choose an embedding of $\mathbb{Q}(\lambda)$ into $\mathbb{C}$.

The next result follows from the Toeplitz theorem (see Proposition 2.2).

Proposition 3.2. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Let, further, $v$ be a vertex of the graph $\Gamma$ not contained in the supports of eigenfunctions of the adjacency operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$. For each $r \in \mathbb{Z}_{\geqslant 0}$, let the system $\operatorname{Syst}_r$ of linear equations over $F$ with unknowns $x_u$, where $u \in B_{\Gamma}(v,r + 1)$, consist of the equation $x_v = 1$, and, for each $u \in B_{\Gamma}(v,r)$, of the equation $(\sum_{u' \in \Gamma(u)}x_{u'}) - \lambda x_u = 0$. Then there exists $r_{\lambda,v} \in \mathbb{Z}_{\geqslant 0}$ ($$the radius of inconsistency for $\lambda$ and $v$$") such that the system \operatorname{Syst}_r is consistent (over F) if and only if r < r_{\lambda,v}. In addition, the number r_{\lambda,v} does not change if F is replaced by F_0(\lambda), where F_0 is the prime subfield of the field F. Remark 3.2. For a locally finite graph \Gamma, a field F with absolute value |\,{\cdot}\,|_\mathrm{v}, and \lambda \in F, the set of all vertices of the graph \Gamma which are not contained in any of the supports of the eigenfunctions of the adjacency operator A_{\Gamma,F} corresponding to the eigenvalue \lambda will play an important role in what follows. In § 4 (see Theorem 4.2), it will be shown that this set coincides with the set L_{F,\lambda}(\Gamma) (see § 4) of all vertices of the graph \Gamma relative to which \Gamma has (F,\lambda)-propagators with finite supports. Let us make some additional observations on the supports of eigenfunctions of the adjacency operators of locally finite graphs. Proposition 3.3. Let \Gamma be a locally finite graph, F be a field with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F, and v \in V(\Gamma). If X_i, i \in I, is a non-empty linearly ordered by inclusion family of subsets of the set V(\Gamma) which contain v and which are supports of the eigenfunctions of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda, then some subset of the set \bigcap_{i \in I}X_i is the support of an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda, and this support contains v. As a corollary (and in view of the Zorn lemma), each support of an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda which contains v also contains an inclusion-minimal support among those of the eigenfunctions of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda and which contain v. Proof. The required result follows by applying the Toeplitz theorem (see Proposition 2.2) to the system of linear equations over F with unknowns x_u, where u \in V(\Gamma), and which consists, first, of the equations (\sum_{u' \in \Gamma(u)}x_{u'}) - \lambda x_u = 0 for all u \in V(\Gamma), second, of the equations x_u = 0 for all u \in V(\Gamma) \setminus \bigcap_{i \in I}X_i, and, third, of the equation x_v = 1. If \Gamma is a locally finite graph, F is a field with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F, and f is an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda, then, for \varnothing \neq X \subseteq V(\Gamma), which is the union of a set of connected components of the support of the function f, the function from F^{V(\Gamma)}, which coincides with f on X and is identically zero on V(\Gamma) \setminus X, is not in general an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda (even though the restriction of f to X is, clearly, an eigenfunction of the operator A_{\langle X \rangle_{\Gamma},F} corresponding to the eigenvalue \lambda). However, such an effect does not appear if, in place of the connected components of the support, one considers the \Gamma^2-connected components of the support (the definition is given below). For an arbitrary graph \Gamma, we will denote by \Gamma^2 the graph with vertex set V(\Gamma^2) = V(\Gamma) and edge set consisting, precisely, of the pairs of its different vertices \{u,u'\} such that u and u' are connected in the graph \Gamma by a path of length \leqslant 2. Let X be a subset of the vertex set of the graph \Gamma. We say that X is \Gamma^2-connected if so is the subgraph \langle X \rangle_{\Gamma^2} of the graph \Gamma^2 generated by X. By definition, by \Gamma^2-connected components of X we will mean sets of vertices of connected components of the graph \langle X \rangle_{\Gamma^2}. If \Gamma is a locally finite graph, F is a field with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F, and f is an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda, then, for \varnothing \neq X \subseteq V(\Gamma), which is the union of an arbitrary set of \Gamma^2-connected components of the support of the function f, the function from F^{V(\Gamma)}, which coincides with f on X and which is identically zero on V(\Gamma) \setminus X, is, clearly, also an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda but with the support X. In particular, for the above (see Proposition 3.3) inclusion-minimal supports among those of the eigenfunctions of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda and which contain v, we have the following result. Proposition 3.4. Let \Gamma be a locally finite graph, F be a field with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F, and v \in V(\Gamma). Then each inclusion-minimal support among those of the eigenfunctions of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda and which contain v, is \Gamma^2-connected. Remark 3.3. In view of assertion 2) of Proposition 3.1, for a locally finite graph \Gamma, a field F with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F, and v \in V(\Gamma), each minimal support of an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda and containing v is not only \Gamma^2-connected (see Proposition 3.4), but is also the support of an eigenfunction from F_0(\lambda)^{V(\Gamma)} of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda, where F_0 is the prime subfield of the field F (or in other words, this is the support of an eigenfunction of the operator A_{\Gamma,F_0(\lambda)} corresponding to the eigenvalue \lambda). The next result will be required in what follows. Proposition 3.5. Let \Gamma be a locally finite graph, F be a field with absolute value |\,{\cdot}\,|_\mathrm{v}, and \lambda \in F. Assume that there exists a family X_i, i \in I, of finite subsets of the set V(\Gamma) such that \bigcup_{i \in I} X_i is infinite, and, for each i \in I, there is an eigenfunction f_i of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda with support X_i. Then, for each vertex from \bigcup_{i \in I} X_i, there exists an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda with infinite support containing this vertex and lying in \bigcup_{i \in I} X_i. Proof. For i \in I, a \Gamma^2-connected component of the set X_i is the support of the eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda, which assumes the same values as f_i on the vertices of this component, and is zero on the remaining vertices of the graph \Gamma. Hence, passing if necessary from the family of sets X_i, i \in I, to the family of all its \Gamma^2-connected components, we can assume without loss of generality that each of the sets X_i, i \in I, is \Gamma^2-connected. In addition, it can be assumed that the sets X_i, i \in I, are pairwise different. We set X := \bigcup_{i \in I} X_i. For a proof of the proposition it suffices to verify the existence of an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda, with infinite support contained in X. Indeed, if f is such a function, then, for each vertex from X_i, i \in I, it is clear that either the function f or the function f + f_i has the property required in the proposition. The finite subsets X_i, i \in I, form a cover of the infinite set X, and hence at least one of the following two assertions holds: 1) for some infinite subset J \subseteq I, the sets X_j, j \in J, are pairwise disjoint; 2) for some vertex v \in X, the set \{i \in I\colon v \in X_i\} is infinite. If assertion 1) holds, then, since the graph \Gamma is locally finite, there exists an infinite subset J' \subseteq J such that (X_{j_1} \cup \Gamma(X_{j_1})) \cap (X_{j_2} \cup \Gamma(X_{j_2})) = \varnothing for arbitrary different j_1, j_2 \in J'. But then the function f \in F^{V(\Gamma)} such that f(u) = 0 for u \in V(\Gamma) \setminus \bigcup_{j \in J'}X_j and f(u) = f_{j}(u) for u \in X_{j}, where j \in J', is, clearly, an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda with infinite support \bigcup_{j \in J'}X_j\subseteq X. So, let us assume that assertion 2) holds. Since the graph \Gamma is locally finite and since each of the sets X_i, i \in I, is \Gamma^2-connected, there exists an infinite path u_0 = v, u_1, u_2,\dotsc of the graph \Gamma^2 with pairwise different vertices such that, for each natural number n, there exists i \in I such that \{u_0,\dotsc,u_n\} \subseteq X_{i}. Since each of the sets X_i, i \in I, is finite, there clearly exists an infinite increasing sequence n_0 = 0,n_1,n_2,\dotsc of non-negative integers such that, for each k \in \mathbb{Z}_{\geqslant 1}, there exists i_k \in I such that u_{n_{k-1}} \in X_{i_k} and \{u_{n_k},u_{n_{k+1}},u_{n_{k+2}},\dots\} \cap X_{i_k} = \varnothing. Consider the following system of linear equations over the field F with unknowns x_u, where u \in V(\Gamma): the system consists, first, of the equations (\sum_{u' \in \Gamma(u)}x_{u'}) - \lambda x_u = 0 for all u \in V(\Gamma), second, of the equations x_u = 0 for all u \in V(\Gamma) \setminus X, and third, of the equations x_{u_{n_k}} = 1 for all k \in \mathbb{Z}_{\geqslant 0}. By existence of the functions f_{i_1},f_{i_2},f_{i_3},\dotsc , each finite subsystem of this system is consistent over F. (As a solution, we may take the values at vertices of an appropriate linear combination of the functions f_{i_1},f_{i_2},f_{i_3},\dotsc . Note that, for each k \in \mathbb{Z}_{\geqslant 1}, by the choice of f_{i_k}, we have (\sum_{u' \in \Gamma(u)}f_{i_k}(u')) - \lambda f_{i_k}(u) = 0 for all u \in V(\Gamma), f_{i_k}(u) = 0 for all u \in V(\Gamma) \setminus X, f_{i_k}(u_{n_{k-1}}) \neq 0 and f_{i_k}(u_{n_l}) = 0 for all l \in \mathbb{Z}_{\geqslant k}.) Therefore, by the Toeplitz theorem (see Proposition 2.2), the entire system is also consistent over F. Let x'_u \in F, where u varies over the set V(\Gamma), be some solution of this system over F. If f \in F^{V(\Gamma)} is defined by f(u) = x'_u for all u \in V(\Gamma), we get an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda with infinite support contained in X. This completes the proof of Proposition 3.5. The following result is another corollary to the Toeplitz theorem. Proposition 3.6. Let \Gamma be a locally finite graph and F be a field with absolute value |\,{\cdot}\,|_\mathrm{v} such that the metric on F associated with this absolute value is complete and is non-discrete. Then, for \lambda \in F, the following conditions (i) and (ii) are equivalent. (i) There exists eigenfunction of the adjacency operator A_{\Gamma,F} corresponding to the eigenvalue \lambda whose support coincides with V(\Gamma). (ii) For each finite subset X \subseteq V(\Gamma) and each vertex u \in X, there exists f_{X,u} \in F^{V(\Gamma)} such that ((A_{\Gamma,F} - \lambda E)(f_{X,u}))|_X = 0 and f_{X,u}(u) \neq 0. Proof. In the proof of Proposition 3.6 we will assume without loss of generality that the graph \Gamma is connected (because, clearly, in the general case it suffices to prove the proposition for connected components of the graph \Gamma) and infinite (because for a finite graph \Gamma in (ii) one may put X = V(\Gamma), and, since the field F is infinite, the vector space W of eigenfunctions of the adjacency operator A_{\Gamma,F} corresponding to the eigenvalue \lambda cannot be the union over all u \in V(\Gamma) of the eigensubspaces W_{u} consisting, for each vertex u \in V(\Gamma), of eigenfunctions of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda which vanish at u ). Let (ii) hold. We enumerate all vertices of the graph \Gamma by natural numbers, V(\Gamma) = \{v_1,v_2,\dots\}, and define (see below) the functions f_i \in F^{V(\Gamma)}, i \in \mathbb{Z}_{\geqslant 1}, with the following two properties: 1) (A_{\Gamma,F} - \lambda E)(f_i) = 0 for each i \in \mathbb{Z}_{\geqslant 1}; 2) for each j \in \mathbb{Z}_{\geqslant 1}, the sequence f_1(v_j), f_2(v_j), \dotsc converges to some non-zero element c_j of the field F in the metric defined on F by the absolute value |\,{\cdot}\,|_\mathrm{v}). It is clear that in this case the function f \in F^{V(\Gamma)}, as defined by f(v_j) = c_j for all j \in \mathbb{Z}_{\geqslant 1}, has the properties required in (i). To define the functions f_i, i \in \mathbb{Z}_{\geqslant 1}, we induct on i. Let i \in \mathbb{Z}_{\geqslant 1}. Assume that the functions f_{i'} are already defined for all i' \in \mathbb{Z}_{\geqslant 1}, i' < i. From (ii) and the Toeplitz theorem (see Proposition 2.2) it follows that there exists \widetilde f_i \in F^{V(\Gamma)} such that (A_{\Gamma,F} - \lambda E)(\widetilde f_i) = 0 and \widetilde f_i (v_i) = 1 (because these conditions are equivalent to solvability of a system of linear equations in which each finite subsystem is solvable by (ii)). For i = 1, we set f_1 = \widetilde f_1. For i > 1, we set f_i := f_{i-1} + \varepsilon_i \widetilde f_i, where \varepsilon_i \neq 0 is such that, first, |\varepsilon_i|_\mathrm{v} |\widetilde f_i(v_{i'})|_\mathrm{v} \leqslant 3^{-i}|f_{i-1}(v_{i'})|_\mathrm{v} for all i' < i and, second, |\varepsilon_i|_\mathrm{v} \leqslant 3^{-i}|f_{i-1}(v_{i})|_\mathrm{v} if f_{i-1}(v_{i}) \neq 0. It is easily checked that this definition is correct and that the so-defined functions f_i \in F^{V(\Gamma)}, i \in \mathbb{Z}_{\geqslant 1}, have properties 1) and 2). This completes the proof of the proposition, because (ii) follows trivially from (i). ### § 4. Propagators If \Gamma is a locally finite graph, F is a field with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F, and v \in V(\Gamma), then, by definition, an (F,\lambda)-propagator of the graph \Gamma relative to the vertex v is any function f \in F^{V(\Gamma)} such that (A_{\Gamma,F} - \lambda E)(f) = \delta_v, where, we recall, \delta_v \in F^{V(\Gamma)}, \delta_v(v) = 1 and \delta_v(u) = 0 for all u \in V(\Gamma) \setminus \{v\}. Note that the property of a function f \in F^{V(\Gamma)} to be an (F,\lambda)-propagator of the graph \Gamma relative to the vertex v is independent of the choice of the absolute value |\,{\cdot}\,|_\mathrm{v}. It is clear that the (F,\lambda)-propagators of a locally finite graph \Gamma relative to a vertex v are precisely those f \in F^{V(\Gamma)} satisfying the following condition: if X is a connected component of the graph \Gamma, then f|_X is an (F,\lambda)-propagator of the graph \langle X \rangle_{\Gamma} relative to the vertex v in the case v \in X and is either the zero function or the eigenfunction of the operator A_{\langle X \rangle_{\Gamma},F} corresponding to the eigenvalue \lambda in the case v \notin X. Remark 4.1. An (F,\lambda)-propagator of the graph \Gamma relative to the vertex v is, effectively, a Green function (or a fundamental solution) with respect to v for the operator A_{\Gamma,F} - \lambda E, and, qua such function, features a number of “expected” properties. However, many “standard” tricks for dealing with Green functions cannot be applied here due to specific properties of the space on which the operator A_{\Gamma,F} - \lambda E is defined. In this, and, especially, in the subsequent sections, we will show that a number of important properties of the operator A_{\Gamma,F} - \lambda E (where \Gamma is a locally finite graph, F is a field with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F) and, in particular, the injectivity property (or, in other words, the property of \lambda to be not an eigenvalue of A_{\Gamma,F}) can be formulated in terms of (F,\lambda)-propagators of the graph \Gamma. It is also worth pointing out that below (see especially § 6) we will show that in many situations the study of (F,\lambda)-propagators of the graph \Gamma is more easy than the direct study of these important properties and (which has great value for the topic of the present paper) the eigenfunctions of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda. Let \Gamma be a locally finite graph and F be a field with absolute value |\,{\cdot}\,|_\mathrm{v}. In general, for given \lambda \in F, and v \in V(\Gamma), the graph \Gamma may fail to have an (F,\lambda)-propagator relative to v (for example, for \lambda = 0 in the case V(\Gamma) = \{v\}), and, on the other hand, such a propagator may fail to be unique (numerous corresponding examples will be considered below). Note that, for \lambda \in F, the difference of two different (F,\lambda)-propagators of the graph \Gamma relative to the same vertex is an eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda. Conversely, for \lambda \in F, the sum of an (F,\lambda)-propagator of the graph \Gamma relative to some its vertex and the eigenfunction of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda is a different (F,\lambda)-propagator of the graph \Gamma relative to the same vertex. For a locally finite graph \Gamma, a field F with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F, and v \in V(\Gamma), it was already noted that the property of a function from V(\Gamma) to F to be an (F,\lambda)-propagator of the graph \Gamma relative to v is independent of the choice of |\,{\cdot}\,|_\mathrm{v}. In addition (cf. the beginning of § 3), using Proposition 2.2 one can easily show that the existence of an (F,\lambda)-propagator of the graph \Gamma relative to v is equivalent to that of an (F',\lambda)-propagator of the graph \Gamma relative to v for some extension F' of the field F_0(\lambda), where F_0 is a prime subfield of the field F. We will formalize these findings (which can be used, for construction of propagators, for convenient variations of fields and equipment of these fields with appropriate absolute values) in a slightly refined way in Proposition 4.1 (which is an analogue for propagators of Proposition 3.1 for eigenfunctions). If \Gamma is a locally finite graph, F is a field with absolute value |\,{\cdot}\,|_\mathrm{v}, \lambda \in F, v \in V(\Gamma) and f is an (F,\lambda)-propagator of the graph \Gamma relative to the vertex v, then the extended support of the (F,\lambda)-propagator f is defined as the union of the support of f and \{v\} (in general, v may fail to lie in the support of f). Proposition 4.1. Let \Gamma be a locally finite graph, F be a field with absolute value |\,{\cdot}\,|_\mathrm{v}, F_0 be the prime subfield of the field F, and \lambda \in F. Then, for v \in V(\Gamma), the following assertions hold. 1) If \varphi is an embedding of the field F into some field F' with arbitrary absolute value |\,{\cdot}\,|_{\mathrm{v}'}, and f is an (F',\varphi(\lambda))-propagator of the graph \Gamma relative to the vertex v such that f(u) \in \varphi(F) for all u \in V(\Gamma), then the function \varphi^{-1} f \in F^{V(\Gamma)} is an (F,\lambda)-propagator of the graph \Gamma relative to the vertex v. 2) If f is an (F,\lambda)-propagator of the graph \Gamma relative to the vertex v, then there exists an (F_0(\lambda),\lambda)-propagator of the graph \Gamma relative to the vertex v whose extended support is contained in that of f. Proof. Assertion 1) is clear. The proof of 2) is similar to that of assertion 2) of Proposition 3.1, but the system of linear equations over F with unknowns x_u, where u \in V(\Gamma), now consists, first, of the equations (\sum_{u' \in \Gamma(u)}x_{u'}) - \lambda x_u = 0 for all u \in V(\Gamma) \setminus \{v\}, second, of the equations x_u = 0 for all vertices u of the graph \Gamma not lying in the extended support of f, and, third, of the equation (\sum_{u' \in \Gamma(v)}x_{u'}) - \lambda x_v = 1. Let \Gamma be a locally finite graph, F be a field with absolute value |\,{\cdot}\,|_\mathrm{v} and \lambda \in F. If the graph \Gamma has some (F,\lambda)-propagator, say p_u, relative to each its vertex u, then the matrix \mathbf{P} from M_{V(\Gamma)\times V(\Gamma)}(F), in which, for u_1, u_2 \in V(\Gamma), the element at the row corresponding to u_1 and the column corresponding to u_2 is p_{u_2}(u_1), is a right inverse of the matrix \mathbf{A}_{\Gamma,F} - \lambda \mathbf{E} (and, since \mathbf{A}_{\Gamma,F} - \lambda \mathbf{E} is symmetric, the matrix \mathbf{P}^\top is a left inverse of \mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}). Conversely, if \mathbf{P} is a matrix from M_{V(\Gamma)\times V(\Gamma)}(F) which is a right inverse of \mathbf{A}_{\Gamma,F} - \lambda \mathbf{E} (this is equivalent to saying that \mathbf{P}^\top is a left inverse of \mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}), then, for each u \in V(\Gamma), if a function p_u \in F^{V(\Gamma)} is such that its value p_u(w) for an arbitrary w \in V(\Gamma) is equal to the element of the matrix \mathbf{P} for the row corresponding to w and the column corresponding to u, then it is an (F,\lambda)-propagator of the graph \Gamma relative to u. Finally, we note that, for \lambda \in F, in view of Corollary 2.1, the surjectivity of the operator A_{\Gamma,F} - \lambda E is equivalent to the existence of an (F,\lambda)-propagator in the graph \Gamma relative to each its vertex. For a locally finite graph \Gamma, a field F with absolute value |\,{\cdot}\,|_\mathrm{v}, and \lambda \in F, we say that a vertex v \in V(\Gamma) is (F,\lambda)-singular if the graph \Gamma does not admit (F,\lambda)-propagators relative to v. By S_{F,\lambda}(\Gamma) we denote the set of all (F,\lambda)-singular vertices of the graph \Gamma. (So, in view of the above remark, the surjectivity condition for A_{\Gamma,F} - \lambda E, as well as the condition that M_{V(\Gamma)\times V(\Gamma)}(F) has a right inverse matrix for \mathbf{A}_{\Gamma,F} - \lambda \mathbf{E} is equivalent to the condition S_{F,\lambda}(\Gamma) = \varnothing.) It is clear that the set S_{F,\lambda}(\Gamma) is \operatorname{Aut(}\Gamma)-invariant, and from Proposition 4.1 it follows that S_{F,\lambda}(\Gamma) = S_{F',\lambda}(\Gamma) for an arbitrary extension F' (with any absolute value) of the field F_0(\lambda), where F_0 is the prime subfield of the field F. In the case of a finite graph \Gamma, for an element \lambda of the field F, it is easily seen that the condition S_{F,\lambda}(\Gamma) \neq \varnothing is equivalent to saying that \lambda lies in the spectrum of the graph \Gamma over F, and, for v \in V(\Gamma), the condition v \in S_{F,\lambda}(\Gamma) is equivalent to saying that v lies in the support of some eigenfunction of the adjacency matrix of the graph \Gamma over F corresponding to the eigenvalue \lambda. Below (see Theorem 4.1), we will show that also in the general case of an arbitrary locally finite graph \Gamma, the set S_{F,\lambda}(\Gamma) coincides with the union of all finite supports of the eigenfunctions of the operator A_{\Gamma,F} corresponding to the eigenvalue \lambda. The next result is an easy consequence of the Toeplitz theorem (see Proposition 2.2). Proposition 4.2. Let \Gamma be a locally finite graph, F be a field with absolute value |\,{\cdot}\,|_\mathrm{v}, and \lambda \in F. Then, for v \in V(\Gamma), the following conditions (i) and (ii) are equivalent. (i) v \in S_{F,\lambda}(\Gamma). (ii) For some finite subset X of the set V(\Gamma), there is no f' \in F^{V(\Gamma)} such that ((A_{\Gamma,F} - \lambda E)(f'))(v) = 1 and ((A_{\Gamma,F} - \lambda E)(f'))(u) = 0 for all u \in X \setminus \{v\}. (It is clear that, in this case, any finite subset of the set V(\Gamma) contains X also shares this property.) The next result is a corollary of Propositions 4.2 and 4.1. Proposition 4.3. Let \Gamma be a locally finite graph, F be a field with absolute value |\,{\cdot}\,|_\mathrm{v}, and \lambda \in F. Assume, in addition, that v \in S_{F,\lambda}(\Gamma). For each r \in \mathbb{Z}_{\geqslant 0}, let the system \operatorname{Pr\operatorname{Syst}}_r of linear equations over F with unknowns x_u, where u \in B_{\Gamma}(v,r + 1), contain, by definition, the equation (\sum_{u' \in \Gamma(v)}x_{u'}) - \lambda x_v = 1 and, for each u \in B_{\Gamma}(v,r) \setminus \{v\}, the equation (\sum_{u' \in \Gamma(u)}x_{u'}) - \lambda x_u = 0. Then there exists \widetilde{r}_{\lambda,v} \in \mathbb{Z}_{\geqslant 0} (the radius of propagator inconsistency for \lambda and v$$"$) such that the system $\operatorname{Pr\operatorname{Syst}}_r$ is consistent (over $F$) if and only if $r < \widetilde{r}_{\lambda,v}$. In addition, the number $\widetilde{r}_{\lambda,v}$ is not changed if $F$ is replaced by $F_0(\lambda)$, where $F_0$ is the prime subfield of the field $F$.

For a locally finite connected graph $\Gamma$ and an element $\lambda$ of the field $F$, it may well be that $S_{F,\lambda}(\Gamma) \neq \varnothing$ and even $S_{F,\lambda}(\Gamma) = V(\Gamma)$ (this holds, for example, for finite regular connected graphs of degree $d \in \mathbb{Z}_{\geqslant 1}$ for $\lambda = d\cdot 1_{F}$ or finite connected vertex-symmetric (that is, with vertex-transitive groups of automorphisms) graphs for $\lambda$ lying in their spectra over $F$; for examples of infinite locally finite connected vertex-symmetric graphs $\Gamma$ with $S_{\mathbb{C},\lambda}(\Gamma) = V(\Gamma)$ for some $\lambda$; see § 8.5). However, as we will see below (see, for example, Corollary 4.2), for a locally finite graph $\Gamma$ and an element $\lambda$ of the field $F$, the situation, where $\Gamma$ has an $(F,\lambda)$-propagator relative to each its vertex (that is, when $S_{F,\lambda}(\Gamma) = \varnothing$) is generic, in a sense.

The following Propositions 4.4 and 4.5 are analogues, for propagators, of Propositions 3.3 and 3.4 for eigenfunctions of the adjacency operators of locally finite graphs.

Proposition 4.4. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, $\lambda \in F$, and $v \in V(\Gamma)$. If $X_i$, $i \in I$, is a non-empty linearly ordered by inclusion family of subsets of the set $V(\Gamma)$ which are extended supports of $(F,\lambda)$-propagators of the graph $\Gamma$ relative to $v$, then some subset of the set $\bigcap_{i \in I}X_i$ is an extended support of an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to $v$. In particular, each extended support of an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to $v$ contains an inclusion-minimal extended support among the extended supports of the $(F,\lambda)$-propagators of the graph $\Gamma$ relative to $v$.

Proof. The required result follows by an application of the Toeplitz theorem (see Proposition 2.2) to the system of linear equations over $F$ with unknowns $x_u$, where $u \in V(\Gamma)$, which consists, first, of the equations $(\sum_{u' \in \Gamma(u)}x_{u'}) - \lambda x_u = 0$ for all $u \in V(\Gamma) \setminus \{v\}$, second, of the equations $x_u = 0$ for all $u \in V(\Gamma) \setminus \bigcap_{i \in I}X_i$, and, third, of the equation $(\sum_{v' \in \Gamma(v)}x_{v'}) - \lambda x_v = 1$.

If $\Gamma$ is a locally finite graph, $F$ is a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, $\lambda \in F$, $v \in V(\Gamma)$, and $p_v$ is an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to the vertex $v$, then, if $X \subseteq V(\Gamma)$ with $v \in X$ is the union of a system of connected components of the extended support $p_v$, then the function from $F^{V(\Gamma)}$ which coincides with $p_v$ on $X$ and which is identically zero on $V(\Gamma) \setminus X$ is not, in general, an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to $v$, even though the restriction of $p_v$ to $X$ is, clearly, an $(F,\lambda)$-propagator of the graph $\langle X \rangle_{\Gamma}$ relative to $v$. However (as in the case of eigenfunctions, see § 3), such an effect does not occur if $\Gamma^2$-connected components are considered in place of the connected components of the extended support of $p_v$.

Indeed, if $\Gamma$ is a locally finite graph, $F$ is a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, $\lambda \in F$, $v \in V(\Gamma)$ and $p_v$ is an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to $v$, then, if $X \subseteq V(\Gamma)$ with $v \in X$ is the union of some family of ${\Gamma^2}$-connected components of the extended support of $p_v$, the function from $F^{V(\Gamma)}$ which coincides with $p_v$ on $X$ and which is identically zero on $V(\Gamma) \setminus X$ is, clearly, also an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to $v$. In particular, if a ${\Gamma^2}$-connected component of the extended support of $p_v$ which contains $v$ (and which can be naturally called the principal ${\Gamma^2}$-connected component of the extended support of $p_v$) is an extended support of an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to the vertex $v$. As a corollary, for the above (see Proposition 4.4) inclusion-minimal among the extended supports of $(F,\lambda)$-propagators of the graph $\Gamma$ relative to $v$ we have the following assertion.

Proposition 4.5. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, $\lambda \in F$, and $v \in V(\Gamma)$. Then each inclusion-minimal extended support among the extended supports of the $(F,\lambda)$-propagators of the graph $\Gamma$ relative to $v$ is $\Gamma^2$-connected.

Remark 4.2. By assertion 2) of Proposition 4.1, for each minimal subset from Proposition 4.5, an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to the vertex $v$ such that this subset is its extended support can be chosen from $F_0(\lambda)^{V(\Gamma)}$, that is, it can be assumed to be an $(F_0(\lambda),\lambda)$-propagator.

We will need the following result in our analysis.

Proposition 4.6. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Assume, in addition, that, for a vertex $v$ of the graph $\Gamma$, there is a sequence $(v_i)_{i \in \mathbb{Z}_{\geqslant 1}}$ of pairwise different vertices of the graph $\Gamma$ such that, for each $i \in \mathbb{Z}_{\geqslant 1}$ there exists an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to the vertex $v_i$ with finite $\Gamma^2$-connected extended support $X_i\ni v$. Then there exists an eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ which has infinite support containing the vertex $v$ and which lies in $\bigcup_{i \in \mathbb{Z}_{\geqslant 1}} X_i$.

Proof. By the assumption, for each $i \in \mathbb{Z}_{\geqslant 1}$, there exists an $(F,\lambda)$-propagator $p_i$ of the graph $\Gamma$ relative to the vertex $v_i$ with extended support $X_i$. We set $X:= \bigcup_{i \in \mathbb{Z}_{\geqslant 1}} X_i$.

Since the graph $\Gamma$ is locally finite and since each of the sets $X_i$, $i \in I$, is $\Gamma^2$-connected, there exists an infinite path $u_0 = v, u_1, u_2,\dotsc$ of the graph $\Gamma^2$ with pairwise different vertices such that, for each integer positive number $n$, there exists $i \in I$ with the property $\{u_0,\dotsc,u_n\} \subseteq X_{i}$.

Let $k \in \mathbb{Z}_{\geqslant 0}$. Consider the following system of linear equations over the field $F$ with unknowns $x_u$, where $u \in V(\Gamma)$: the system consists, first, of the equations $(\sum_{u' \in \Gamma(u)}x_{u'}) - \lambda x_u = 0$ for all $u \in V(\Gamma)$, second, of the equations $x_u = 0$ for all $u \in V(\Gamma) \setminus X$, and, third, of the equation $x_{u_k} = 1$. Since we have the functions $p_{1},p_{2},p_{3},\dotsc$, each finite subsystem of this system is consistent over $F$. Therefore, by the Toeplitz theorem (see Proposition 2.2), the entire system is consistent over $F$. Let $x'_u \in F$, where $u$ varies over the set $V(\Gamma)$, be some solution of this system over $F$. Let $f_k \in F^{V(\Gamma)}$ be defined by $f_k(u) = x'_u$ for all $u \in V(\Gamma)$. As a result, we get an eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$, the support of this eigenfunction lies in $X$, and $f_k(u_k) = 1$.

If the support of the function $f_0$ is infinite, then the function $f_0$ has the properties required in Proposition 4.6. Assume that the support of the function $f_0$ is finite. If, for some $k \in \mathbb{Z}_{\geqslant 1}$, the support of the function $f_k$ is infinite, then the function $f_k$ or the function $f_k + f_0$ have the properties required in Proposition 4.6. So, let us assume that, for each $k \in \mathbb{Z}_{\geqslant 0}$, the support of the function $f_k$ is finite. But in this case, Proposition 4.6 follows from Proposition 3.5 (in which one should put $I = \mathbb{Z}_{\geqslant 0}$, and consider the support of the function $f_i$ as $X_i$, $i \in I$).

Given a locally finite graph $\Gamma$, a field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$ and $\lambda \in F$, a vertex $v \in V(\Gamma)$ is called $(F,\lambda)$-local if the graph $\Gamma$ has an $(F,\lambda)$-propagator relative to $v$ with finite support, or, in other words, if $\delta_v \in (A_{\Gamma,F} - \lambda E)(F^{V(\Gamma)*})$. By $L_{F,\lambda}(\Gamma)$ we denote the set of all $(F,\lambda)$-local vertices of the graph $\Gamma$. (So, the condition that $A_{\Gamma,F} - \lambda E$ maps $F^{V(\Gamma)*}$ surjectively onto itself, as well as the condition that $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ has the inverse matrix in $M^{\mathrm{rcf}}_{V(\Gamma)\times V(\Gamma)}(F)$, is equivalent to the condition $L_{F,\lambda}(\Gamma) = V(\Gamma)$.) It is clear that set $L_{F,\lambda}(\Gamma)$ is $\operatorname{Aut(}\Gamma)$-invariant, and from assertion 2) of Proposition 4.1 it follows that $L_{F,\lambda}(\Gamma) = L_{F',\lambda}(\Gamma)$ for an arbitrary extension $F'$ (with arbitrary absolute value) of the field $F_0(\lambda)$, where $F_0$ is the prime subfield of the field $F$. Below (see Theorem 4.2) we will show that $L_{F,\lambda}(\Gamma)$ is precisely the complement in $V(\Gamma)$ of the union of all supports of eigenfunctions of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$. (So, it will be shown that $L_{F,\lambda}(\Gamma)$ is precisely the set of vertices $v$ of the graph $\Gamma$ for which the number $r_{\lambda,v}$ is defined in accordance with Proposition 3.2.)

In the case of a finite graph $\Gamma$, the partition $V(\Gamma) = S_{F,\lambda}(\Gamma) \cup L_{F,\lambda}(\Gamma)$ clearly holds, and $L_{F,\lambda}(\Gamma) \neq V(\Gamma)$ if and only if $\lambda$ lies in the spectrum of the graph $\Gamma$ over $F$.

For further purposes, we need some trivial (in principle) observations regarding eigenfunctions of the matrix representation of the adjacency operator of a locally finite graph. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. For $u \in V(\Gamma)$ (in accordance with § 2), we set $\alpha_u := (\sum_{u' \in \Gamma(u)}\delta_{u'}) - \lambda \delta_u$. Let, in addition, $\boldsymbol{\alpha}_u$, where $u \in V(\Gamma)$, is the column of the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$, corresponding to $u$. (So, $\boldsymbol{\alpha}_u^\top$ is the row of the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ corresponding to $u$.) It is clear that the element of the column $\boldsymbol{\alpha}_u$ from the row corresponding to $v \in V(\Gamma)$ is $\alpha_u(v)$. Next, since $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E} \in M^{\mathrm{rcf}}_{V(\Gamma)\times V(\Gamma)}(F)$, the column $\sum_{u \in V(\Gamma)} f(u)\boldsymbol{\alpha}_u$ is correctly defined in the natural way for an arbitrary function $f \in F^{V(\Gamma)}$. Furthermore, $f$ is an eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ if and only if $f$ is a non-zero function with the property $\sum_{u \in V(\Gamma)} f(u)\boldsymbol{\alpha}_u = \mathbf{0}$, where $\mathbf{0}$ is the zero column. (Similarly, $f$ is an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to its vertex $v$ if and only if $\sum_{u \in V(\Gamma)} f(u)\boldsymbol{\alpha}_u = \boldsymbol{\delta}_v$, where $\boldsymbol{\delta}_v$ is the column with 1 at the position corresponding to the vertex $v$, and with 0 at the remaining positions.) In particular, if $X$ is a finite subset of $V(\Gamma)$ and $v$ is some vertex from $X$, then the operator $A_{\Gamma,F}$ has an eigenfunction corresponding to the eigenvalue $\lambda$ whose support lies in $X$ and contains $v$ if and only if the column $\boldsymbol{\alpha}_v$ is a linear combination (with coefficients from $F$) of the columns $\boldsymbol{\alpha}_u$, $u \in X \setminus \{v\}$, or, equivalently, the function $\alpha_v$ is a linear combination (with coefficients from $F$) of the functions $\alpha_u$, $u \in X \setminus \{v\}$.

Proposition 4.7. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then, for any finite subset $X$ of $V(\Gamma)$ and $v \in X$, the following conditions (i) and (ii) are equivalent.

(i) The operator $A_{\Gamma,F}$ has an eigenfunction $f$ corresponding to the eigenvalue $\lambda$ such that the support of $f$ is contained in $X$ and contains $v$.

(ii) There does not exist $f' \in F^{V(\Gamma)}$ such that $((A_{\Gamma,F} - \lambda E)(f'))(v) = 1$ and $((A_{\Gamma,F} - \lambda E)(f'))(u) = 0$ for all $u \in X \setminus \{v\}$.

Proof. For arbitrary $u_1,u_2 \in V(\Gamma)$, let $\alpha_{u_1,u_2} = \alpha_{u_2}(u_1)$ be the element of the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ at the row corresponding to $u_1$, and the column corresponding to $u_2$. (Note that $\alpha_{u_1,u_2} = \alpha_{u_2,u_1}$, since the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ is symmetric.)

Assume that condition (i) is met, but there exists a function $f' \in F^{V(\Gamma)}$ such that $((A_{\Gamma,F} - \lambda E)(f'))(v) = 1$ and $((A_{\Gamma,F} - \lambda E)(f'))(u) = 0$ for all $u \in X \setminus \{v\}$. Without loss of generality we can assume that the support of $f'$ is contained in $X \cup \Gamma(X)$ (and, therefore, the supports of the functions $f$ and $f'$ are finite). On the one hand, we have

$$$$\sum_{u_1,u_2 \in V(\Gamma)}f'(u_1)\alpha_{u_1,u_2}f(u_2)=\sum_{u_1 \in V(\Gamma)}f'(u_1) \sum_{u_2 \in V(\Gamma)}\alpha_{u_1,u_2}f(u_2)=0.$$ \tag{4.1}$$
But, on the other hand,
\begin{equation*} \begin{aligned} \, &\sum_{u_1,u_2 \in V(\Gamma)}f'(u_1)\alpha_{u_1,u_2}f(u_2)=\sum_{u_2 \in V(\Gamma)}f(u_2) \sum_{u_1 \in V(\Gamma)}\alpha_{u_1,u_2}f'(u_1) \\ &\qquad= \sum_{u_2 \in X}f(u_2) \sum_{u_1 \in X \cup \Gamma(X)}\alpha_{u_1,u_2}f'(u_1) \\ &\qquad =\sum_{u_2 \in X}f(u_2) \sum_{u_1 \in X \cup \Gamma(X)}\alpha_{u_2,u_1}f'(u_1)= f(v) \ne 0. \end{aligned} \end{equation*} \notag
So, (ii) follows from (i).

We claim that (ii) implies (i). If the function $\alpha_v \in F^{V(\Gamma)}$ lies in the linear hull in $F^{V(\Gamma)}$ of the functions $\alpha_u$, $u \in X\setminus \{v\}$, then, as mentioned before the proposition, (i) holds. So, let us assume that (ii) is met, but the function $\alpha_v$ is not contained in the linear hull in $F^{V(\Gamma)}$ of the functions $\alpha_u$, $u \in X \setminus \{v\}$. Then the subspace $\langle\delta_u : u \in X \cup \Gamma(X)\rangle$ of the vector space $F^{V(\Gamma)}$ contains $\alpha_u$, $u \in X$, and admits a linear functional $\chi$ such that $\chi(\alpha_v) = 1$ and $\chi(\alpha_u) = 0$ for all $u \in X \setminus \{v\}$. We define $f'' \in F^{V(\Gamma)}$ by $f''(u) = \chi(\delta_u)$ for all $u \in X \cup \Gamma (X)$ and $f''(u) = 0$ for all $u \in V(\Gamma) \setminus (X \cup \Gamma (X))$. It is easily seen that, for the function $f''$, we have $((A_{\Gamma,F} - \lambda E)(f''))(v) = 1$ and $((A_{\Gamma,F} - \lambda E)(f''))(u) = 0$ for all $u \in X \setminus \{v\}$. This, however, contradicts the above assumption that (ii) holds. This completes the proof of the proposition.

The following proposition is dual in a sense to Proposition 4.7.

Proposition 4.8. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then, for any finite subset $X$ of $V(\Gamma)$ and $v \in X$, the following conditions (i) and (ii) are equivalent.

(i) There does not exist $f \in F^{V(\Gamma)}$ such that $v$ lies in the support of $f$ and $((A_{\Gamma,F} - \lambda E)(f))(u) = 0$ for all $u \in X$.

(ii) The graph $\Gamma$ has an $(F,\lambda)$-propagator $f'$ relative to the vertex $v$ such that the support of $f'$ is contained in $X$.

Proof. As in the proof of Proposition 4.7, for arbitrary $u_1,u_2 \in V(\Gamma)$, let $\alpha_{u_1,u_2} = \alpha_{u_2}(u_1)$ be the element of the $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ for the row corresponding to $u_1$ and the column corresponding to $u_2$.

Assume that (ii) holds, but there exists a function $f \in F^{V(\Gamma)}$ such that $f(v) \neq 0$ and $((A_{\Gamma,F} - \lambda E)(f))(u) = 0$ for all $u \in X$. Without loss of generality we can assume that the support of $f$ is contained in $X \cup \Gamma(X)$ (and, therefore, the functions $f$ and $f'$ have finite supports). It is easily checked that, for $f$ and $f'$, on the one hand, (4.1) still holds, but on the other hand,

\begin{equation*} \begin{aligned} \, &\sum_{u_1,u_2 \in V(\Gamma)}f'(u_1)\alpha_{u_1,u_2}f(u_2) = \sum_{u_1 \in X,u_2 \in X \cup \Gamma(X)}f'(u_1)\alpha_{u_1,u_2}f(u_2) \\ &\qquad= \sum_{u_2 \in X \cup \Gamma(X)}f(u_2)\sum_{u_1 \in X}\alpha_{u_1,u_2}f'(u_1) = \sum_{u_2 \in X \cup \Gamma(X)}f(u_2)\sum_{u_1 \in V(\Gamma)}\alpha_{u_1,u_2}f'(u_1) \\ &\qquad= \sum_{u_2 \in X \cup \Gamma(X)}f(u_2)\sum_{u_1 \in V(\Gamma)}\alpha_{u_2,u_1}f'(u_1)= f(v) \ne 0. \end{aligned} \end{equation*} \notag
This contradiction proves that (ii) implies (i).

Let us show that (i) implies (ii). Condition (ii) is equivalent to saying that $\delta_v$ lies in the linear hull in $F^{V(\Gamma)}$ of the functions $\alpha_u$, $u \in X$. Assume that (i) holds, but the function $\delta_v$ does not lie in the linear hull in $F^{V(\Gamma)}$ of the functions $\alpha_u$, $u \in X$. In this case, the subspace $\langle\delta_u : u \in X \cup \Gamma(X)\rangle$ of the vector space $F^{V(\Gamma)}$ contains $\alpha_u$, $u \in X$, and admits a linear functional $\chi$ such that $\chi(\delta_v) = 1$ and $\chi(\alpha_u) = 0$ for all $u \in X$. Let $f'' \in F^{V(\Gamma)}$ be defined by $f''(u) = \chi(\delta_u)$ for all $u \in X \cup \Gamma (X)$ and $f''(u) = 0$ for all $u \in V(\Gamma) \setminus (X \cup \Gamma (X))$. It is easily seen that, for the function $f''$, we have $f''(v) = 1$ and $((A_{\Gamma,F} - \lambda E)(f''))(u) = 0$ for all $u \in X$. This, however, contradicts the above assumption that (i) holds. This proves of the proposition.

The next result follows from Proposition 4.7 and the Toeplitz theorem (see Proposition 2.2).

Theorem 4.1. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then, for $v \in V(\Gamma)$, the following conditions (i) and (ii) are equivalent.

(i) The operator $A_{\Gamma,F}$ has an eigenfunction corresponding to the eigenvalue $\lambda$ whose support is finite and contains $v$.

(ii) The graph $\Gamma$ does not admit $(F,\lambda)$-propagators relative to the vertex $v$. In other words, $v \in S_{F,\lambda}(\Gamma)$.

Corollary 4.1. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then the set $S_{F,\lambda}(\Gamma)$ coincides with the union of all finite supports of the eigenfunctions of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$.

Corollary 4.2. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, $F_0$ be the prime subfield of the field $F$, and $\lambda \in F$. Assume, in addition, that $v \in S_{F,\lambda}(\Gamma)$. Then the following assertions hold.

$1)$ There exists a finite subset $X\ni v$ of the set $V(\Gamma)$ such that the subgraph $\langle X \rangle_{\Gamma}$ of the graph $\Gamma$ generated by $X$ is connected, and $\lambda$ is an eigenvalue of the adjacency matrix of the graph $\langle X \rangle_{\Gamma}$ over $F$, and there is an eigenfunction of the adjacency matrix of the graph $\langle X \rangle_{\Gamma}$ over $F$ corresponding to $\lambda$, which lies in $(F_0(\lambda))^X$, and whose support is $X$. In addition, there exists a finite subset $Y\supseteq X$ of the set $V(\Gamma)$ such that the subgraph $\langle Y \rangle_{\Gamma^2}$ of the graph $\Gamma^2$ generated by $Y$ is connected, and $\lambda$ is an eigenvalue of the adjacency matrix of the graph $\langle Z \rangle_{\Gamma}$ over $F$ for each finite subset $Z\supseteq Y$ of the set $V(\Gamma)$, and there is an eigenfunction of the adjacency matrix of the graph $\langle Z \rangle_{\Gamma}$ over $F$ corresponding to $\lambda$ which lies in $(F_0(\lambda))^Z$ and whose support is $Y$. In particular, $\lambda$ is an algebraic element over $F_0$ (and the field $F_0(\lambda)$ is finite if the field $F$ has positive characteristic).

$2)$ If $F$ is a field of characteristic $0$ (that is, $F_0 = \mathbb{Q}$), and $X$ is as in assertion $1)$, then $\lambda$ is a root of a unitary polynomial from $\mathbb{Z}[x]$ of degree $|X|$, whose roots are real, and their (usual on $\mathbb{R}$) absolute values are majorized by the maximum of the degrees of the vertices of the graph $\langle X \rangle_{\Gamma}$ (and are majorized by the maximum of the degrees of the vertices from $X$ in the graph $\Gamma$ which is attained only in the case, where $X\ni v$ is a connected component of the graph $\Gamma$ and $\langle X \rangle_{\Gamma}$ is a (finite) regular graph).

Proof. It is easily checked that as $X$ and $Y$ in assertion $1)$ one may take, respectively, the connected component that contains $v$ and the $\Gamma^2$-connected component that contains $v$ of a finite support of an eigenfunction of the operator $A_{\Gamma,F_0(\lambda)}$ corresponding to the eigenvalue $\lambda$ whose existence is secured by Theorem 4.1 (in which as $F$ one takes $F_0(\lambda)$). Assertion 2) of the corollary follows from assertion 1) and the well-known properties of the spectra of finite graphs.

Remark 4.3. Let $\Gamma$ be a locally finite graph, $F$ be a field of positive characteristic with absolute value $|\,{\cdot}\,|_\mathrm{v}$, $F_0$ be the prime subfield of the field $F$ and $v \in V(\Gamma)$. Then, for $\lambda \in F$, the condition that the graph $\Gamma$ does not admit an $(F,\lambda)$-propagator relative to $v$ (by assertion 1) of Corollary 4.2, this implies that $\lambda$ is algebraic over $F_0$) is equivalent (see assertion 2) of Proposition 4.1) to saying that the graph $\Gamma$ has no an $(F_0(\lambda),\lambda)$-propagator relative to $v$ (where $F_0(\lambda)$ is a finite field); it is also equivalent to saying that (see Theorem 4.1) the vertex $v$ lies in the finite support of an eigenfunction of the adjacency operator $A_{\Gamma,F_0(\lambda)}$ (where $F_0(\lambda)$ is a finite field) corresponding to the eigenvalue $\lambda$.

Recall that Proposition 4.7 and the Toeplitz theorem (see Proposition 2.2) imply Theorem 4.1. Similarly, Proposition 4.8 and the Toeplitz theorem (see Proposition 2.2) imply the following result, which is important in our further analysis (Theorem 4.2 is in a sense dual to Theorem 4.1).

Theorem 4.2. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then, for $v \in V(\Gamma)$, the following conditions (i) and (ii) are equivalent.

(i) The vertex $v$ does not lie in the support of any eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$.

(ii) The graph $\Gamma$ has a finitely supported $(F,\lambda)$-propagator relative to the vertex $v$. In other words, $v \in L_{F,\lambda}(\Gamma)$.

### § 5. Injectivity and some other properties of the operators $A_{\Gamma,F} - \lambda E$ in terms of propagators

In this section, we will show that, for a locally finite graph $\Gamma$, a field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$, several important properties of the operator $A_{\Gamma,F} - \lambda E$ can be naturally formulated in terms of $(F,\lambda)$-propagators of the graph $\Gamma$ relative to its vertices. What is important, the potency of this reformulation will be demonstrated in this and subsequent sections.

By Theorem 4.1, for a locally finite graph $\Gamma$, a field $F$ with some absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$ the condition $S_{F,\lambda}(\Gamma) \neq \varnothing$ is equivalent to saying that the operator $A_{\Gamma,F}$ has an finitely supported eigenfunction corresponding to the eigenvalue $\lambda$, or, in other words, to the condition that the restriction of the operator $A_{\Gamma,F} - \lambda E$ to $F^{V(\Gamma)*}$ is not an injective operator. So, recalling the findings at the beginning of the previous section (after the proof of Proposition 4.1), and using Corollary 2.1 we arrive at the following result.

Theorem 5.1. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then the following conditions (i)–(v) are equivalent.

(i) The operator $A_{\Gamma,F} - \lambda E$ is surjective.

(ii) The matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ has in $M_{V(\Gamma)\times V(\Gamma)}(F)$ a right (or left) inverse matrix (and, therefore, it has a right inverse matrix and a left inverse matrix which are transposes of each other).

(iii) $S_{F,\lambda}(\Gamma) = \varnothing$.

(iv) The operator $A_{\Gamma,F} - \lambda E$ maps the subspace $F^{V(\Gamma)*}$ of the space $F^{V(\Gamma)}$ injectively into itself (or, in other words, the operator $A_{\Gamma,F}$ has no finitely supported eigenfunctions corresponding to the eigenvalue $\lambda$).

$(v)$ $F^{V(\Gamma)*} \subseteq (A_{\Gamma,F} - \lambda E)(F^{V(\Gamma)})$.

The next result is a clear corollary to Theorem 4.1.

Proposition 5.1. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. The set $S_{F,\lambda}(\Gamma)$ is finite if and only if the finitely supported eigenfunctions of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ form a finite-dimensional subspace of the space $F^{V(\Gamma)}$.

The following result is a consequence of Theorem 4.1 and Proposition 3.5.

Proposition 5.2. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. If the set $S_{F,\lambda}(\Gamma)$ is infinite, then the operator $A_{\Gamma,F}$ has an eigenfunction corresponding to the eigenvalue $\lambda$ with infinite support from $S_{F,\lambda}(\Gamma)$.

Remark 5.1. From Theorem 4.1 and Proposition 5.2 it follows that, for a locally finite graph $\Gamma$, a field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$, the condition that $S_{F,\lambda}(\Gamma)$ is infinite implies that each vertex from $S_{F,\lambda}(\Gamma)$ lies in the support of an eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$, and this support is infinite and lies in $S_{F,\lambda}(\Gamma)$. (Indeed, by Theorem 4.1, each vertex $v$ from $S_{F,\lambda}(\Gamma)$ lies in the finite support from $S_{F,\lambda}(\Gamma)$ of some eigenfunction $f_1$ of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$. In addition, by Proposition 5.2, there is an eigenfunction $f_2$ of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ with infinite support from $S_{F,\lambda}(\Gamma)$. If $v$ lies in the support of $f_2$, then $f_2$ is the required function. If $v$ does not lie in the support of $f_2$, then $f_1 + f_2$ is the required function.)

Remark 5.2. Another corollary to Theorem 4.1 is as follows: if $\Gamma$ is a locally finite graph, $F$ is a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$, then $S_{F,\lambda}(\Gamma)$ has no singleton connected components if $\lambda \neq 0$, and has no singleton $\Gamma^2$-connected components if $\lambda = 0$ and $\Gamma$ has no singleton connected components.

The proof of the following result is close to that of Theorem 3 from [9].

Theorem 5.2. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. If the graph $\Gamma$ relative to some its vertex $v$ has an $(F,\lambda)$-propagator with infinite support, then the operator $A_{\Gamma,F}$ has an infinitely supported eigenfunction $f$ corresponding to the eigenvalue $\lambda$. If, in addition, $\Gamma$ does not admit finitely supported $(F,\lambda)$-propagators relative to $v$ (or, in other words, if $v \notin L_{F,\lambda}(\Gamma)$), then $f$ can be chosen to satisfy the additional property that the support of $f$ contains $v$.

Proof. Note that the second assertion of the theorem follows from the first assertion and Theorem 4.2. Indeed, under the assumptions of the second assertion of the theorem, if the first assertion holds, then the operator $A_{\Gamma,F}$ has an infinitely supported eigenfunction $f_1$ corresponding to the eigenvalue $\lambda$, and, since $v \notin L_{F,\lambda}(\Gamma)$, from Theorem 4.2 it follows that the operator $A_{\Gamma,F}$ has an eigenfunction $f_2$ corresponding to the eigenvalue $\lambda$ whose support contains $v$. It is clear that, among the functions $f_1$, $f_2$, $f_1 + f_2$, there is a function with infinite support containing $v$. This function can be taken as $f$ in the second assertion of the theorem.

So, it remains to verify the first assertion of the theorem. Let the graph $\Gamma$ has an infinitely supported $(F,\lambda)$-propagator $p_v$ relative to its vertex $v$ . If the graph $\Gamma$ has also a finitely supported $(F,\lambda)$-propagator relative to $v$, then the difference of $p_v$ and this propagator is, clearly, an infinitely supported eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$. So, we can assume that the raph $\Gamma$ does not admit finitely supported $(F,\lambda)$-propagators relative to $v$. If, for each vertex $u$ of the graph $\Gamma$, $\boldsymbol{\alpha}_u$ denotes the column of the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ corresponding to $u$, then, clearly, the last condition can be reformulated as follows: for an arbitrary finite subset $U\subset V(\Gamma)$, the linear hull of the set $\{\boldsymbol{\alpha}_u: u \in U\}$ in the vector space over $F$ of columns does not contain the column $\boldsymbol{\delta}_v$ (with 1 at the position corresponding to the vertex $v$, and 0’s at the remaining positions). In other words, for an arbitrary finite subset $U\subset V(\Gamma)$, the system of linear equations (over $F$ with unknowns $x_u, u \in U$)

$$\begin{equation*} \sum_{u \in U} x_u\boldsymbol{\alpha}_u = \boldsymbol{\delta}_v, \end{equation*} \notag$$
has no solution in $F$. By the Toeplitz theorem (see Proposition 2.1), this means that there exist a finite subset $U'$ of $V(\Gamma)$ and $b_{u'} \in F$, where $u' \in U'$, such that, on the one hand,
$$$$\sum_{u' \in U'}b_{u'}\alpha_{u',u}=0$$ \tag{5.1}$$
for each vertex $u \in U$, where $\alpha_{u',u}, u' \in U'$, is the element of the column $\boldsymbol{\alpha}_u$ in the row corresponding to the vertex $u'$, but, on the other hand,
$$$$\sum_{u' \in U'}b_{u'}\delta_{u',v} \neq 0,$$ \tag{5.2}$$
where $\delta_{u',v} = 0$ for $u' \neq v$ and $\delta_{v,v} = 1$ if $v \in U'$. By (5.2), we have $v \in U'$ and $b_v \neq 0$, and hance by (5.1) the row corresponding to the vertex $v$ in the $V(\Gamma) \times U$-submatrix of the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ is a linear combination of other rows of this submatrix. Since the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ is symmetric, this also means that the column corresponding to the vertex $v$ in the $U \times V(\Gamma)$-submatrix of the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ is a linear combination of the other columns of this submatrix. Since $U$ is an arbitrary finite subset of $V(\Gamma)$, it follows that each finite subsystem of the system of linear equations (over $F$ with unknowns $y_u$, $u \in V(\Gamma) \setminus \{v\})$
$$$$\sum_{u \in V(\Gamma)\setminus \{v\}} y_u\boldsymbol{\alpha}_u=\boldsymbol{\alpha}_v,$$ \tag{5.3}$$
is solvable in $F$, and hence by the Toeplitz theorem (see Proposition 2.2) this system of linear equations is solvable in $F$.

Let $y_u' \in F, u \in V(\Gamma)\setminus \{v\}$, be some solution in $F$ of the system of linear equations defined by (5.3). Then the function $f \in F^{V(\Gamma)}$, as defined by $f(v) = 1$ and $f(u) = - y_u'$ for all $u \in V(\Gamma)\setminus \{v\}$, is an eigenfunction of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$. To complete the proof of Theorem 5.2 it remains to note that the support of the function $f$ is infinite by Theorem 4.1, since the graph $\Gamma$ relative to the vertex $v$ admits the $(F,\lambda)$-propagator $p_v$.

Since, for a locally finite graph $\Gamma$, a field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$, the condition that the operator $A_{\Gamma,F}$ has an infinitely supported eigenfunction corresponding to the eigenvalue $\lambda$ implies that the graph $\Gamma$ has an infinitely supported $(F,\lambda)$-propagator relative to any vertex from $V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$, an appeal Theorem 5.2 in view of Corollary 4.1 produces the following result.

Corollary 5.1. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. If all $(F,\lambda)$-propagators of the graph $\Gamma$ relative to some vertex from $V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$ are finitely supported, then all $(F,\lambda)$-propagators of the graph $\Gamma$ relative to any vertex from $V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$ are finitely supported, and all $(F,\lambda)$-propagators of the graph $\Gamma$ relative to any fixed vertex from $V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$ have the same restriction to $V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$.

The next theorem gives, for a locally finite graph $\Gamma$, a field $F$ with arbitrary absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$, several characterizations, including those in terms of $(F,\lambda)$-propagators of the graph $\Gamma$, the injectivity of the operator $A_{\Gamma,F} - \lambda E$, or, in other words, conditions under which $\lambda$ is not an eigenvalue of the adjacency operator $A_{\Gamma,F}$.

Theorem 5.3. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then the following conditions (i)–(viii) are equivalent.

(i) $\lambda$ is not an eigenvalue of the adjacency operator $A_{\Gamma,F}$ of the graph $\Gamma$, or, in other words, the operator $A_{\Gamma,F} - \lambda E$ is injective.

(ii) The operator $A_{\Gamma,F} - \lambda E$ is bijective.

(iii) The graph $\Gamma$ has a unique $(F,\lambda)$-propagator relative to some its vertex.

(iv) $L_{F,\lambda}(\Gamma) = V(\Gamma)$.

(v) The graph $\Gamma$ has a unique $(F,\lambda)$-propagator $p_v$ relative to each its vertex $v$, and this propagator has finite support, and $p_{v_1}(v_2) = p_{v_2}(v_1)$ for all $v_1,v_2 \in V(\Gamma)$ (in particular, each vertex of the graph $\Gamma$ is contained only in a finite number of supports of propagators $p_u$, $u \in V(\Gamma)$).

(vi) The matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ has a (symmetric) inverse matrix in the algebra $M^{\mathrm{rcf}}_{V(\Gamma)\times V(\Gamma)}(F)$.

(vii) The operator $A_{\Gamma,F} - \lambda E$ maps the subspace $F^{V(\Gamma)*}$ of the space $F^{V(\Gamma)}$ surjectively onto itself.

(viii) The operator $A_{\Gamma,F} - \lambda E$ maps the subspace $F^{V(\Gamma)*}$ of the space $F^{V(\Gamma)}$ bijectively onto itself.

Proof. It is clear that condition (v) implies condition (iv), and condition (vi) implies condition (v). So, to prove the theorem it suffices to verify that conditions (i), (ii), (iii), (iv), (vi), (vii), (viii) are equivalent. Let us prove this.

Assume that (iv) holds. Then the graph $\Gamma$ has an $(F,\lambda)$-propagator $p_u$ with finite support relative to each its vertex $u$. Let $\mathbf{P}$ be the matrix from $M^{\mathrm{cf}}_{V(\Gamma)\times V(\Gamma)}(F)$ such that, for all $u_1, u_2 \in V(\Gamma)$, the element for the row corresponding to $u_1$ and the column corresponding to $u_2$ is $p_{u_2}(u_1)$. Then $(\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}) \mathbf{P}= \mathbf{E}$, and (since the matrix $\mathbf{A}_{\Gamma,F}$ is symmetric) we also have $\mathbf{P}^\top(\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}) = \mathbf{E}$. Hence (since $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E} \in M^{\mathrm{rcf}}_{V(\Gamma)\times V(\Gamma)}(F)$), we have

$$\begin{equation*} \mathbf{P}=\bigl(\mathbf{P}^\top(\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E})\bigr) \mathbf{P}=\mathbf{P}^\top((\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E})\mathbf{P})= \mathbf{P}^\top. \end{equation*} \notag$$
So, $\mathbf{P}$ is a symmetric matrix which is inverse of the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$ in the algebra $M^{\mathrm{rcf}}_{V(\Gamma)\times V(\Gamma)}(F)$. Now (vi) follows from (iv). Condition (iv) is clear from (vi), and so conditions (iv) and (vi) are equivalent.

Next, it is clear that condition (iv) is equivalent to condition (vii), which is secured by condition (viii). It is also clear that condition (vi) implies conditions (ii), (iii), (viii), and that each of conditions (ii) and (iii) implies condition (i).

So, to complete the proof of Theorem 5.3, it suffices to verify that condition (iv) follows from (i). But this result is also secured by Theorem 4.2.

Remark 5.3. Under either of the equivalent conditions (i)–(viii), the inverse operator of $A_{\Gamma,F} - \lambda E$ is continuous. This follows, for example, from (vi).

For a locally finite graph $\Gamma$, a field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$, a relaxation of the injectivity condition of the operator $A_{\Gamma,F} - \lambda E$ is not only the condition that the operator $A_{\Gamma,F}$ has no eigenfunction corresponding to the eigenvalue $\lambda$ with finite support (and the equivalent conditions (i)–(v) of Theorem 5.1), but also the condition that the operator $A_{\Gamma,F}$ has no eigenfunction corresponding to the eigenvalue $\lambda$, with infinite support (figuratively speaking, the “no-collapse” condition for functions with infinite support). The following theorem shows that the last condition is equivalent to the condition that $F^{V(\Gamma)}$ has no function with infinite support whose image under the operator $A_{\Gamma,F} - \lambda E$ has finite support, and both these conditions are equivalent to a condition naturally formulated in terms of $(F,\lambda)$-propagators of the graph $\Gamma$.

Theorem 5.4. Let $\Gamma$ be a locally finite graph, $F$ be a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then the following conditions (i)– (iii) are equivalent.

(i) The operator $A_{\Gamma,F}$ has no infinitely supported eigenfunctions corresponding to the eigenvalue $\lambda$.

(ii) The operator $A_{\Gamma,F} - \lambda E$ maps each infinitely supported function from $F^{V(\Gamma)}$ to an infinitely supported function.

(iii) The set $S_{F,\lambda}(\Gamma)$ is finite, and the graph $\Gamma$ admits only $(F,\lambda)$-propagators with finite support relative to some (or, by Corollary 5.1, equivalently, to any) vertex from $V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$.

Proof. It is clear that (ii) implies (i). In addition, from Proposition 5.2 and Theorem 5.2 it follows that (i) implies (iii). So, to verify Theorem 5.4 it remains to show that (iii) follows from (ii).

Assume that (iii) holds. If the graph $\Gamma$ is finite, then (ii) holds trivially. So, we can assume that the graph $\Gamma$ is infinite. For each vertex $u \in V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$, let $p_u$ be some $(F,\lambda)$-propagator with finite support of the graph $\Gamma$ relative to $u$. Replacing if necessary the $(F,\lambda)$-propagator $p_u$ for $u \in V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$ by its restriction to the main $\Gamma^2$-connected component of its extended support (see § 4), we can assume without loss of generality that the extended support of $p_u$ is $\Gamma^2$-connected for each vertex $u \in V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$. From Proposition 4.6 it follows that each vertex of the graph $\Gamma$ is contained only in a finite number of extended supports of $(F,\lambda)$-propagators $p_u$, $u \in V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$. (Indeed, if some vertex of the graph $\Gamma$ is contained in infinitely many extended supports of $(F,\lambda)$-propagators $p_u$, $u \in V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$, then, by Proposition 4.6, the operator $A_{\Gamma,F}$ has an infinitely supported eigenfunction corresponding to the eigenvalue $\lambda$. If $f$ is such a function, then, for an arbitrary vertex $u \in V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$, the function $p_u + f$ is an $(F,\lambda)$-propagator with infinite support of the graph $\Gamma$ relative to $u$, which contradicts (iii).)

We let $\mathbf{P}$ denote the matrix from $M^{\mathrm{cf}}_{V(\Gamma)\times V(\Gamma)}(F)$ such that, for $u_1, u_2 \in V(\Gamma)$, the element for the row corresponding to $u_1$ and the column corresponding to $u_2$ is $p_{u_2}(u_1)$ for $u_2 \in V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$ and is $\delta_{u_1,u_2}$ for $u_2 \in S_{F,\lambda}(\Gamma)$ (where $\delta_{u_1,u_2} = 1$, if $u_1 = u_2$, and $\delta_{u_1,u_2} = 0$, if $u_1 \neq u_2$). Since each vertex of the graph $\Gamma$ is contained only in a finite number of supports of the functions $p_u$, $u \in V(\Gamma) \setminus S_{F,\lambda}(\Gamma)$, it follows that $\mathbf{P}$, and, therefore, $\mathbf{P}^\top$, lies in $M^{\mathrm{rcf}}_{V(\Gamma)\times V(\Gamma)}(F)$. Next, for the matrix $\mathbf{P}^\top (\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E})$, its $(V(\Gamma) \setminus S_{F,\lambda}(\Gamma)) \times V(\Gamma)$-submatrix coincides with the $(V(\Gamma) \setminus S_{F,\lambda}(\Gamma)) \times V(\Gamma)$-submatrix of the identity $V(\Gamma) \times V(\Gamma)$-matrix, and its $S_{F,\lambda}(\Gamma) \times V(\Gamma)$-submatrix coincides with the $S_{F,\lambda}(\Gamma) \times V(\Gamma)$-submatrix of the matrix $\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}$. Hence (since $S_{F,\lambda}(\Gamma)$ is finite), for each function $f \in F^{V(\Gamma)}$ with infinite support, for which by $\mathbf{f}$ we denote the column (with elements from $F$) whose rows correspond to $V(\Gamma)$, and the element in the row corresponding to $u \in V(\Gamma)$ is $f(u)$, we find that the column $(\mathbf{P}^\top (\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E}))\mathbf{f}$ has (like $\mathbf{f}$) infinitely many non-zero elements, which by $\mathbf{P}^\top \in M^{\mathrm{rcf}}_{V(\Gamma)\times V(\Gamma)}(F)$ implies that the column $(\mathbf{A}_{\Gamma,F} - \lambda \mathbf{E})\mathbf{f}$ also has infinitely many non-zero elements; the support of the function $(A_{\Gamma,F} - \lambda E)(f)$ is infinite. This completes the proof of (ii).

### § 6. Propagators and sums over paths

In this section, we consider locally finite connected graphs. The results obtained can be applied to connected components of arbitrary locally finite graphs.

Above it was shown that, for a locally finite graph $\Gamma$ and a field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$, a number of interesting properties of the adjacency operator $A_{\Gamma,F}$ (and, in particular, properties of its eigenfunctions) can be naturally formulated in terms of $(F,\lambda)$-propagators of the graph $\Gamma$ for $\lambda \in F$. The expedience of this reformulation is supported by the presence of a construction of propagators (unlike eigenfunctions) involving certain sums over paths of the graph, which is described (for connected graphs) in the present section. Sums over paths and the corresponding generating functions are widely used in the theory of graphs (both finite, see, for example, [12], and infinite, for example, when studying random walks on such graphs; see [13]). In our construction, the propagators are obtained as families of generating functions of certain sums over paths, and, in the case $F = \mathbb{C}$, also as families of analytic extensions of these generating functions. Before proceeding with the construction, we recall that if $\Gamma$ is a locally finite connected graph, $F$ is a field with absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$, then, by assertion 2) of Proposition 3.1 and Theorem 5.2 (or Theorem 5.3), to show that $\lambda$ is an eigenvalue of the adjacency operator $A_{\Gamma,F}$, it suffices to verify that $\Gamma$ admits an $(F',\lambda)$-propagator with infinite support relative to some its vertex for some extension $F'$ of the field $F_0(\lambda)$, where $F_0$ is the prime subfield of the field $F$ with arbitrary absolute value $|\,{\cdot}\,|_{\rm v'}$. The choice of “large” field $F'\supseteq F_0(\lambda)$ can facilitate finding of an infinitely supported $(F',\lambda)$-propagator.

Let us now proceed with the description of the construction of propagators based on certain sums over paths of the graph.

Let $\Gamma$ be a locally finite connected graph, $K$ be a field, and $x$ be an independent variable over $K$. As usual, for arbitrary $v, w \in V(\Gamma)$, by definition, the generating function over $K$ for the number of paths of the graph $\Gamma$ that start at $v$ and end at $w$ is the element of the $K$-algebra $K[[x]]$ of formal power series of $x$ with coefficients from $K$ defined by

$$$$W_{\Gamma,K}(x,v,w) := \sum_{n \in \mathbb{Z}_{\geqslant 0}} (N_{\Gamma}(v,w,n)\cdot 1_K)\ x^n,$$ \tag{6.1}$$
where, for each $n \in \mathbb{Z}_{\geqslant 0}$, $N_{\Gamma}(v,w,n)$ is the number of paths of length $n$ of the graph $\Gamma$ that start at $v$ and end at $w$ (in what follows, depending on the context, we will sometimes drop the unit element $1_K$ of the field $K$ in the notation $m \cdot 1_K$, where $m \in \mathbb{Z}_{\geqslant 1}$). Note that
$$$$W_{\Gamma,K}(x,v,w)=W_{\Gamma,K}(x,w,v).$$ \tag{6.2}$$

The $K$-algebra $K[[x]]$ of formal power series of $x$ with coefficients from $K$ embeds naturally into its quotient field $K((x))$. For an arbitrary $v \in V(\Gamma)$, we define the element $p_{\Gamma,K,x,v} \in K[[x]]^{V(\Gamma)} \subseteq K((x))^{V(\Gamma)}$ by

$$\begin{equation*} p_{\Gamma,K,x,v}(w) := - x W_{\Gamma,K}(x,v,w)\quad \text{for all }\ w \in V(\Gamma). \end{equation*} \notag$$
For $v, w \in V(\Gamma)$, the element $W_{\Gamma,K}(x,v,w)$ of the field $K((x))$ can be interpreted as follows: with each path of the graph $\Gamma$ which starts at $v$ and ends at $w$ one associates the weight from $K[[x]]$ equal to $x$ to the power of the length of this path, after which $W_{\Gamma,K}(x,v,w)$ coincides with the sum (in the sense of [14], Chap IV, $\S\ 5, {\rm n}^\circ 4$), of the weights over all paths of the graph $\Gamma$ which start at $v$ and end at $w$. Using the trivial observation that, for arbitrary $v, w \in V(\Gamma)$ and $n \in \mathbb{Z}_{\geqslant 1}$, in the graph $\Gamma$ a path of length $n$ from $v$ to $w$ is precisely the product (that is, a sequential passing) of a path of length $n-1$ from $v$ to some vertex in $\Gamma(w)$ and a path of length $1$ from this last vertex to the vertex $w$, we have
$$$$N_{\Gamma}(v,w,n) = \sum_{w' \in \Gamma(w)} N_{\Gamma}(v,w',n-1),$$ \tag{6.3}$$
whence follows assertion $1)$ of Proposition 6.1 (see below). Assertion $2)$ of Proposition 6.1 is secured by (6.2), and assertion $3)$ follows since the graph $\Gamma$ is connected.

Proposition 6.1. Let $\Gamma$ be a locally finite connected graph, $K$ be a field, and $x$ be an independent variable over $K$. We equip $K((x))$ with an arbitrary absolute value. Then (in the above notation) the following assertions hold.

$1)$ For $v \in V(\Gamma)$, the function $p_{\Gamma,K,x,v} \in K((x))^{V(\Gamma)}$ is a $(K((x)),1/x)$-propagator of the graph $\Gamma$ relative to the vertex $v$.

$2)$ For $v, v' \in V(\Gamma)$, $p_{\Gamma,K,x,v}(v') = p_{\Gamma,K,x,v'}(v)$.

$3)$ If $K$ is a field of characteristic $0$, then, for $v \in V(\Gamma)$, the support of $p_{\Gamma,K,x,v}$ coincides with $V(\Gamma)$.

Remark 6.1. Assertion 1) of Proposition 6.1 can be looked upon as a sort of a hint to the specificity of the case $\lambda = 0$ when studying $(F,\lambda)$-propagators of locally finite connected graphs $\Gamma$.

Remark 6.2. In the case of a regular connected graph $\Gamma$ of degree $d \in \mathbb{Z}_{\geqslant 1}$ and the quotient field $K((x))$ (with arbitrary absolute value) of the $K$-algebra $K[[x]]$ of formal power series of $x$ with coefficients from an arbitrary field $K$, the generating function

$$\begin{equation*} \widehat{W}_{\Gamma,K}(x,v,w) := \sum_{n \in \mathbb{Z}_{\geqslant 0}} \widehat{N}_{\Gamma}(v,w,n)\cdot 1_K x^n \in K[[x]], \end{equation*} \notag$$
where $v, w \in V(\Gamma)$ and, for $n \in \mathbb{Z}_{\geqslant 0}$, $\widehat{N}_{\Gamma}(v,w,n)$ is the number of the paths $v = u_0,\dotsc,u_n = w$ of the graph $\Gamma$ such that $u_{i-1} \neq u_{i+1}$ for all $0 < i < n$, can be used in the role similar to that in which the generating function
$$\begin{equation*} W_{\Gamma,K}(x,v,w) = \sum_{n \in \mathbb{Z}_{\geqslant 0}} N_{\Gamma}(v,w,n)\cdot 1_K x^n, \end{equation*} \notag$$
(see (6.1)) was used above for construction of values of the propagators $p_{\Gamma,K,x,v}(w)$, $v,w \in V(\Gamma)$. The relation
$$\begin{equation*} \widehat{N}_{\Gamma}(v,w,n)=\sum_{w' \in \Gamma(w)}\widehat{N}_{\Gamma}(v,w',n-1) - (d - 1) \widehat{N}_{\Gamma}(v,w,n-2), \end{equation*} \notag$$
which holds for all $v, w \in V(\Gamma)$ and $n \in \mathbb{Z}_{\geqslant 0}$, except for $v = w \in V(\Gamma)$, $n = 0$ and $v = w \in V(\Gamma)$, $n = 2$ plays the role of (6.3). Using this relation, one can show that, for $v \in V(\Gamma)$, the function $\widehat{p}_{\Gamma,K,x,v} \in K((x))^{V(\Gamma)}$, which is defined by
$$\begin{equation*} \widehat{p}_{\Gamma,K,x,v}(w)=- \frac{x}{1 - x^2}\, \widehat{W}_{\Gamma,K}(x,v,w)\quad \text{for all }\ w \in V(\Gamma), \end{equation*} \notag$$
is a $(K((x)),(1+(d-1)x^2)/x)$-propagator of the graph $\Gamma$ relative to the vertex $v$.

However, even in the case of a regular graph $\Gamma$, this use of $\widehat{W}_{\Gamma,K}(x,v,w)$ in place of $W_{\Gamma,K}(x,v,w)$, plays no principal role, because

$$\begin{equation*} \widehat{W}_{\Gamma,K}(x,v,w)=\frac{1-x^2}{1+(d-1)x^2} \, W_{\Gamma,K}\biggl(\frac{x}{1+(d-1)x^2},v,w\biggr) \end{equation*} \notag$$
(see the end of Chap. 4 in [12], and [15]).

From assertion 3) of Proposition 6.1 in view of Theorem 5.2 (or Theorem 5.3) and assertion 2) of Proposition 3.1 (and also of the equality $K(x) = K(1/x)$, where $1/x$ is also an independent variable over $K$) we have the following result. If $\Gamma$ is an infinite locally finite connected graph and $x$ is an independent variable over $\mathbb{Q}$, then $x$ is an eigenvalue of the adjacency operator $A_{\Gamma,\mathbb{Q}(x)}$ (for an arbitrary absolute value on the field of rational functions $\mathbb{Q}(x)$). This implies (in view of assertion 1) of Proposition 3.1) Theorem 6.1 (see below). Before proceeding with this theorem, we describe the natural context for this result.

Let $\Gamma$ be an infinite locally finite connected graph, $F$ be a field of characteristic $0$ with arbitrary absolute value, and $\mathbb{Q}$ be the prime subfield of the field $F$. As we have already shown, the adjacency operator $A_{\Gamma,\mathbb{Q}(x)}$ has an eigenfunction $f \in \mathbb{Q}(x)^{V(\Gamma)}$ corresponding to the eigenvalue $x$. For each vertex $w$ of the graph $\Gamma$, the element $f(w)$ of the field $\mathbb{Q}(x)$ is uniquely written in the form $f_{1}(w)/f_{2}(w)$, where $f_{1}(w) \in \mathbb{Q}[x]$, $0 \neq f_{2}(w) \in \mathbb{Q}[x]$, the leading coefficient $f_{2}(w)$ is 1, and $\deg (f_{1}(w))$ and $\deg (f_{2}(w))$ are smallest possible for such representations of $f(w)$. Replacing, if necessary, $f$ by its product by $\operatorname{gcd}(f_2(w): w \in V(\Gamma))/\operatorname{gcd}(f_1(w): w \in V(\Gamma)) \in \mathbb{Q}(x) \setminus \{0\}$, it can be assumed that $\operatorname{gcd}(f_1(w): w \in V(\Gamma)) = 1$ and $\operatorname{gcd}(f_2(w)\colon w \in V(\Gamma)) = 1$. If $\lambda$ is a non-zero element of the field $F$ such that $(f_{1}(w))(\lambda) \neq 0$ for some vertex $w \in V(\Gamma)$ and $(f_{2}(w))(\lambda) \neq 0$ for all vertices $w \in V(\Gamma)$ (this holds, for example, if $\lambda$ is transcendental over $\mathbb{Q}$), then the function from $\mathbb{Q}(\lambda)^{V(\Gamma)} \leqslant F^{V(\Gamma)}$, whose value at each vertex $w$ of the graph $\Gamma$ is equal to that assumed by the rational function $f_{1}(w)/f_{2}(w) \in \mathbb{Q}(x)$ for $x = \lambda$ is, clearly, an eigenfunction of the adjacency operator $A_{\Gamma,\mathbb{Q}(\lambda)}$ corresponding to the eigenvalue $\lambda$. In particular, the following result holds.

Theorem 6.1. Let $\Gamma$ be an infinite locally finite connected graph, $F$ be a field of characteristic $0$ with arbitrary absolute value, and $\lambda$ be an element of the field $F$ transcendental over its prime subfield $\mathbb{Q}$. Then $\lambda$ is an eigenvalue of the adjacency operator $A_{\Gamma,\mathbb{Q}(\lambda)}$ (and, therefore, of the adjacency operator $A_{\Gamma,F}$).

Remark 6.3. Under the assumptions of Theorem 6.1, it is clear that the supports of all the eigenfunctions of the adjacency operator $A_{\Gamma,F}$ corresponding to $\lambda$ are infinite, and, in addition, have only infinite connected components. (Indeed, $\lambda$ is an eigenvalue of the operator $A_{\langle X \rangle_{\Gamma},F}$ for any connected component $X$ of the support of any eigenfunction of the operator $A_{\Gamma,F}$, and hence $X$ cannot be finite since $\lambda$ is transcendental over $\mathbb{Q}$.)

Remark 6.4. In general, for a field $F$ of positive characteristic, there is no analogue of Theorem 6.1, see § 8.1.

Let us get back to the study of propagators of locally finite connected graphs. The following result is a consequence of Proposition 6.1 and assertion 2) of Proposition 4.1.

Proposition 6.2. In the notation of Proposition 6.1, let $K_0$ be the prime subfield of the field $K$. Then the graph $\Gamma$ has, relative to any vertex $v$, a $(K_0(x),1/x)$-propagator with extended support lying in the extended support of the $(K((x)),1/x)$-propagator $p_{\Gamma,K,x,v}$ of the graph $\Gamma$ relative to $v$.

Let $\Gamma$ be a locally finite connected graph, $F$ be a field with some absolute value, $F_0$ is the prime subfield of the field $F$, and $x$ be an independent variable over $F$. By Proposition 6.2, for each absolute value on $F(x)$, the graph $\Gamma$ has an $(F(x),1/x)$-propagator $p_v \in F_0(x)^{V(\Gamma)}$ relative to an arbitrary vertex $v$. For each vertex $w$ of the graph $\Gamma$, the element $p_v(w)$ of the field $F_0(x)$ is uniquely written in the form $p_{v,1}(w)/p_{v,2}(w)$, where $p_{v,1}(w) \in F_0[x]$, $0 \neq p_{v,2}(w) \in F_0[x]$, the leading coefficient $p_{v,2}(w)$ is 1, and $\deg (p_{v,1}(w))$ and $\deg (p_{v,2}(w))$ are smallest possible for such representations of $p_v(w)$. If now $\lambda$ is a non-zero element of the field $F$ such that $(p_{v,2}(w))(\lambda) \neq 0$ for all $w \in V(\Gamma)$ (this holds, for example, if $\lambda$ is transcendental over $F_0$), then the function from $F_0(\lambda)^{V(\Gamma)} \leqslant F^{V(\Gamma)}$, whose value at each vertex $w$ of the graph $\Gamma$ is equal to that assumed by the rational function $p_{v,1}(w)/p_{v,2} \in F_0(x)$ for $x = \lambda$ is, clearly, an $(F_0(\lambda),1/\lambda)$-propagator (and, therefore, an $(F,1/\lambda)$-propagator) of the graph $\Gamma$ relative to the vertex $v$.

In particular, we again (see assertion 1) of Corollary 4.2) find that the situation where, for $\lambda \in F$, the graph $\Gamma$ has no $(F,\lambda)$-propagator relative to some its vertex, is possible only in the case of an element $\lambda$ algebraic over $F_0$.

Remark 6.5. From assertion 1) of Proposition 6.1 it follows that if $\Gamma$ is a locally finite connected graph and $F$ is a field of positive characteristic which is complete relative to (a fortiori, non-Archimedean) absolute value $|\,{\cdot}\,|_\mathrm{v}$, then, for $v \in V(\Gamma)$, and $\lambda \in F$ with $|\lambda|_\mathrm{v} > 1$, the function $f: V(\Gamma) \to F$, as defined by

$$\begin{equation*} f(w)=- \lambda^{-1} \sum_{n \in \mathbb{Z}_{\geqslant 0}} (N_{\Gamma}(v,w,n)\cdot 1_F)\ \lambda^{-n}\quad \text{for all }\ w \in V(\Gamma) \end{equation*} \notag$$
(where the sum on the right denotes the $|\,{\cdot}\,|_\mathrm{v}$-limit of the partial sums
$$\begin{equation*} \sum_{0 \leqslant n \leqslant n'} (N_{\Gamma}(v,w,n)\cdot 1_F) \lambda^{-n} \end{equation*} \notag$$
as $n' \to \infty$, $n' \in \mathbb{Z}_{\geqslant 0}$; this limit clearly exists), is an $(F,\lambda)$-propagator of the graph $\Gamma$ relative to the vertex $v$. Since, under these assumptions, the element $\lambda$ is transcendental over any prime subfield of the field $F$, it follows that in our case the existence of an $(F,\lambda)$-propagator in the graph $\Gamma$ relative to $v$ is secured by assertion 1) of Corollary 4.2, and also by Proposition 6.2. Our aim in this remark is to give an “explicit form” of one of such $(F,\lambda)$-propagators.

In the remaining part of the present section, we will apply the above approach to construction of propagators of locally finite connected graphs in the case of the field $F = \mathbb{C}$ with the usual absolute value $|\,{\cdot}\,|$ of a complex number as an absolute value. A special attention will be paid to the graphs with uniformly bounded degrees of vertices. First, we will give in this case some simple corollaries of the above results of this section.

Let $\Gamma$ be a locally finite connected graph and $v \in V(\Gamma)$. Recall that, for $w \in V(\Gamma)$, by $W_{\Gamma,\mathbb{C}}(x,v,w) \in \mathbb{C}((x))$ we denote the generating function over $\mathbb{C}$ for the number of paths of the graph $\Gamma$ that start at $v$ and end at $w$ (see (6.1)). For $w \in V(\Gamma)$ and $0 \neq \lambda \in \mathbb{C}$, we let $W_{\Gamma,\mathbb{C}}(\lambda^{-1},v,w)$ denote the sum of the series obtained from $W_{\Gamma,\mathbb{C}}(x,v,w)$ by substituting $\lambda^{-1}$ for $x$ if this sum is defined (that is, if the resulting series $\sum_{n \in \mathbb{Z}_{\geqslant 0}} N_{\Gamma}(v,w,n) \lambda^{-n}$ converges). For such $\lambda$, we set

$$\begin{equation*} s_{\Gamma,\lambda,v}(w) := -\lambda^{-1} W_{\Gamma,\mathbb{C}}(\lambda^{-1},v,w). \end{equation*} \notag$$
Note that, for $w \in V(\Gamma)$, and $\lambda \in \mathbb{C}$, the number $s_{\Gamma,\lambda,v}(w)$ is defined if and only so is the number $s_{\Gamma,\lambda,w}(v)$; and for such $w$ and $\lambda$, we have
$$\begin{equation*} s_{\Gamma,\lambda,v}(w) = s_{\Gamma,\lambda,w}(v). \end{equation*} \notag$$
We let $D_{\Gamma,v}$ denote the set of $0 \neq \lambda \in \mathbb{C}$ such that $s_{\Gamma,\lambda,v}(w)$ (or, equivalently, $W_{\Gamma,\mathbb{C}}(\lambda^{-1},v,w)$) is defined for all $w \in V(\Gamma)$. Note that in the case where the degrees of vertices of the graph $\Gamma$ are majorized by some natural number $d$, for arbitrary $w \in V(\Gamma)$, $n \in \mathbb{Z}_{\geqslant 0}$ we, clearly, have $N_{\Gamma}(v,w,n) \leqslant d^n$, and hence
$$\begin{equation*} \{c \in \mathbb{C} \colon |c| > d\} \subseteq D_{\Gamma,v}. \end{equation*} \notag$$
Moreover (see Remark 6.7 below), for such a graph $\Gamma$, for arbitrary fixed $v \in V(\Gamma)$, and $\lambda \in \{c \in \mathbb{C} \colon |c| > d\}$, the sum
$$\begin{equation*} \sum_{w \in V(\Gamma)}|s_{\Gamma,\lambda,v}(w)|^2 \end{equation*} \notag$$
is finite. It is clear that, for $|V(\Gamma)| > 1$, if $\lambda \in D_{\Gamma,v}$ and $\lambda \in \mathbb{R}_{>0}$, then $\lambda > 1$.

In the following Propositions 6.3 and 6.4 we collect some simple assertions (some of which will be required in what follows) regarding $s_{\Gamma,\lambda,v}(w)$ qua functions of $w \in V(\Gamma)$ for $\lambda \in D_{\Gamma,v}$. Assertion $1)$ of Proposition 6.3 easily follows from (6.3) (cf. the proof of assertion 1) of Proposition 6.1). Assertions $2)$ and $3)$ of Proposition 6.3 are straightforward since the coefficients $W_{\Gamma}(v,w,x)$ are real and non-negative; the proof of assertion 3) also depends on the inequalities $N_{\Gamma}(v,w,n) \leqslant d^n$ for all $n \in \mathbb{Z}_{\geqslant 0}$.

Proposition 6.3. Let $\Gamma$ be a locally finite connected graph, $v \in V(\Gamma)$ and $\lambda \in D_{\Gamma,v}$ (for example, this condition is met if $\Gamma$ is a connected graph in which the degrees of vertices are majorized by some natural number $d$, $v \in V(\Gamma)$ and $|\lambda| > d$, see above). Then the following results hold.

$1)$ The function $s_{\Gamma,\lambda,v} \in \mathbb{C}^{V(\Gamma)}$ (see above) is a $(\mathbb{C},\lambda)$-propagator of the graph $\Gamma$ relative to the vertex $v$.

$2)$ If $w \in V(\Gamma)$, and $\lambda \in \mathbb{R}$, then $s_{\Gamma,\lambda,v}(w) \in \mathbb{R}$, and $s_{\Gamma,\lambda,v}(w) < 0$ for $\lambda > 0$. If, in addition, $\lambda' \in \mathbb{R}$ and $\lambda' > \lambda > 0$, then $\lambda' \in D_{\Gamma,v}$ and $|s_{\Gamma,\lambda',v}(w)| < |s_{\Gamma,\lambda,v}(w)|$.

$3)$ If the degrees of the vertices of the graph $\Gamma$ are majorized by some natural number $d$, then, for $|\lambda| > d$, we have $|s_{\Gamma,\lambda,v}(w)| \leqslant |s_{\Gamma,|\lambda|,v}(w)| \leqslant 1/(|\lambda| - d)$ for all $w \in V(\Gamma)$.

Let $\Gamma$ be a locally finite connected graph and $v \in V(\Gamma)$. Assume that $\lambda \in D_{\Gamma,v}$ and the function $s_{\Gamma,\lambda,v}$ has infinite support. Then by assertion 1) of Proposition 6.3 and Theorem 5.2 (or Theorem 5.3), the number $\lambda$ is an eigenvalue of the adjacency operator of the graph $\Gamma$. By assertion 2) of Proposition 6.3, for each positive real number $\lambda \in D_{\Gamma,v}$ (in particular, in the case where the degrees of vertices of $\Gamma$ are majorized by some natural number $d$, for $\lambda \in \mathbb{R}_{> d}$), the support of the function $s_{\Gamma,\lambda,v}$ coincides with $V(\Gamma)$. Hence, in the case of an infinite graph $\Gamma$ each such real number $\lambda$ is an eigenvalue of the adjacency operator of the graph $\Gamma$. This conclusion will be refined in assertion 3) of the following Proposition 6.4. The proof of this result depends on assertions 1) and 2) of this proposition.

Proposition 6.4. Let $\Gamma$ be a locally finite connected graph, $v \in V(\Gamma)$ and $\lambda$ be a positive real number from $D_{\Gamma,v}$. (This condition is met, for example, if $\Gamma$ is a connected graph in which the degrees of the vertices are majorized by some natural number $d$, $v \in V(\Gamma)$, and $\lambda \in \mathbb{R}_{> d}$.) Then the following results hold.

1) $\lambda \in D_{\Gamma,u}$ for all $u \in V(\Gamma)$.

2) $s_{\Gamma,\lambda,v}(w_1)/s_{\Gamma,\lambda,v}(w_2) \leqslant \lambda$ for all $\{w_1,w_2\} \in E(\Gamma)$ (recall that by assertion 2) of Proposition $6.3$, $s_{\Gamma,\lambda,v}(w) < 0$ for all $w \in V(\Gamma)$).

3) If $\Gamma$ is an infinite graph, then there exists an eigenfunction $f$ of the adjacency operator $A_{\Gamma, \mathbb{C}}$ of the graph $\Gamma$ corresponding to the eigenvalue $\lambda$ such that $f(v) = 1$, $f(w) \in \mathbb{R}_{>0}$ for all $w \in V(\Gamma)$ and $f(w_1)/f(w_2) \leqslant \lambda$ for all $\{w_1,w_2\} \in E(\Gamma)$ (and hence, in particular, $\lambda ^{-d_{\Gamma}(v,w)} \leqslant f(w) \leqslant \lambda ^{d_{\Gamma}(v,w)}$ for all $w \in V(\Gamma)$).

Proof. For a proof of assertion 1) of the proposition it suffices to note that, for a given $u \in V(\Gamma)$ and arbitrary $w \in V(\Gamma)$ and $n \in \mathbb{Z}_{\geqslant d_{\Gamma}(u,v)}$, we have
$$\begin{equation*} N_{\Gamma}(u,w,n) \leqslant N_{\Gamma}(v,w,n+d_{\Gamma}(u,v)). \end{equation*} \notag$$

For a proof of assertion 2) of the proposition it suffices to take into account that the inequality $N_{\Gamma}(v,w_1,n) \leqslant N_{\Gamma}(v,w_2,n+1)$, where $n \in \mathbb{Z}_{\geqslant 0}$, implies

$$\begin{equation*} \frac{\sum_{n \in \mathbb{Z}_{\geqslant 0}}N_{\Gamma}(v,w_1,n)\lambda^{-n}}{\sum_{n \in \mathbb{Z}_{\geqslant 0}}N_{\Gamma}(v,w_2,n)\lambda^{-n}} \leqslant \frac{\lambda \sum_{n \in \mathbb{Z}_{\geqslant 0}} N_{\Gamma}(v,w_2,n+1)\lambda^{-n-1}}{\sum_{n \in \mathbb{Z}_{\geqslant 0}}N_{\Gamma}(v,w_2,n)\lambda^{-n}} \leqslant \lambda. \end{equation*} \notag$$

Let us verify assertion 3). For arbitrary vertex $u$ of the graph $\Gamma$, consider the function $f_u \in \mathbb{C}^{V(\Gamma)}$ defined by $f_u(w) = s_{\Gamma,\lambda,u}(w)/s_{\Gamma,\lambda,u}(v)$ for all $w \in V(\Gamma)$. We have $\lambda \in D_{\Gamma,u}$ by the already proved assertion 1) of Proposition 6.4, and now from assertions 2) and 1) of Proposition 6.3 it follows that the function $f_u$ is well defined and assumes only real positive values (because the function $s_{\Gamma,\lambda,u}$ assumes real negative values everywhere on $V(\Gamma)$), $f_u(v) = 1$ and $(A_{\Gamma,\mathbb{C}}(f_u))(w) = \lambda f_u(w)$ for all $w \in B_{\Gamma}(v,d_{\Gamma}(u,v) - 1)$. In addition, by the already proved assertion 2) of Proposition 6.4, we have $f_u(w_1)/f_u(w_2) \leqslant \lambda$ for all $\{w_1,w_2\} \in E(\Gamma)$. The connected locally finite graph $\Gamma$ is infinite, the vertex $u$ can be chosen to lie from $v$ at distance exceeding any given natural number. This implies the existence, for any arbitrary natural number $r$, of a function $f_r \in \mathbb{C}^{V(\Gamma)}$ such that $f_r(w) \in \mathbb{R}_{>0}$ for all $w \in V(\Gamma)$, $f_r(v) = 1$, $(A_{\Gamma,\mathbb{C}}(f_r))(w) = \lambda f_r(w)$ for all $w \in B_{\Gamma}(v,r)$ and, finally, $f_r(w_1)/f_r(w_2) \leqslant \lambda$ for all $\{w_1,w_2\} \in E(\Gamma)$. It is clear that the sequence of functions $(f_r)_{r \in \mathbb{Z}_{\geqslant 1}}$ contains a subsequence converging to some function $f$ in the topology of pointwise convergence. Clearly, the limit function features all the properties required in assertion 3) of Proposition 6.4.

Additional (deeper) results can be obtained by using, in effect, analytic extensions of the above generating functions $s_{\Gamma,\lambda,v}$ in the case, where $\Gamma$ is a connected graph in which the degrees of vertices are majorized by some natural number $d$ (and, as before, $F = \mathbb{C}$ with the usual absolute value). It will be shown that the construction that follows is capable of delivering square-summable $(\mathbb{C},\lambda)$-propagators of the graph $\Gamma$ for all $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$.

So, let $\Gamma$ be a connected graph in which the degrees of vertices are majorized by some natural number $d$, and let $F = \mathbb{C}$ with the usual absolute value. Let $l_2(V(\Gamma))\subseteq\mathbb{C}^{V(\Gamma)}$ be the Hilbert space of square-summable functions with inner product

$$\begin{equation*} (f_1,f_2) = \sum_{u \in V(\Gamma)}f_1(u)\overline{f_2(u)}\quad \text{for all }\ f_1, f_2 \in l_2(V(\Gamma)), \end{equation*} \notag$$
where $\overline{f_2(u)}$ for $u \in V(\Gamma)$ is the complex conjugate of $f_2(u)$ (note that the topology of $l_2(V(\Gamma))$ is not induced by that of the topological vector space $\mathbb{C}^{V(\Gamma)}$), and let $\mathcal L (l^2(V(\Gamma)))$ be the set of bounded linear operators on the Hilbert space $l_2(V(\Gamma))$. In what follows, when dealing with operators from $\mathcal L (l^2(V(\Gamma)))$, and, in particular, with their spectra, we will use the terminology of the theory of $C^*$-algebras (the space $\mathcal L (l^2(V(\Gamma)))$ (with natural operations) is an example of such an algebra). So, given an operator $A \in \mathcal L (l^2(V(\Gamma)))$, its resolvent set $r(A)$ consists, by definition, of all $\lambda \in \mathbb{C}$ such that $A - \lambda E$ is a bijection of $l_2(V(\Gamma))$ onto $l_2(V(\Gamma))$ (and hence $(A - \lambda E)^{-1} \in \mathcal L (l^2(V(\Gamma)))$ by the Banach inverse mapping theorem); the operator $(\lambda E - A)^{-1}$ (defined for $\lambda \in r(A)$) is called the resolvent of $A$ at $\lambda$, and the spectrum $\sigma(A)$ is defined as $\mathbb{C} \setminus r(A)$.

The Hilbert space $l_2(V(\Gamma))\subseteq \mathbb{C}^{V(\Gamma)}$ (the topology of $l_2(V(\Gamma))$ is not induced by that of the topological vector space $\mathbb{C}^{V(\Gamma)}$) is $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$-invariant, and the restriction of $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$ to $l_2(V(\Gamma))$, which is denoted by $A^{(l_2)}_{\Gamma,\mathbb{C}}$, is an operator from $\mathcal L (l^2(V(\Gamma)))$.

Remark 6.6. As pointed out in Introduction, in the case of a connected graph $\Gamma$ whose degrees of vertices are uniformly bounded, the operator $A^{(l_2)}_{\Gamma,\mathbb{C}}$ coincides with the operator considered in [4], [5] (and which is called the adjacency operator there). Recall that the adjacency operator in the sense of [4], [5] is defined in the more general case of a countable locally finite graph $\Gamma$ as the $l_2(V(\Gamma))$-closure of the restriction $A^{({\mathrm{alg}})}_{\Gamma,\mathbb{C}}$ to the space of finitely supported functions.

The operator $A^{(l_2)}_{\Gamma,\mathbb{C}}$ has the following properties (cf. [4] and [5]).

a) The norm of $A^{(l_2)}_{\Gamma,\mathbb{C}}$ is at most $d$ (see, for example, Theorem 6.12-A in [16]).

b) $A^{(l_2)}_{\Gamma,\mathbb{C}}$ is self-adjoint (see, for example, § 6.2 in [16]).

c) $\sigma(A^{(l_2)}_{\Gamma,\mathbb{C}})$ is contained in $\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d}$ (this follows from properties a), b), and, for example, from Theorem 2.2.5 in [17]).

The operator $A^{(l_2)}_{\Gamma,\mathbb{C}}$ will be required in the proof of the following theorem. The first assertion of this theorem is immediate from the above property c).

Theorem 6.2. Let $\Gamma$ be a connected graph whose degrees of vertices are majorized by some natural number $d$. Then the following results hold.

$1)$ The set $\mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$ is contained in the resolvent set of the operator $A^{(l_2)}_{\Gamma,\mathbb{C}}$. So, for each $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, we have $R_{\Gamma,d,\lambda} := (A^{(l_2)}_{\Gamma,\mathbb{C}} - \lambda E)^{-1} \in \mathcal L (l^2(V(\Gamma)))$.

$2)$ For arbitrary $v \in V(\Gamma)$, and $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, the function $R_{\Gamma,d,\lambda}(\delta_v) \in \mathbb{C}^{V(\Gamma)}$ is a $(\mathbb{C},\lambda)$-propagator of the graph $\Gamma$ relative to the vertex $v$, and this propagator lies in $l_2(V(\Gamma))$ and is a unique propagator with this property.

$3)$ For arbitrary $v, w \in V(\Gamma)$ and $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, we set

$$\begin{equation*} \widetilde s_{\Gamma,d,\lambda,v}(w) := (R_{\Gamma,d,\lambda}(\delta_v))(w) = (R_{\Gamma,d,\lambda}(\delta_v),\delta_w) \end{equation*} \notag$$
(the inner product of $R_{\Gamma,d,\lambda}(\delta_v)$ and $\delta_w$ in $l_2(V(\Gamma))$). Then, for arbitrary fixed $v, w \in V(\Gamma)$, the function $\widetilde s_{\Gamma,d,\lambda,v}(w)$ of $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$ is an analytic function which coincides on the set $\{\lambda \in \mathbb{C} \colon |\lambda| > d\}$ with $s_{\Gamma,\lambda,v}(w)$, which is considered as a function of $\lambda$.

Proof. From assertion 1) of the theorem (which is secured by property c) of the operator $A^{(l_2)}_{\Gamma,\mathbb{C}}$) it follows that, for arbitrary $v \in V(\Gamma)$, and $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, the function $R_{\Gamma,d,\lambda}(\delta_v) \in \mathbb{C}^{V(\Gamma)}$ is a $(\mathbb{C},\lambda)$-propagator from $l_2(V(\Gamma))$, of the graph $\Gamma$ relative to the vertex $v$; moreover, it is a unique $(\mathbb{C},\lambda)$-propagator from $l_2(V(\Gamma))$ of the graph $\Gamma$ relative to the vertex $v$, because the difference of different $(\mathbb{C},\lambda)$-propagators from $l_2(V(\Gamma))$ of the graph $\Gamma$ relative to the vertex $v$ would be an eigenfunction of the operator $A^{(l_2)}_{\Gamma,\mathbb{C}}$ corresponding to the eigenvalue $\lambda$, but this is impossible since $\lambda \notin \sigma(A^{(l_2)}_{\Gamma,\mathbb{C}})$) (see property c)).

It remains to prove assertion 3) of the theorem. The analyticity of the function $\widetilde s_{\Gamma,d,\lambda,v}(w)$ of $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$ is secured, for example, by Theorem 4.12 in [18]. Let us now show that, for all $v, w \in V(\Gamma)$ and $\lambda \in \mathbb{C}$ with $|\lambda| > d$, we have $\widetilde s_{\Gamma,d,\lambda,v}(w) = s_{\Gamma,\lambda,v}(w)$. For $|\lambda| > d$, by property a) of the operator $A^{(l_2)}_{\Gamma,\mathbb{C}}$, the norm of the operator $\lambda^{-1} A^{(l_2)}_{\Gamma,\mathbb{C}}$ is $<1$, and, therefore, for $|\lambda| > d$, we have (in the sense of convergence of the sum relative to the uniform operator topology on $\mathcal L (l^2(V(\Gamma)))$)

\begin{equation*} \begin{aligned} \, R_{\Gamma,d,\lambda} &=\bigl(A^{(l_2)}_{\Gamma,\mathbb{C}} - \lambda E\bigr)^{-1} = -\lambda^{-1}\bigl(E - \lambda^{-1} A^{(l_2)}_{\Gamma,\mathbb{C}}\bigr)^{-1} \\ &= -\lambda^{-1}\biggl(E+\sum_{n \in \mathbb{Z}_{\geqslant 1}} \bigl(\lambda^{-1} A^{(l_2)}_{\Gamma,\mathbb{C}}\bigr)^n\biggr), \end{aligned} \end{equation*} \notag
which, for all $v, w \in V(\Gamma)$, implies
\begin{equation*} \begin{aligned} \, \widetilde s_{\Gamma,d,\lambda,v}(w) &= (R_{\Gamma,d,\lambda}(\delta_v),\delta_w) = -\lambda^{-1}\biggl((\delta_v,\delta_w) + \biggl(\sum_{n \in \mathbb{Z}_{\geqslant 1}} \lambda^{-n}\bigl(A^{(l_2)}_{\Gamma,\mathbb{C}}\bigr)^n(\delta_v),\delta_w\biggr)\biggr) \\ &= -\lambda^{-1}\biggl((\delta_v,\delta_w) + \sum_{n \in \mathbb{Z}_{\geqslant 1}}\bigl(\lambda^{-n}\bigl(A^{(l_2)}_{\Gamma,\mathbb{C}}\bigr)^n(\delta_v),\delta_w\bigr)\biggr) = s_{\Gamma,\lambda,v}(w). \end{aligned} \end{equation*} \notag

Remark 6.7. Under the hypotheses of Theorem 6.2, by assertions $2)$ and $3)$ of this theorem, for arbitrary fixed $v \in V(\Gamma)$, and $\lambda \in \{c \in \mathbb{C} \colon |c| > d\}$, the function $s_{\Gamma,\lambda,v}(w)\in \mathbb{C}^{V(\Gamma)}$ of $w \in V(\Gamma)$ lies in $l_2(V(\Gamma))$.

Remark 6.8. It is worth pointing out that assertion $2)$ of Theorem 6.2 implies the existence and uniqueness, for an arbitrary connected graph $\Gamma$ for which the degrees of the vertices are unifornly bounded, and arbitrary $v \in V(\Gamma)$, $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, where $d$ is the maximum of the degrees fo the vertices of the graph $\Gamma$, of a square-summable $(\mathbb{C},\lambda)$-propagator $\widetilde s_{\Gamma,d,\lambda,v}$ of the graph $\Gamma$ relative to the vertex $v$ (a sort of a canonical $(\mathbb{C},\lambda)$-propagator $\Gamma$ relative to $v$). (As a corollary, for these $\Gamma$ and $\lambda$, $A_{\Gamma,\mathbb{C}}$ does not contain square-summable eigenfunctions corresponding to the eigenvalue $\lambda$.) Note that the existence part of propagators in this assertion (even in the case of a connected graph $\Gamma$ in which the degrees of vertices are majorized by some natural number $d$, and $F = \mathbb{C}$ with the usual absolute value) is weaker than assertion 2) of Corollary 4.2. However, the advantage of this assertion, for $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$, is that it provides an “explicit form” of the propagator relative to a given arbitrary vertex, and this propagator is unique in $l_2(V(\Gamma))$. It seems tempting to study analytic properties of these canonical propagators $\widetilde s_{\Gamma,d,\lambda,v}$ (qua vector functions of $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$) by employing, for example, the Hilbert relation for $R_{\Gamma,d,\lambda}$ and the equality of $R_{\Gamma,d,\lambda}^2$ to the derivative of $R_{\Gamma,d,\lambda}$ with respect to $\lambda$. Given $w \in V(\Gamma)$, it seems quite interesting, in relation the above results, to study the zeros of $\widetilde s_{\Gamma,d,\lambda,v}(w)$ considered as functions of $\lambda \in \mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$.

Remark 6.9. Another aspect of assertion $3)$ of Theorem 6.2 is worth pointing out. By fixing $d \in \mathbb{Z}_{\geqslant 2}$, varying the connected graphs $\Gamma$ in which the degrees of vertices are majorized by $d$, and also by varying vertices $v, w \in V(\Gamma)$, we get a wide class of functions $s_{\Gamma,\lambda,v}(w)$ of $\lambda$ which are holomorphic on $\{c \in \mathbb{C}\colon |c| > d\}$ and which can be analytically extended to functions $\widetilde s_{\Gamma,d,\lambda,v}(w)$ of $\lambda$ which are holomorphic on $\mathbb{C} \setminus (\mathbb{R}_{\geqslant - d} \cap \mathbb{R}_{\leqslant d})$. This situation can also be looked upon from the following positions: for a connected graph $\Gamma$ in which the degrees of vertices are majorized by $d$, and for arbitrary $v, w \in V(\Gamma)$, the generating series

$$\begin{equation*} W_{\Gamma,\mathbb{C}}(x,v,w) = \sum_{n \in \mathbb{Z}_{\geqslant 0}} N_{\Gamma}(v,w,n) x^n, \end{equation*} \notag$$
which converges absolutely for $x \in \{c \in \mathbb{C} \colon |c| < 1/d\}$, can be naturally “summed” for each $x \in \{c \in \mathbb{C} \colon |c| \geqslant 1/d\} \setminus (\mathbb{R}_{\leqslant - 1/d} \cup \mathbb{R}_{\geqslant 1/d})$ by associating with it the value $-x^{-1} \widetilde s_{\Gamma,d,x^{-1},v}(w)$.

Remark 6.10. In relation to assertion $3)$ of Theorem 6.2, it is worth pointing out the results of § 8.3, where we construct an infinite cubic connected graph $\Gamma$ such that, for any (either of the two) complex non-real root $\lambda_0$ of the polynomial $x^3 + x^2 - 1 \in \mathbb{C}[x]$, the operator $A_{\Gamma,\mathbb{C}} - \lambda_0 E$ is injective, that is, by Theorem 5.3, $\Gamma$ has a unique $(\mathbb{C},\lambda_0)$-propagator $p_v$ relative to each vertex $v$, and $p_v$ has finite support. But then by assertions $2)$ and $3)$ of Theorem 6.2, for arbitrary $v, w \in V(\Gamma)$, we have $p_v(w) = \widetilde s_{\Gamma,3,\lambda_0,v}(w)$. So, for arbitrary vertex $v \in V(\Gamma)$, for all except finitely many vertices $w \in V(\Gamma)$, the function $\widetilde s_{\Gamma,3,\lambda,v}(w)$ of $\lambda$ (which is analytic on $\mathbb{C} \setminus (\mathbb{R}_{\geqslant - 3} \cap \mathbb{R}_{\leqslant 3})$ by assertion $3)$ of Theorem 6.2) vanishes at $\lambda_0$. In addition, by assertion 2) of Proposition 6.3, for arbitrary $v, w \in V(\Gamma)$, the function $\widetilde s_{\Gamma,3,\lambda,v}(w)$ of $\lambda$, which is analytic on $\mathbb{C} \setminus (\mathbb{R}_{\geqslant - 3} \cap \mathbb{R}_{\leqslant 3})$, assumes real negative values everywhere on $\mathbb{R}_{\geqslant 3}$.

### § 7. “Genericity” of surjectivity and “exceptionality” (in the case of an infinite connected graph $\Gamma$ and a field $F$ of characteristic $0$) of injectivity for the operators $A_{\Gamma,F} - \lambda E$

Throughout this section, we assume that $\Gamma$ is a locally finite graph and $F$ is a field with some absolute value $|\,{\cdot}\,|_\mathrm{v}$. Let us recall (see Theorems 5.1 and 5.3) that, for $\lambda \in F$, the surjectivity condition for the operator $A_{\Gamma, F} - \lambda E$ is equivalent to saying that the graph $\Gamma$ has $(F,\lambda)$-propagators relative to all its vertices (that is, $S_{F,\lambda}(\Gamma) = \varnothing$), and the injectivity condition for the operator $A_{\Gamma, F} - \lambda E$ is equivalent to saying that the graph $\Gamma$ has $(F,\lambda)$-propagators with finite supports relative to all its vertices (that is, $L_{F,\lambda}(\Gamma) = V(\Gamma)$).

It is clear that, in the case of a finite graph $\Gamma$, the surjectivity and injectivity conditions of the operator $A_{\Gamma, F} - \lambda E$ are equivalent and are “generic” in the sense that they fail to hold only for $\lambda$’s which are eigenvalues of the adjacency matrix of the graph $\Gamma$ over $F$. Here and in what follows, by “genericity” or, vice versa, “exceptionality” of some property of elements $\lambda$ of a field $F$, we will mean (by projecting the situation to the case where $F$ is $\mathbb{C}$ or, more generally, a field which is not the algebraic extension of its prime subfield) that this property may fail to hold, or, respectively, hold only for certain elements $\lambda$ which are algebraic over the prime subfield.

However, as will be shown in this section, the above results of the present paper imply that the situation changes in the case of an infinite graph $\Gamma$. Even though, for $\lambda \in F$, the presence of $(F,\lambda)$-propagators in an infinite graph $\Gamma$ relative to all its vertices (that is, the surjectivity condition for $A_{\Gamma, F} - \lambda E$) is still “generic” by Corollary 4.2, the more restrictive condition of existence of $(F,\lambda)$-propagators with finite supports in an infinite connected graph $\Gamma$ relative to all its vertices (that is, the injectivity condition for $A_{\Gamma, F} - \lambda E$) is “exceptional” for $\lambda$ in the case of the field $F$ of characteristic $0$ (but may fail to be “exceptional” for $\lambda$ in the case of a field $F$ of positive characteristic, see § 8.1.1). Below (see Propositions 7.3 and 7.2), we will show that, in the case of an infinite connected graph $\Gamma$ and a field $F$ of characteristic $0$, even the condition for existence of an $(F,\lambda)$-propagator with finite support in the graph $\Gamma$ relative to some vertex (that is, condition $L_{F,\lambda}(\Gamma) \neq \varnothing$) is “exceptional” for $\lambda \in F$. So, it will be shown that, for an infinite locally finite connected graph $\Gamma$ and a field $F$ of characteristic $0$, the situation where $S_{F,\lambda}(\Gamma) = \varnothing$, $L_{F,\lambda}(\Gamma) = \varnothing$ and (see Theorems 4.1 and 4.2) the supports of all eigenfunctions of the operator $A_{\Gamma,F}$ corresponding to the eigenvalue $\lambda$ are infinite and their union is the entire set $V(\Gamma)$ are “generic” for $\lambda \in F$. We note, however, that there are infinite locally finite connected graphs $\Gamma$ and fields $F$ of characteristic $0$ with absolute values such that, for some $\lambda \in F$, the equality $S_{F,\lambda}(\Gamma) = V(\Gamma)$ holds (see § 8.5), and, in addition, there are graphs $\Gamma$ and fields $F$ with the same properties such that, for some $\lambda \in F$, the equality $L_{F,\lambda}(\Gamma) = V(\Gamma)$ holds, or, in other words, $\lambda$ is not an eigenvalue of the operator $A_{\Gamma, F}$ (see §§ 8.2, 8.3 and 8.4).

A different situation may well appear in the case of a field $F$ of positive characteristic: for each prime $p \in \mathbb{Z}_{\geqslant 1}$, one may easily give an example of an infinite locally finite connected vertex-symmetric graph $\Gamma$ such that, for each field $F$ of characteristic $p$ with arbitrary absolute value and each $\lambda \in F \setminus \{0\}$, the equality $L_{F,\lambda}(\Gamma) = V(\Gamma)$ holds, or, in other words, $\lambda$ is not an eigenvalue of the operator $A_{\Gamma, F}$ (see § 8.1.1).

So, from Corollary 4.2 of Theorem 4.1 it follows that, for a locally finite graph $\Gamma$ and a field $F$ with absolute value $|\,{\cdot}\,|_\mathrm{v}$, a “generic” situation for $\lambda \in F$ is where the graph $\Gamma$ admits an $(F,\lambda)$-propagator relative to each its vertex, or, in other words, for $\lambda \in F$ an “exceptional” is the condition that the graph $\Gamma$ does not admit an $(F,\lambda)$-propagator relative to some its vertex (that is, $S_{F,\lambda}(\Gamma) \neq \varnothing$). Let us return back to the derivation from Theorem 4.1 of the “exceptionality” for $\lambda \in F$ of the condition $S_{F,\lambda}(\Gamma) \neq \varnothing$. We augment it with one refining observation. So, by Theorem 4.1, for a locally finite graph $\Gamma$, a field $F$, and $\lambda \in F$, the condition $S_{F,\lambda}(\Gamma) \neq \varnothing$ is equivalent to saying that the operator $A_{\Gamma, F}$ has an eigenfunction with finite support corresponding to the eigenvalue $\lambda$. Hence this property is “exceptional” for $\lambda \in F$, because if $X$ is a finite support of some eigenfunction of the operator $A_{\Gamma, F}$ corresponding to the eigenvalue $\lambda$, then, for each finite subset $X'\supseteq X$ of the set $V(\Gamma)$, the element $\lambda$ is an eigenvalue of the adjacency matrix over $F$ of the finite subgraph $\langle X' \rangle_{\Gamma}$ of the graph $\Gamma$ induced by $X'$. It is worth mentioning that the following Proposition 7.1 implies that the condition that the operator $A_{\Gamma, F}$ has an eigenfunction with finite support corresponding to the eigenvalue $\lambda$ is, in general, more restrictive that the condition that $\lambda$ lies in the set of eigenvalues of the adjacency matrix over $F$ of some induced finite subgraph of the graph $\Gamma$.

Proposition 7.1. Let $\Gamma$ be a locally finite graph, $F$ be a field with some absolute value $|\,{\cdot}\,|_\mathrm{v}$, and $\lambda \in F$. Then, for $\varnothing \neq X \subseteq V(\Gamma)$, the following conditions are equivalent.

(i) The operator $A_{\Gamma, F}$ has an eigenfunction corresponding to the eigenvalue $\lambda$ whose support lies in $X$.

(ii) The operator $A_{\langle X \rangle_{\Gamma}, F}$ has an eigenfunction $f$ corresponding to the eigenvalue $\lambda$ such that, for any vertex $u \in \Gamma (X) \setminus X$ (or, equivalently, for any vertex $u \in V(\Gamma) \setminus X$),

$$\begin{equation*} \sum_{u' \in \Gamma(u)\cap X}f(u') = 0. \end{equation*} \notag$$

The proof is clear. If (i) holds and $\widetilde f$ is an eigenfunction of the operator $A_{\Gamma, F}$ corresponding to the eigenvalue $\lambda$ whose support lies in $X$, then (ii) holds, because, clearly, as $f$ one may take $\widetilde f|_X$. Conversely, if (ii) is met, then so is (i), because $\widetilde f \in F^{V(\Gamma)}$, which coincides with $f$ on $X$ and which is $0$ everywhere on $V(\Gamma) \setminus X$ is, clearly, an eigenfunction of the $A_{\Gamma, F}$ which corresponds to the eigenvalue $\lambda$ whose support lies in $X$.

Remark 7.1. For propagators, we have the following analogous result (with a similar proof). Under the assumptions of Proposition 7.1, let $v \in X$. Then the following conditions are equivalent.

(i) The graph $\Gamma$ admits an $(F,\lambda)$-propagator relative to the vertex $v$ whose support lies in $X$.

(ii) The graph $\langle X \rangle_{\Gamma}$ admits an $(F,\lambda)$-propagator $p_v$ relative to the vertex $v$ such that, for any vertex $u \in \Gamma (X) \setminus X$ (or, equivalently, for any vertex $u \in V(\Gamma) \setminus X$) the equality $\sum_{u' \in \Gamma(u)\cap X}p_v(u') = 0$ holds.

Let us now show that if $\Gamma$ is an infinite locally finite connected graph and $F$ is a field of characteristic $0$ with some absolute value $|\,{\cdot}\,|_\mathrm{v}$, then, in contrast to the case of finite graphs, for $\lambda \in F$, the “exceptional” property is the presence of an $(F,\lambda)$-propagator with finite support of the graph $\Gamma$ even relative to some its vertex. By Theorem 5.3, this also implies the “exceptionality” of the injection property of the operator $A_{\Gamma, F} - \lambda E$. Note that the “exceptionality” of the injection property of the operator $A_{\Gamma, F} - \lambda E$ (in the sense that it is possible only for algebraic (over $\mathbb{Q} \subseteq F$) elements $\lambda$) is also secured by Theorem 6.1.

We need the following auxiliary result.

Proposition 7.2. Let $F$ be a field of characteristic $0$ and let $F[x]$ be the algebra of polynomials of a single variable $x$ with coefficients from $F$. Let $\Delta$ be a finite connected graph with $|V(\Delta)| > 1$ and let $\mathbf{A}_{\Delta,F} - x \mathbf{E}$ be the characteristic matrix of its adjacency matrix (over $F$). Then each minor of order $|V(\Delta)| - 1$ of the matrix $\mathbf{A}_{\Delta,F} - x \mathbf{E}$, as considered as an element of $F[x]$, is non-zero (and belongs to \mathbb{Z}[x] \subseteq F[x]$$). As a corollary, the matrix \mathbf{A}_{\Delta,F} - x \mathbf{E}, as considered over the field \mathbb{Q}(x), has the inverse matrix, whose all elements are non-zero. Proof. Without loss of generality we can assume that F = \mathbb{Q}. Assume that the zero element of \mathbb{Q}[x] is the determinant of the matrix \mathbf{A}' obtained from \mathbf{A}_{\Delta,\mathbb{Q}} - x \mathbf{E} after removing the row corresponding to a vertex u of the graph \Delta and the column corresponding to a vertex u' of the graph \Delta. For each i \in \{1,\dotsc,|V(\Delta)|\}, let v_i be the vertex of the graph \Delta corresponding to the ith row (and ith column) of the matrix \mathbf{A}_{\Delta,\mathbb{Q}}. Since u \neq u' (it is clear that all principal minors of the matrix \mathbf{A}_{\Delta,\mathbb{Q}} - x \mathbf{E} are non-zero), we can without loss of generality assume that u = v_1 and u' = v_{|V(\Delta)|}. Let {\boldsymbol \delta}_1 := (1,0,\dotsc,0)^\top (a matrix of size |V(\Delta)| \times 1 over \mathbb{Q}[x]). Since \det (\mathbf{A}_{\Delta,\mathbb{Q}} - x \mathbf{E}) \neq 0 and \det(\mathbf{A}') = 0, the system of linear equations$$ \begin{equation*} (\mathbf{A}_{\Delta,\mathbb{Q}} - x \mathbf{E})(x_1,\dotsc,x_{|V(\Delta)|})^\top = {\boldsymbol \delta}_1 \end{equation*} \notag $$over the field \mathbb{Q}(x) has a unique solution (x'_1,\dotsc,x'_{|V(\Delta)|})^\top, and, in addition, we have x'_{|V(\Delta)|} = 0 (by the Cramer rule)). But then, for each \lambda \in \mathbb{R} such that \det (\mathbf{A}_{\Delta,\mathbb{Q}} - \lambda \mathbf{E}) \neq 0 (the matrix \mathbf{A}_{\Delta,\mathbb{Q}} - \lambda \mathbf{E} is considered as a matrix over \mathbb{R}) the system of linear equations$$ $$(\mathbf{A}_{\Delta,\mathbb{Q}} - \lambda \mathbf{ E})(x_1,\dots,x_{|V(\Delta)|})^\top={\boldsymbol \delta}_1,$$ \tag{7.1} $$considered as a system of linear equations over the field \mathbb{R}, also has a unique solution (x'_{\lambda,1},\dotsc,x'_{\lambda,|V(\Delta)|})^\top, and, in addition, x'_{\lambda,|V(\Delta)|} = 0. Let d be the maximum of the degrees of the vertices in the graph \Delta and \lambda_0 \in \mathbb{R}_{> d}. Then \det (\mathbf{A}_{\Delta,\mathbb{Q}} - \lambda_0 \mathbf{E}) \neq 0. In addition, by assertion 1) of Proposition 6.3, the solution of (7.1), as considered as a system of linear equations over \mathbb{R}, for \lambda = \lambda_0 is (s_1,\dotsc,s_{|V(\Delta)|})^\top, where s_i := s_{\Delta,\lambda_0,v_1}(v_i) for each i \in \{1,\dotsc,|V(\Delta)|\}. Therefore, s_i = x'_{\lambda_0,i} for all i \in \{1,\dotsc,|V(\Delta)|\}. However s_{|V(\Delta)|} = s_{\Delta,\lambda_0,v_1}(v_{|V(\Delta)|}) < 0 by assertion 2) of Proposition 6.3, and x'_{\lambda_0,|V(\Delta)|}=0. This contradiction proves Proposition 7.2. Remark 7.2. For each field F of characteristic p > 0, in general there is no analogue of Proposition 7.2. To see this, it suffices to consider an example of the subgraph generated by a ball of radius 2 of the graph from § 8.1.1 (with the same p). Remark 7.3. Under the additional assumption that \Delta is regular, the conclusion of Proposition 7.2 follows from the Kirchhoff Matrix-Tree Theorem. Corollary 7.1. Let \Delta be a finite connected graph, |V(\Delta)| > 1, and let F be a field of characteristic 0, and \lambda be an element of F which is not an eigenvalue of the adjacency matrix of the graph \Delta (over F), but such that the (F,\lambda)-propagator of the graph \Delta relative to some vertex of the graph \Delta assumes zero value at some vertex of the graph \Delta. Then \lambda is algebraic element of degree < |V(\Delta)| over \mathbb{Q} \subseteq F. Proof. Since \lambda is not an eigenvalue of the adjacency matrix of the graph \Delta, the condition that an (F,\lambda)-propagator of the graph \Delta relative to some vertex u assumes zero value at some vertex u' is equivalent to saying that the determinant of the matrix obtained from \mathbf{A}_{\Delta,F} - \lambda \mathbf{E} after removing the row corresponding to the vertex u of the graph \Delta and the column corresponding to the vertex u' of the graph \Delta is zero. Now the required result follows from Proposition 7.2. Now we can rigorously justify the above thesis. Let \Gamma be an infinite locally finite connected graph and F be a field of characteristic 0 with some absolute value |\,{\cdot}\,|_\mathrm{v}. Proposition 7.3 (see below) and Proposition 7.2 imply the “exceptionality” for \lambda \in F of the fact that the graph \Gamma admits an (F,\lambda)-propagator with finite support relative to some its vertex (that is, the condition L_{F,\lambda}(\Gamma) \neq \varnothing). Even more “exceptional” for \lambda \in F is the injectivity condition for the operator A_{\Gamma, F} - \lambda E, which by Theorem 5.3 is equivalent to saying that the graph \Gamma admits an (F,\lambda)-propagator with finite support relative to each vertex of \Gamma (that is, the condition L_{F,\lambda}(\Gamma) = V(\Gamma)). Proposition 7.3. Let \Gamma be a locally finite graph, F be a field with some absolute value |\,{\cdot}\,|_\mathrm{v} and v \in V(\Gamma). Then, for \lambda \in F, if \Gamma admits an finitely supported (F,\lambda)-propagator relative to v (that is, v \in L_{F,\lambda}(\Gamma)), then there exists a finite subset X\ni v of the set V(\Gamma) such that, for each finite subset X'\supseteq X of the set V(\Gamma), either the determinant of the matrix \mathbf{A}_{\langle X'\rangle_{\Gamma},F} - \lambda \mathbf{E} is zero or all minors of this matrix obtained by removing the row corresponding to the vertex v and the column corresponding to any of the vertices of the set X' \setminus X are zero. ### § 8. Some examples ### 8.1. Let F be an arbitrary field of characteristic p > 0 with arbitrary absolute value. ### 8.1.1. One can easily construct an example of an infinite locally finite connected vertex-symmetric graph \Gamma such that no \lambda \in F \setminus \{0\} is an eigenvalue of the adjacency operator A_{\Gamma,F}. Indeed, let \Delta be an arbitrary infinite locally finite connected vertex-symmetric graph. Let the graph \Gamma be defined by$$ \begin{equation*} \begin{aligned} \, V(\Gamma) &=\bigl\{ v_{u,k} \colon u \in V(\Delta),\,\, k \in \{1,\dots,p\}\bigr\}, \\ E(\Gamma) &=\bigl\{\{v_{u',k'},v_{u'',k''}\} \colon \{u',u''\} \in E(\Delta),\,\, k',k'' \in \{1,\dots,p\}\bigr\}. \end{aligned} \end{equation*} \notag $$We claim that no \lambda \in F \setminus \{0\} is an eigenvalue of the adjacency operator A_{\Gamma,F}. Let \lambda \in F \setminus \{0\}, and let f \in F^{V(\Gamma)} be such that$$ \begin{equation*} \lambda f(v) = \sum_{w \in \Gamma(v)}f(w) \end{equation*} \notag $$for all v \in V(\Gamma). Then, for arbitrary u' \in V(\Delta) and k_1,k_2 \in \{1,\dotsc,p\}, since \Gamma(v_{u',k_1}) = \Gamma(v_{u',k_2}), we have \lambda f(v_{u',k_1}) = \lambda f(v_{u',k_2}), and hence (since \lambda \neq 0) f(v_{u',k_1}) = f(v_{u',k_2}). Therefore, for an arbitrary vertex v_{u,k}, u \in V(\Delta), k \in \{1,\dotsc,p\}, of the graph \Gamma, we have$$ \begin{equation*} f(v_{u,k})=\frac{1}{\lambda} \sum_{u' \in \Delta(u)} \sum_{k' \in \{1,\dots,p\}}f(v_{u',k'}) = \frac{1}{\lambda} \sum_{u' \in \Delta(u)} p\cdot f(v_{u',1})=0. \end{equation*} \notag $$So, f is the identically zero function on V(\Gamma). As a corollary, \lambda is not an eigenvalue of the adjacency operator A_{\Gamma,F}. ### 8.1.2. One can also easily construct an example of an infinite locally finite connected vertex-symmetric graph \Gamma such that 0 \in F is not an eigenvalue of the adjacency operator A_{\Gamma,F}. Let the graph \Gamma be defined by$$ \begin{equation*} \begin{aligned} \, V(\Gamma) &=\bigl\{ v_{i,k} \colon i \in \mathbb{Z}, \,\, k \in \{1,\dots,p\}\bigr\}, \\ E(\Gamma) &=\bigl\{\{v_{2i',k'},v_{2i'+1,k''}\} \colon i' \in \mathbb{Z},\,\, k',k'' \in \{1,\dots,p\}\bigr\} \\ &\qquad\cup \bigl\{\{v_{2i',k'},v_{2i'-1,k'}\} \colon i' \in \mathbb{Z},\,\, k' \in \{1,\dots,p\}\bigr\}. \end{aligned} \end{equation*} \notag $$We claim that 0 \in F is not an eigenvalue of the adjacency operator A_{\Gamma,F}. Let f \in F^{V(\Gamma)} be such that$$ \begin{equation*} (0 \cdot f(v) =)\ 0 = \sum_{w \in \Gamma(v)}f(w) \end{equation*} \notag $$for all v \in V(\Gamma). Let us first show that f(v_{i,k_1}) = f(v_{i,k_2}) for arbitrary i \in \mathbb{Z} and k_1,k_2 \in \{1,\dotsc,p\}. Indeed, for even i, we have$$ \begin{equation*} 0 = \sum_{w \in \Gamma(v_{i-1,k_1})}f(w) = f(v_{i,k_1}) + \sum_{k \in \{1,\dotsc,p\}}f(v_{i-2,k}) \end{equation*} \notag $$and$$ \begin{equation*} 0 = \sum_{w \in \Gamma(v_{i-1,k_2})}f(w) = f(v_{i,k_2}) + \sum_{k \in \{1,\dotsc,p\}}f(v_{i-2,k}), \end{equation*} \notag $$which implies that f(v_{i,k_1}) = f(v_{i,k_2}), and for odd i, we have$$ \begin{equation*} 0=\sum_{w \in \Gamma(v_{i-1,k_2})}f(w)=f(v_{i,k_2})+\sum_{k \in \{1,\dots,p\}}f(v_{i-2,k}) \end{equation*} \notag $$and$$ \begin{equation*} 0 = \sum_{w \in \Gamma(v_{i+1,k_2})}f(w) = f(v_{i,k_2}) + \sum_{k \in \{1,\dotsc,p\}}f(v_{i+2,k}), \end{equation*} \notag $$which implies that f(v_{i,k_1}) = f(v_{i,k_2}) also in this case. Now, for an arbitrary even i \in \mathbb{Z} and arbitrary k \in \{1,\dotsc,p\}, we have$$ \begin{equation*} 0 = \!\!\sum_{w \in \Gamma(v_{i-1,k})}f(w) = f(v_{i,k}) + \sum_{k' \in \{1,\dotsc,p\}}f(v_{i-2,k'}) = f(v_{i,k}) + p \cdot f(v_{i-2,1}) = f(v_{i,k}), \end{equation*} \notag $$and further, for an arbitrary odd i \in \mathbb{Z} and arbitrary k \in \{1,\dotsc,p\},$$ \begin{equation*} 0 = \!\!\sum_{w \in \Gamma(v_{i+1,k})}f(w) = f(v_{i,k}) + \sum_{k' \in \{1,\dotsc,p\}}f(v_{i+2,k'}) = f(v_{i,k}) + p \cdot f(v_{i+2,1}) = f(v_{i,k}). \end{equation*} \notag $$So, f is identically zero on V(\Gamma). As a corollary, 0 is not an eigenvalue of the adjacency operator A_{\Gamma,F}. ### 8.2. Let us now give an example of an infinite cubic connected graph \Gamma such that the roots of the equation x^3 - x^2 - 6x + 2 = 0 in the field \mathbb C (for definiteness, with the usual absolute value) are not eigenvalues of the adjacency operator A_{\Gamma, \mathbb C}. We set$$ \begin{equation*} \begin{aligned} \, V(\Gamma) &=\{u_{i,1},\dots,u_{i,5},v_i \colon i \in \mathbb{Z}\}, \\ E(\Gamma) &=\bigl\{\{u_{i,1},u_{i,2}\}, \{u_{i,1},u_{i,3}\}, \{u_{i,2},u_{i,4}\}, \{u_{i,2},u_{i,5}\}, \{u_{i,3},u_{i,4}\}, \{u_{i,3},u_{i,5}\}, \\ &\qquad \{u_{i,4},u_{i,5}\}\colon i \in \mathbb{Z}\bigr\}\cup \bigl\{\{u_{i,1},v_i\} \colon i \in \mathbb{Z}\bigr\} \cup \bigl\{\{v_i,v_{i+1}\} \colon i \in \mathbb{Z}\bigr\}. \end{aligned} \end{equation*} \notag $$Then \Gamma is an infinite cubic connected graph. Let \lambda be an arbitrary complex root of the equation x^3 - x^2 - 6x + 2 = 0, and let f \in \mathbb{C}^{V(\Gamma)} be such that$$ \begin{equation*} \lambda f(w) = \sum_{w' \in \Gamma(w)} f(w') \end{equation*} \notag $$for each vertex w of the graph \Gamma. Assume that f(v_j) \neq 0 for some j \in \mathbb{Z}. Without loss of generality it can be assumed that f(v_j) = 1 and, in addition, f(u_{j,2}) = f(u_{j,3}) (since \Gamma (u_{j,2}) = \Gamma (u_{j,3}), and \lambda \neq 0) and f(u_{j,4}) = f(u_{j,5}) (because \Gamma admits an automorphism which swaps u_{j,4} and u_{j,5} and stabilizes the remaining vertices of the graph \Gamma). But then$$ \begin{equation*} \begin{aligned} \, \lambda f(u_{j,1}) &=1+2 f(u_{j,2}), \\ \lambda f(u_{j,2}) &=f(u_{j,1})+2 f(u_{j,4}), \\ \lambda f(u_{j,4}) &=2 f(u_{j,2})+f(u_{j,4}), \end{aligned} \end{equation*} \notag $$which implies that (\lambda^3 - \lambda^2 - 6 \lambda + 2) f(u_{j,4}) = 2. This contradicts the choice of \lambda. Hence f(v_i) = 0 for all i \in \mathbb{Z}. For an arbitrary i \in \mathbb{Z}, since f(v_{i-1}) = f(v_i) = f(v_{i+1}) = 0, and \lambda f(v_i) = f(v_{i-1}) + f(v_{i+1}) + f(u_{i,1}), we have f(u_{i,1}) = 0, which, since \lambda f(u_{i,1}) = f(v_i) + f(u_{i,2}) + f(u_{i,3}) and since f(u_{i,2}) = f(u_{i,3}) (this equality holds because \Gamma (u_{i,2}) = \Gamma (u_{i,3}), and \lambda \neq 0), implies that f(u_{i,2}) = f(u_{i,3}) = 0. Now since \lambda f(u_{i,4}) = f(u_{i,2}) + f(u_{i,3}) + f(u_{i,5}) = f(u_{i,5}) and \lambda f(u_{i,5}) = f(u_{i,2}) + f(u_{i,3}) + f(u_{i,4}) = f(u_{i,4}) and since \lambda^2 \neq 1 we have f(u_{i,4}) = f(u_{i,5}) = 0. So, f = 0 and \lambda is not an eigenvalue of the adjacency operator A_{\Gamma,\mathbb C} of the graph \Gamma. Note that the group \operatorname{Aut(}\Gamma) of automorphisms of the graph \Gamma has four orbits on V(\Gamma). Remark 8.1. This example is constructed according to the following scheme. Let \Delta be a finite connected graph, u \in V(\Delta), and \lambda \in \mathbb C. We make the following assumptions. 1) The graph \Delta does not admit (\mathbb C, \lambda)-propagators relative to the vertex u. It is clear that under condition 1) the number \lambda is an eigenvalue of the adjacency matrix of the graph \Delta (considered over \mathbb C). In particular, \lambda is a totally real algebraic integer. Assume in addition that 2) \lambda is a simple (that is, not multiple) eigenvalue of the adjacency matrix of the graph \Delta. By Theorem 4.1, under conditions 1) and 2), the eigenvector of the adjacency matrix of the graph \Delta corresponding to \lambda, as considered as a function from \mathbb C^{V(\Delta)}, assumes non-zero value at the vertex u. (In the above example, V(\Delta) = \{u = u_{1},\dotsc,u_{5}\}, E(\Delta) = \{\{u_{1},u_{2}\}, \{u_{1},u_{3}\}, \{u_{2},u_{4}\}, \{u_{2},u_{5}\}, \{u_{3},u_{4}\}, \{u_{3},u_{5}\}, \{u_{4},u_{5}\}, \lambda is any complex root of the equation x^3 - x^2 - 6x + 2 = 0.) For each i \in \mathbb{Z}, let \Delta _i be the graph which is the image of the graph \Delta. under isomorphism \varphi_i. We define a graph \Gamma by V(\Gamma) = (\bigcup_{i \in \mathbb{Z}} V(\Delta_i)) \cup \{v_i \colon i \in \mathbb{Z}\} (it is assumed that the sets V(\Delta_i), i \in \mathbb{Z}, are pairwise disjoint, and are disjoint from the set \{v_i \colon i \in \mathbb{Z}\}), E(\Gamma) = (\bigcup_{i \in \mathbb{Z}} E(\Delta_i)) \cup \{\{\varphi_i(u),v_i\} \colon i \in \mathbb{Z}\} \cup \{\{v_i,v_{i+1}\} \colon i \in \mathbb{Z}\}. Then \Gamma is an infinite locally finite connected graph such that \lambda is not an eigenvalue of the adjacency operator A_{\Gamma,\mathbb C}. Indeed, if f \in \mathbb C ^{V(\Gamma)} is an eigenfunction of the adjacency operator A_{\Gamma,\mathbb{C}} corresponding to the eigenvalue \lambda, then, then we get a contradiction as follows. In view of 1), we have f(v_i) = 0 for all i \in \mathbb{Z} (f(v_i) \neq 0 for some i \in \mathbb{Z} would imply the existence of a (\mathbb C, \lambda)-propagator of the graph \Delta_i relative \varphi_i(u), which in our case would be the restriction to V(\Delta_i) of the function -f/f(v_i)), which in view of 2) implies that f is zero everywhere on V(\Gamma) (in view of f(v_i) = 0, f(\varphi_i(u)) = \lambda f(v_i) - f(v_{i-1}) - f(v_{i+1}) = 0 and the remark after condition 2), the existence of a non-zero restriction of f to V(\Delta_i) for i \in \mathbb{Z} would contradicts condition 2)). To conclude, it is worth pointing out again that the number \lambda used in this construction scheme is real. ### 8.3. Remarks 8.1 and 6.10 suggest the problem of existence of an infinite locally finite connected graph \Gamma such that some \lambda \in \mathbb{C} \setminus \mathbb{R} is not an eigenvalue of the adjacency operator A_{\Gamma, \mathbb C} (for definiteness, with the usual absolute value on \mathbb C). A positive answer to this question is given by the following example (of an infinite) cubic connected graph \Gamma such that any complex non-real root \lambda of the equation x^3 + x^2 - 1 = 0 (which has two complex conjugate non-real roots and one real root) is not an eigenvalue of the adjacency operator A_{\Gamma, \mathbb C}. (Since the polynomial x^3 + x^2 - 1 = 0 is irreducible over \mathbb{Q}, it follows by Proposition 3.1 that the real root of the equation x^3 + x^2 - 1 = 0 is also not an eigenvalue of A_{\Gamma, \mathbb C}.) Let \Delta be the graph with vertex set$$ \begin{equation*} V(\Delta)=\{u_j \colon 1 \leqslant j \leqslant 6\} \end{equation*} \notag $$and edge set$$ \begin{equation*} E(\Delta) \,{=}\, \bigl\{\{u_1,u_2\},\{u_1,u_3\},\{u_2,u_4\},\{u_2,u_5\}, \{u_3,u_4\}, \{u_3,u_6\},\{u_4,u_5\},\{u_5,u_6\}\bigr\}. \end{equation*} \notag $$The graph \Delta has the property (not quite usual for finite graphs) that, for non-real \lambda, its (\mathbb C, \lambda)-propagator relative to some vertex (namely, the vertex u_1 or u_6) assumes zero value at a different vertex (namely, at the vertex u_6 or u_1, respectively). Let \check \Delta be the graph with vertex set V(\check \Delta) = V(\Delta) \cup \{v,v'\} and edge set E(\check \Delta) = E(\Delta) \cup \{\{v,u_1\},\{v',u_6\}\}. We let U denote the subspace of the vector space \mathbb C^{V(\check \Delta)} of complex-valued functions on V(\check \Delta) consisting of all f \in \mathbb C^{V(\check \Delta)} such that \lambda f(u_j) = \sum _{u \in \check \Delta (u_j)} f(u) for all 1 \leqslant j \leqslant 6. The dimension of U is 2. As a basis for U, we may take the functions f_1 and f_2 defined as follows:$$ \begin{equation*} \begin{gathered} \, f_1(v)=1-2\lambda,\quad f_1(u_1)=-2-\lambda,\quad f_1(u_2)=\lambda,\quad f_1(u_3)=-\frac{1+\lambda}{\lambda}, \\ f_1(u_4)=1,\quad f_1(u_5)=\frac{1+\lambda}{\lambda},\quad f_1(u_6)=0,\quad f_1(v')=0,\quad f_2(w)=f_1(g(w)) \end{gathered} \end{equation*} \notag $$for all w \in V(\check \Delta), where g is the automorphism of the graph \check \Delta stabilizing the vertices u_3, u_4 and swapping the vertices v and v', u_1 and u_6, u_2 and u_5. For further purposes it is worth pointing out that, for an arbitrary c \in \mathbb C, the functions (c/(1-2\lambda))f_1 and (c/(1-2\lambda))f_2 from U are such that$$ \begin{equation*} \begin{alignedat}{2} \frac{c}{1-2\lambda}f_1(v)&=c,&\qquad \frac{c}{1-2\lambda}f_1(u_6)&=0=\frac{c}{1-2\lambda}f_1(v'), \\ \frac{c}{1-2\lambda}f_2(v')&=c,&\qquad \frac{c}{1-2\lambda}f_2(u_1)&=0=\frac{c}{1-2\lambda}f_2(v) \end{alignedat} \end{equation*} \notag $$and$$ \begin{equation*} \lambda \, \frac{c}{1-2\lambda}\, f_k(u_j)=\sum_{u \in \check \Delta (u_j)} \, \frac{c}{1-2\lambda}\, f_k(u) \end{equation*} \notag $$for all 1 \leqslant k \leqslant 2, 1 \leqslant j \leqslant 6. Now let \Gamma be the graph with vertex set$$ \begin{equation*} V(\Gamma)=\{u_{i,j} \colon i \in \mathbb{Z},\, 1 \leqslant j \leqslant 6\} \end{equation*} \notag $$and edge set$$ \begin{equation*} \begin{aligned} \, E(\Gamma) &= \bigl\{\{u_{i,1},u_{i,2}\},\{u_{i,1},u_{i,3}\},\{u_{i,2},u_{i,4}\},\{u_{i,2},u_{i,5}\}, \\ &\qquad\{u_{i,3},u_{i,4}\},\{u_{i,3},u_{i,6}\},\{u_{i,4},u_{i,5}\},\{u_{i,5},u_{i,6}\},\{u_{i,6}, u_{i+1,1}\}\colon i \in \mathbb{Z}\bigr\}. \end{aligned} \end{equation*} \notag $$The graph \Gamma is an infinite cubic connected graph. We claim that the number \lambda is not an eigenvalue of the adjacency operator A_{\Gamma, \mathbb C}. Assume the contrary. Let \widetilde f \in \mathbb C^{V(\Gamma)} be an eigenfunction of the adjacency operator A_{\Gamma, \mathbb C} corresponding to the eigenvalue \lambda. Since \lambda is non-real, the subgraph of the graph \Gamma generated by the support of the function \widetilde f has no finite connected components (since the restriction of \widetilde f to this component would be an eigenvector of the adjacency matrix of the finite graph corresponding to \lambda). In particular, there exists m \in \mathbb{Z} such that \widetilde f(u_{i,1}) \neq 0 \neq \widetilde f(u_{i,6}) for all i \in \mathbb{Z}_{\geqslant m} or for all i \in \mathbb{Z}_{\leqslant m}. Since \Gamma admits an automorphism u_{i,1} \mapsto u_{-i,6}, u_{i,2} \mapsto u_{-i,5}, u_{i,3} \mapsto u_{-i,3}, u_{i,4} \mapsto u_{-i,4}, u_{i,5} \mapsto u_{-i,2}, u_{i,6} \mapsto u_{-i,1}, i \in \mathbb{Z}, and an automorphism u_{i,j} \mapsto u_{i+1,j}, i \in \mathbb{Z}, 1 \leqslant j \leqslant 6, we can without loss of generality assume that m = 0 and \widetilde f(u_{i,1}) \neq 0 \neq \widetilde f(u_{i,6}) for all i \in \mathbb{Z}_{\geqslant 0}. (For further purposes it is only important that \widetilde f can be chosen with non-zero values \widetilde f(u_{0,6}) and \widetilde f(u_{1,1}).) We set X_0 = \{u_{-1,6},u_{0,1},\dotsc,u_{0,6},u_{1,1}\}, X_1 = \{u_{0,6},u_{1,1},\dotsc,u_{1,6},u_{2,1}\}. Each of the subgraphs \langle X_0 \rangle_{\Gamma} and \langle X_1 \rangle_{\Gamma} of the graph \Gamma is, clearly, isomorphic to the graph \check \Delta, which, since there exist functions f_1 and f_2 (see above), implies that there exist functions f^- \in \mathbb C^{X_0} and f^+ \in \mathbb C^{X_1} such that f^-(u_{-1,6}) = \widetilde f(u_{-1,6}), f^-(u_{0,6}) = 0 = f^-(u_{1,1}), \lambda f^-(u_{0,j}) = \sum _{u \in \Gamma (u_{0,j})} f^-(u) for all 1 \leqslant j \leqslant 6, f^+(u_{2,1}) = \widetilde f(u_{2,1}), f^+(u_{0,6}) = 0 = f^+(u_{1,1}), \lambda f^+(u_{1,j}) = \sum _{u \in \Gamma (u_{1,j})} f^+(u) for all 1 \leqslant j \leqslant 6. We extend the functions f^-, f^+ to the functions f_{\mathrm{ext}}^-, f_{\mathrm{ext}}^+ from \mathbb C^{X_0 \cup X_1} by setting f_{\mathrm{ext}}^-(w) = 0 for all w \in X_1 and f_{\mathrm{ext}}^+(w) = 0 for all w \in X_0. Let \widehat f \in \mathbb C^{X_0 \cup X_1}, \widehat f (w) = \widetilde f(w) - f_{\mathrm{ext}}^-(w) - f_{\mathrm{ext}}^+(w) for all w \in X_0 \cup X_1. Then \widehat f(u_{-1,6}) = 0 = \widehat f(u_{2,1}), \widehat f(u_{0,6}) = \widetilde f(u_{0,6}) \neq 0 \neq \widetilde f(u_{1,1}) = \widehat f(u_{1,1}), \widehat f (u_{i,j}) = \sum _{u \in \Gamma (u_{i,j})} \widehat f(u) for all 1\leqslant i \leqslant 2, 1 \leqslant j \leqslant 6. But then the restriction of the function \widehat f to the set X := (X_0 \cup X_1) \setminus \{u_{-1,6},u_{2,1}\} is an eigenfunction of the adjacency matrix of the finite graph \langle X \rangle_{\Gamma} corresponding to the eigenvalue \lambda. However, this is impossible since \lambda is non-real, which completes the proof. Note that the group \operatorname{Aut(}\Gamma) of automorphisms of the graph \Gamma has four orbits on V(\Gamma). ### 8.4. For the graph from § 8.2 and the graphs from Remark 8.1, both the vertex and edge connectivity is 1. A more delicate is an example of an infinite locally finite regular graph for which both the vertex and edge connectivity is >1, but for which not all complex numbers are eigenvalues of the adjacency operator over \mathbb C (for definiteness, with the usual absolute value). Below, we construct an example of an infinite cubic graph \Gamma for which both the vertex and edge connectivity is 2, but 0 is not an eigenvalue of the adjacency operator A_{\Gamma, \mathbb C}. For each i \in \mathbb{Z} we define the graph \Delta_i by$$ \begin{equation*} \begin{aligned} \, V(\Delta_i) &=\{u_{i,1},\dots,u_{i,16}\}, \\ E(\Delta_i) &= \bigl\{\{u_{i,1},u_{i,3}\}, \{u_{i,2},u_{i,4}\}, \{u_{i,3},u_{i,5}\}, \{u_{i,3},u_{i,6}\}, \{u_{i,4},u_{i,7}\}, \{u_{i,4},u_{i,8}\}, \\ &\qquad\{u_{i,5},u_{i,8}\}, \{u_{i,5},u_{i,9}\}, \{u_{i,6},u_{i,7}\}, \{u_{i,6},u_{i,9}\}, \{u_{i,7},u_{i,10}\}, \{u_{i,8},u_{i,11}\}, \\ &\qquad\{u_{i,9},u_{i,12}\}, \{u_{i,10},u_{i,13}\}, \{u_{i,10},u_{i,14}\}, \{u_{i,11},u_{i,12}\}, \{u_{i,11},u_{i,15}\}, \\ &\qquad\{u_{i,12},u_{i,13}\}, \{u_{i,13},u_{i,16}\}, \{u_{i,14},u_{i,15}\}, \{u_{i,14},u_{i,16}\}, \{u_{i,15},u_{i,16}\}\bigr\}. \end{aligned} \end{equation*} \notag $$(It is assumed that V(\Delta_{i'}) \cap V(\Delta_{i''}) = \varnothing for all different i', i'' \in \mathbb{Z}.) Let i \in \mathbb Z, and let f \in \mathbb C^{V(\Delta_i)} be such that$$ $$\sum_{u' \in \Delta_i(u)} f(u')=0$$ \tag{8.1} $$for all u \in V(\Delta_i)\setminus \{u_{i,1},u_{i,2}\}. Setting a := f(u_{i,10}) and b := f(u_{i,14}) and using (8.1), we easily get$$ \begin{equation*} \begin{gathered} \, f(u_{i,1})=f(u_{i,2})=f(u_{i,7})=f(u_{i,8})=f(u_{i,12})=f(u_{i,15})=0, \\ f(u_{i,3})=a - 2b,\qquad f(u_{i,4})=-a+\frac{1}{2}\, b,\qquad f(u_{i,5})=\frac{1}{2}\, b, \qquad f(u_{i,6})=- \frac{1}{2}\, b, \\ f(u_{i,9})=-a+2b,\qquad f(u_{i,11})=a - b,\qquad f(u_{i,13})=-b,\qquad f(u_{i,16})=-a. \end{gathered} \end{equation*} \notag $$Let the graph \Gamma be defined by$$ \begin{equation*} \begin{aligned} \, V(\Gamma) &=\bigcup_{i \in \mathbb{Z}} V(\Delta_i)=\{u_{i,1},\dots,u_{i,16} \colon i \in \mathbb{Z}\}, \\ E(\Gamma) &= \biggl(\bigcup_{i \in \mathbb{Z}} E(\Delta_i)\biggr) \cup \bigl\{\{u_{i,1},u_{i+1,1}\}, \{u_{i,2},u_{i+1,2}\}\colon i \in \mathbb{Z}\bigr\}. \end{aligned} \end{equation*} \notag $$Then \Gamma is an infinite cubic graph for which both the vertex and edge connectivity is 2. We claim that 0 is not an eigenvalue of the adjacency operator of the graph \Gamma. Let \widetilde f \in \mathbb{C}^{V(\Gamma)} be such that$$ $$\sum_{u' \in \Gamma(u)} \widetilde f(u')=0$$ \tag{8.2} $$for all u \in V(\Gamma). For an arbitrary i \in \mathbb{Z}, applying the assertion from the previous paragraph to the restriction of the function \widetilde f to V(\Delta_i), we conclude that$$ $$\widetilde f(u_{i,1})=0=\widetilde f(u_{i,2}).$$ \tag{8.3} $$Next, for an arbitrary i \in \mathbb{Z}, we have$$ \begin{equation*} \Gamma(u_{i,1})=\{u_{i-1,1}, u_{i,3}, u_{i+1,1}\},\qquad \Gamma(u_{i,2})=\{u_{i-1,2}, u_{i,4}, u_{i+1,2}\}, \end{equation*} \notag $$which in view of (8.2) and (8.3) implies that \widetilde f(u_{i,3}) = 0 = \widetilde f(u_{i,4}) for all i \in \mathbb{Z}. But now another appeal to the assertion from the previous paragraph to the restriction of the function \widetilde f to V(\Delta_i), i \in \mathbb{Z}, shows that \widetilde f(u) = 0 for all u \in V(\Delta_i), i \in \mathbb{Z}. So, each function \widetilde f \in \mathbb{C}^{V(\Gamma)} with condition (8.2) is identically 0 on V(\Gamma). Therefore, 0 is not an eigenvalue of the adjacency operator of the graph \Gamma. Note that the group \operatorname{Aut(}\Gamma) of automorphisms of the graph \Gamma has finite number of orbits on V(\Gamma). ### 8.5. One can easily provide examples of infinite locally finite connected vertex-symmetric graphs \Gamma such that S_{F,\lambda}(\Gamma) = V(\Gamma) for a suitable field F with arbitrary absolute value and an appropriate element \lambda \in F. ### 8.5.1. Let F be a field (with arbitrary absolute value) and \lambda \in F be an eigenvalue of the adjacency matrix over F of a finite connected vertex-symmetric graph \Lambda. Let us give an example of an infinite locally finite connected vertex-symmetric graph \Gamma such that S_{F,\lambda}(\Gamma) = V(\Gamma). Let \Delta be an arbitrary infinite locally finite connected vertex-symmetric graph. We set$$ \begin{equation*} \begin{aligned} \, V(\Gamma) &= \bigl\{(v,w,j)\colon v \in V(\Delta),\, w \in V(\Lambda),\, j \in \{1,2,3,4\}\bigr\}, \\ E(\Gamma) &=\bigl\{\{(v_1,w_1,j_1),(v_2,w_2,j_2)\} \colon \{v_1,v_2\} \in E(\Delta),\, w_1,w_2 \in V(\Lambda), \\ &\quad j_1,j_2 \in \{1,2,3,4\}\bigr\} \cup \bigl\{\{(v,w_1,j_1),(v,w_2,j_2)\} \colon v \in V(\Delta), \, w_1,w_2 \in V(\Lambda), \\ &\quad j_1,j_2 \in \{1,2,3,4\},\, |j_1-j_2| \in \{1, 3\}\bigr\} \,{\cup}\, \bigl\{\{(v,w_1,j),(v,w_2,j)\} \colon v \in V(\Delta), \\ &\quad \{w_1,w_2\} \in E(\Lambda),\, j \in \{1,2,3,4\}\bigr\}. \end{aligned} \end{equation*} \notag$It is clear that$\Gamma$is an infinite locally finite connected vertex-symmetric graph. Next, since$\lambda \in F$is an eigenvalue of the adjacency matrix over$F$of the graph$\Lambda$, there is an eigenfunction$f \in F^{V(\Lambda)}$of the adjacency matrix over$F$of the graph$\Lambda$corresponding to the eigenvalue$\lambda$. Let$v_0 \in V(\Delta)$. Let the function$\widetilde f \in F^{V(\Gamma)}$be defined by$\widetilde f((v_0,w,1)) = f(w)$for all$w \in V(\Lambda)$and$\widetilde f((v_0,w,3)) = -f(w)$for all$w \in V(\Lambda)$, and$\widetilde f$is$0$at the remaining vertices of the graph$\Gamma$. It is easily checked that$\widetilde f$is an eigenfunction of the operator$A_{\Gamma,F}$corresponding to the eigenvalue$\lambda$, and$\widetilde f$has finite support. By Theorem 4.1, this implies$S_{F,\lambda}(\Gamma) \neq \varnothing$and hence, since$\Gamma$is vertex-symmetric, we arrive at the required equality$S_{F,\lambda}(\Gamma) = V(\Gamma)$. ### 8.5.2. If$\Gamma$be an arbitrary infinite locally finite connected vertex-symmetric graph with the property that, for$u \in V(\Gamma)$, there exists$v \in V(\Gamma)$such that$\{u,v\} \in E(\Gamma)$and$\Gamma(u) \setminus \{v\} = \Gamma(v) \setminus \{u\}$. Then, as is easy to see, for an arbitrary field$F$(with arbitrary absolute value) we have$S_{F,-1}(\Gamma) = V(\Gamma)$. A similar argument shows that if$\Gamma$is an arbitrary infinite locally finite connected vertex-symmetric graph such that, for each$u \in V(\Gamma)$, there exists$v \in V(\Gamma) \setminus \{u\}$satisfying$\Gamma(u) = \Gamma(v)$, then$S_{F,0}(\Gamma) = V(\Gamma)$for an arbitrary field$F\$ (with arbitrary absolute value).

#### Bibliography

2. D. Cvetković, M. Doob, and H. Sachs, Spectra of graphs. Theory and applications, Pure Appl. Math., 87, Academic Press, Inc., New York–London; DVW, Berlin, 1980
3. A. E. Brouwer and W. H. Haemers, Spectra of graphs, Universitext, Springer, New York, 2012
4. B. Mohar, “The spectrum of an infinite graph”, Linear Algebra Appl., 48 (1982), 245–256
5. B. Mohar and W. Woess, “A survey on spectra of infinite graphs”, Bull. London Math. Soc., 21:3 (1989), 209–234
6. O. Toeplitz, “Über die Auflösung unendlichvieler linearer Gleichungen mit unendlichvielen Unbekannten”, Rend. Circ. Mat. Palermo, 28 (1909), 88–96
7. A. Abian, “Solvability of infinite systems of linear equations”, Arch. Math. (Brno), 12:1 (1976), 43–44
8. Yu. I. Lyubich, “Linear functional analysis”, Functional analysis I, Encyclopaedia Math. Sci., 19, Springer-Verlag, Berlin, 1992, 1–283
9. Shi Qiang Wang, “The inverses of infinite matrices over a field”, (­  ЄЁв. п§.), Beijing Shifan Daxue Xuebao [J. Beijing Normal Univ. (Nat. Sci.)], 29:3 (1993), 327–330
10. V. I. Trofimov, “The existence of nonconstant harmonic functions on infinite vertex-symmetric graphs”, European J. Combin., 19:4 (1998), 519–523
11. The Kourovka notebook. Unsolved problems in group theory, 15th augm. ed., eds. V. D. Mazurov and E. I. Khukhro, Rus. Acad. Sci. Sib. Branch Inst. Math., Novosibirsk, 2002
12. C. D. Godsil, Algebraic combinatorics, Chapman and Hall Math. Ser., Chapman & Hall, New York, 1993
13. W. Woess, Random walks on infinite graphs and groups, Cambridge Tracts in Math., 138, Cambridge Univ. Press, Cambridge, 2000
14. N. Bourbaki, Éléments de mathématique. Livre II: Algèbre, Ch. IV: Polynomes et fractions rationnelles. Ch. V: Corps commutatifs, Actualités Sci. Indust., 1102, Hermann & Cie, Paris, 1950    ; Ch. VI: Groupes et corps ordonnés, Actualités Sci. Indust., 1179, Hermann & Cie, Paris, 1952
15. L. Bartholdi, “Counting paths in graphs”, Enseign. Math. (2), 45:1-2 (1999), 83–131
16. A. E. Taylor, Introduction to functional analysis, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958
17. O. Bratteli and D. W. Robinson, Operator algebras and quantum statistical mechanics, v. 1, Texts Monogr. Phys., Springer-Verlag, New York–Heidelberg–Berlin, 1979
18. M. H. Stone, Linear transformations in Hilbert space and their applications to analysis, Amer. Math. Soc. Colloq. Publ., 15, Amer. Math. Soc., New York, 1932

 Statistics & downloads: Abstract page: 256 Russian version PDF: 2 English version PDF: 9 Russian version HTML: 10 English version HTML: 146 References: 61 First page: 4