The Locally Finite Case (Undirected)

Watkins and Shearer [WS] note that the distance sequences of (undirected) locally finite vertex-transitive graphs may not be log-concave; in fact, even unimodality does not necessarily hold. Log-concavity does hold in the locally finite case, however, under the much more restrictive condition of distance transitivity (or, more generally, distance regularity)[TL] (cf. [BCN, p. 167]).

Watkins and Shearer provide examples of families of vertex-transitive locally finite graphs, both finite and infinite, whose distance sequences are not unimodal. Of particular interest are their examples of infinite locally finite graphs with infinitely many valleys in their distance sequences. One such example ($T_1$ in their paper) is the archimedean tessellation of the plane by regular hexagons and equilateral triangles, of a common sidelength, such that every edge separates a hexagon and a triangle. The distance sequence $\{f(k)\}$ of this graph is given by $f(0)=1$ , $f(1)=4$ , and for $k>1$ ,

$$f(k)=\left\{ \begin{array}{ll} 5k-2 & \textrm{if $k$ is even}\\ 4k+2 & \textrm{if $k$ is odd} \end{array} \right.$$

thus the triple $f(k)$ , $f(k+1)$ , $f(k+2)$ is a valley in the distance sequence of the graph for all even $k\geq 10$ .

Examples such as these motivate the study of pathologies of the distance sequence. See Question 4, Section 6.