Constructions: Directed Graphs

Theorem 4.1   Let $\{d(k)\}$ be any nonincreasing sequence of infinite cardinals. Then $1,d(1),d(2),\dots$ is the out-distance sequence of some vertex-transitive digraph. Furthermore, let $n>0$ and let $\{{g^{+}}(k)\}$ be the out-distance sequence of some vertex-transitive digraph of finite out-degree. Then

$$1,d(1),\dots,d(n),{g^{+}}(n+1),{g^{+}}(n+2),\dots$$

is the out-distance sequence of some vertex-transitive digraph.

In particular then, Theorem 4.1 implies that the out-distance sequences of vertex-transitive digraphs with infinite out-degree are not always unimodal. Theorem 4.1 follows from the following constructions.

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

Let $d$ be an infinite cardinal, and let $n>0$ . We construct $G_{n,d}$ , which has the vertex set $\mathbb{Z}\times[d]$ . There is an edge from $(z_1,\alpha_1)$ to $(z_2,\alpha_2)$ in $G_{n,d}$ when $z_2-z_1=1$ or $z_2-z_1>n$ . So $G_{n,d}$ is acyclic and has out-distance sequence $\{{g^{+}}(k)\}$ satisfying ${g^{+}}(k)=d$ for all $0<k\leq n$ , and ${g^{+}}(n+1)=0$ .

We also define $G_{\infty,d}$ on the same vertex set. There is an edge from $(z_1,\alpha_1)$ to $(z_2,\alpha_2)$ in $G_{\infty,d}$ if and only if $z_2-z_1=1$ . Thus $G_{\infty,d}$ has out-distance sequence $1,d,d,\dots$ .

$1,d(1),d(2),\dots$

Definition 4.2   Let $G_1$ and $G_2$ be digraphs with vertex sets $V_1$ and $V_2$ , respectively. Then the lexicographic product $G_1\bullet G_2$ (cf.[B1, p. 1463]) has vertex set $V_1\times V_2$ ; there is an edge from the vertex $(v_1,v_2)$ to the vertex $(v^{\prime}_1,v^{\prime}_2)$ in $G_1\bullet G_2$ when either $(v_1,v^{\prime}_1)$ is an edge in $G_1$ , or $v_1=v^{\prime}_1$ and $(v_2,v^{\prime}_2)$ is an edge in $G_2$ . On more than two graphs, we define the product recursively: $G_1\bullet \cdots\bullet G_n=(G_1\bullet \cdots\bullet G_{n-1})\bullet G_n$ . (This product is associative.)

Note that if $G$ and $H$ are vertex-transitive, $G\bullet H$ is vertex-transitive.

Observation 4.3   If $G$ and $H$ are acyclic, $G\bullet H$ is acyclic.

Observation 4.4   Let $\{d(k)\}$ be a nonincreasing sequence of infinite cardinals. Let $G_1$ be a vertex-transitive digraph with out-distance sequence $1,d(1),\dots,d(m)$ , and let $G_2$ be a vertex-transitive digraph with $\lvert V(G_2) \rvert \leq d(m)$ and with out-distance sequence $1,{g^{+}}(1),{g^{+}}(2),\dots$ . If $G_1$ is acyclic, then $G_1\bullet G_2$ has out-distance sequence

$$1,d(1),\dots,d(m),{g^{+}}(m+1),{g^{+}}(m+2),\dots.$$

Let $\{d(k)\}$ be a nonincreasing sequence of infinite cardinals; so the sequence must be eventually constant. Thus there exists an $m$ such that $d(i)=d(m)$ for all $i\geq m$ . Then by Observations 4.3 and 4.4,

$$(G_{1,d(1)}\bullet \cdots \bullet G_{m,d(m)})\bullet G_{\infty,d(m+1)}$$

(with $G_{n,d}$ as constructed in 4.1) is vertex-transitive and has out-distance sequence $1,d(1),d(2),\dots$ . This proves the first part of Theorem 4.1.

$1,d(1),\dots ,d(n),{g^{+}}(n+1),{g^{+}}(n+2),\dots$

Let $\{d(k)\}$ as above and let $G$ be a vertex-transitive digraph of finite out-degree with out-distance sequence $\{{g^{+}}(k)\}$ . From Observations 4.3 and 4.4, then,

$$(G_{1,d(1)}\bullet G_{2,d(2)} \bullet \cdots \bullet G_{n,d(n)})\bullet G$$

is a vertex-transitive digraph with out-distance sequence

$$1,d(1),\dots,d(n),{g^{+}}(n+1),{g^{+}}(n+2),\dots.$$

This proves the second part of Theorem 4.1.$\qedsymbol$