Graph with complex eigenvalues The question I am wondering about is: 
Can the discrete Laplacian have complex eigenvalues on a graph?
Clearly, there are two cases where it is obvious that this is impossible.
1.) The graph is finite 
2.) The underlying space is $\ell^2$, since then the discrete Laplacian is self-adjoint.
Thus, my question requires us to look at an infinite graph and a large space.
Hence: Does there exist an infinite graph such that the discrete Laplacian on $\ell^{\infty}$ has complex eigenvalues?
Thank you very much
BTW: My casual use of complex in the above text refers to $\mathbb C \backslash \mathbb R$ 
 A: Take the infinite binary tree $T_2 = (V,E)$, viewed as a bi-infinite `backbone' $B \approx \mathbb Z$ with binary trees dangling off $B$. For every vertex $v \in V$ on the tree, there then is a closest element $\pi(v) \in \mathbb Z$ on the backbone and we write $d(v)$ for the distance from $v$ to $\pi(v)$. We then set $A(v) = \exp(i\theta (\pi(v) + d(v)))$ and check that $\Delta A = \lambda A$ with $\lambda = 2 e^{i\theta} + e^{-i\theta} - 2$.
A: If I understand the question correctly, you may have non-real eigenvalues even if the underlying space is $\ell^2$. It will be the case if the discrete laplacian is not essentially self-adjoint (or, in other words, its deficiency indices are non-zero): in this case every non-real number will be an eigenvalue. To construct such a graph one may take an infinite tree such that the branching number suitably exploses at infinity. For example, Proposition 1.2 in https://arxiv.org/abs/1005.0165 produces an explicit example in $\ell^2$ (and then in $\ell^\infty$ as well).
