I made some progress in answering my question.

Let A be the adjacency matrix for a directed graph G that contains n nodes. This is, of course, the general case, and whenever we speak of an undirected graph, that is taken as a shorthand for a directed graph with edges going in both directions.

Let T: R^n --> R^n be the linear transformation performed by A.

Let v in R^n be a vector whose components are natural numbers. So v represents a multiset of nodes in G. Then T(v) also has components that are natural numbers.
I.e., T maps N^n into N^n.

Now let's start by considering the interpretation of an eigenvector w in N^n. Since T(w) is in N^n, it must be that T(w) = q w, for some non-negative rational number q.

Let's take a further special case, where w1 is an eigenvector whose components are 0 or 1. Then T(w1) = k w, for some non-negative integer k.

w1 is the characteristic function for a subgraph G1 of G.

Hence, for any node i in G, T(w1)(i) = the number of predecessors that i has in G1.

Since w1 is an eigenvector with eigenvalue k, we also know that:

For any node i in G, T(w1)(i) = k if i is in G1, else it equals 0.

Putting these two statements together, it follows that:

So T(w1)(i) = the number of predecessors that i has in G1 = k if i is in G1, else 0.

Conclusion: the characteristic function a subgraph G1 is an eigenvector of T, with eigenvalue k, if and only if every node in G1 has exactly k predecessors in G1.

Let G' be the restriction of G to G1.


k = 0. Then for each node i in G1, all of the predecessors are outside of G1. That is to say, G' has no edges at all.

k = 1. Every node in G' has a single predecessor. Then G' is a union of finite cycles and/or infinite linear chains.

k = 2. Every node in G' has exactly two predecessors.

Example: an infinite binary tree, oriented with the edges coming into the root.

Example: an undirected graph that consists of linear chains and finite cycles.

k = 3.

Example: the cube, viewed as an undirected graph.

Example: an infinite hexagonal lattice, viewed as an undirected graph

In the world of undirected graphs, the characteristic functions for any subgraph in one of the following forms is an eigenvector:

* isolated points
* cycles
* infinite chains
* regular polyhedron
* regular infinite lattice
* clique