Constructions: Undirected Graphs

To demonstrate that Corollary 1.5 completely describes the restrictions on the distance sequences of locally infinite vertex-transitive undirected graphs, we offer constructions for each distance sequence permitted. All graphs in this section are undirected.

$1,d,d,d,\dots$

For a vertex-transitive graph with the distance sequence $\{f(k)\}$ such that $f(k)=d$ for all $k>1$ we need only consider an infinite tree of degree $d$ .

$1,d,e$ $(1\leq e\leq d)$

Define $L(d,e)$ to be the complement of the union of $d$ disjoint copies of the complete graphs $K_{e+1}$ on $e+1$ vertices. $L(d,e)$ is vertex-transitive, has diameter 2, and distance sequence $1,d,e$ .

$1,d,\dots ,d,e$ $(1\leq e\leq d)$

Let $n\geq1$ be an integer, $d$ an infinite cardinal, and $1\leq e\leq d$ . We now consider the case where the diameter is $n\geq 3$ .

We construct a vertex-transitive graph $G$ of degree $d$ , diameter $n$ and distance sequence $f(k)=d$ $(1\leq k\leq n-1)$ , $f(n)=e$ . If $a$ is a cardinal then we use $[a]$ to denote a (standard) set of cardinality $a$ .

Consider the graph $G=C_{2n-4}\times L(d,e)$ where $L(d,e)$ is the graph from Construction 3.2, $C_{2n-4}$ is the $(2n-4)$ -cycle, and $\times$ refers to the Cartesian product. The Cartesian product $G=H_1\times H_2$ of the graphs $H_1$ and $H_2$ is given by $V(G)=V(H_1)\times V(H_2)$ , with $(h_1,h_2)\sim(h_1^\prime,h_2^\prime)$ in $G$ if either $h_1=h_1^\prime$ and $h_2\sim h_2^\prime$ , or $h_2=h_2^\prime$ and $h_1\sim h_1^\prime$ , where $\sim$ refers to adjacency in the appropriate graph (cf.[B1, p. 1463]). Note that if $H_1$ and $H_2$ are vertex-transitive then so is $G$ .

Note that $L(d,e)$ is the complement of $\overline{K_d}\times K_{e+1}$ , so $V(L(d,e))=[d]\times [e+1]$ and $V(G)=[2n-4]\times [d] \times [e+1]$ . There is an edge between $(i,j,k)$ and $(i',j',k')$ in $G$ if either $i=i'$ and $j\neq j'$ , or $i\equiv i'+1\mod(2n-4)$ , $j=j'$ , and $k=k'$ .

$G$ has degree $d$ , so its distance sequence begins with $1,d,\ldots ,d$ . Considering some vertex $v=(i,j,k)$ , we see that the sphere $S(t,v)$ is the set of vertices $w=(i',j',k')$ for which one of the following holds:

1. $t\leq n-2$ , $i'=i\pm t\mod (2n-4),\textrm{ }j'=j, \textrm{ and } k'=k;$
2. $1\leq t\leq n-1$ , $i'=i\pm (t-1)\mod (2n-4) \textrm{ and } j'\neq j;$
3. $2\leq t\leq n$ , $i'=i\pm (t-2)\mod (2n-4), j'=j, \textrm{ and } k'\neq k.$

So $S(n,v)$ is the set of vertices described by condition (3), and $\lvert S(n,v) \rvert =f(n)=e$ .