Expansion in symmetric graphs

If \(f(k)\) is the number of vertices at distance \(k\) from some vertex \(x\) in a graph, then the sequence {\( f(k) \)} is the "distance sequence" of the graph at \(x\). In a vertex transitive graph (e.g., a Cayley graph) the sequence is the same at all vertices, and so we speak simply of the distance sequence of the graph.

We will discuss what is known about the behavior of such distance sequences for vertex-transitive graphs of finite degree, and then show how the distance sequences can be completely characterized for graphs of infinite degree. We'll also prove some results about directed graphs of infinite out-degree, and consider some interesting open problems connected to these results.

Wesley Pegden