Finding necessary/sufficient conditions for when a directed graph's geodesic function is unbounded.

51 Views Asked by At

Given any directed graph $G=(V,R)$ where $R\subseteq V\times V$ is an arbitrary binary relation, we have under the standard definition of distance in an unweighted digraph that $d_G:V\times V\to \mathbb{N}\cup \{\infty\}$ is defined so that for any $u,v\in V$ we have:

$$d_{G}(u,v)=\begin{cases}\text{ The length of the shortest walk from }u\text{ to }v&\text{ if }(u,v)\in R^{+}\\\infty&\text{ if }(u,v)\not\in R^{+}\end{cases}$$

Where $R^{+}$ is the transitive closure of $R$ so that if $\circ$ denotes relational composition and one writes $R^n=\underbrace{R\circ R\circ R\circ \cdots \circ R}_{n\text{ times }}$ then we can explicitly define the transitive closure as $R^{+}=\bigcup_{n=1}^{\infty}R^n$.

Now if there is some $N\in \mathbb{N}$ for which $d_{G}(u,v)\leq N$ for every $(u,v)\in R^{+}$ we call $G$ bounded. Therefore with all this in mind, what are some other equivalent conditions we can list to determine if $G$ is bounded? In particular something that refers to internal properties of the digraph $G$. That is not just a rephrasing of the above definition for when a digraph is bounded using alternate notation or something of that nature. I can see necessary conditions, myself though nothing equivalent.

For instance, it's clear that if any digraph $G$ is not bounded then there exists an infinite strictly increasing sequence of integers: $0<d_G(u_1,v_1)<d_G(u_2,v_2)<d_G(u_3,v_3)<\cdots$ therefore for any $N\in \mathbb{N}$ there is some $(x,y)\in R^{+}$ with $d_G(x,y)>N\implies N+1\leq d_G(x,y)$ so there must exist either a directed cycle if $x=y$ of length greater then or equal to $N+1$ or a directed path of length greater then or equal to $N+1$ if $x\neq y$ though in either of these scenarios said directed path/cycle will always contain in it some other directed path of length $N$. Meaning that if $G$ is not bounded then it contains an infinite number of directed paths of length $n$ for every natural number $n\in \mathbb{N}$. However this by itself is not a sufficient condition for a digraph not to be bounded, even though it is necessary. For instance consider the digraph $H$ defined as follows:

$$H=\left(\mathbb{Q},\left\{(p,q)\in \mathbb{Q}\times \mathbb{Q}:p<q\right\}\right)$$

Now since $P=(\mathbb{Q},<)$ is dense, for any $u,v\in V(H)=\mathbb{Q}$ we can always find $q_1,q_2,\ldots q_{n-1}\in \mathbb{Q}$ for any integer $n>1$ with $u<q_1<q_2<q_3<\ldots <q_{n-1}<v$ so letting $u=q_0$ and $v=q_n$ we get that $\small \bigwedge_{k=1}^n[q_{k-1}<q_k]\iff \bigwedge_{k=1}^n[(q_{k-1},q_k)\in E(H)]\iff \{(q_0,q_1),(q_1,q_2),(q_2,q_3)..,(q_{n-1},q_n)\}\subseteq E(H)$ therefore $(u,q_1,q_2,q_3,\ldots q_{n-1},v)$ is a directed path of length $n$ in $H$ now since we can repeat this construction a countably infinite number of times by adding $\pm \epsilon\in \mathbb{Q}$ to each $q_k$ for $1\leq k\leq n-1$ such that our previous inequality holds. We see there are an infinite number of paths from $u$ to $v$ of length $n$ in $H$ for all $n\in \mathbb{N}$, yet by our definition of $H$ we get $d_{H}(x,y)=1$ for all $(x,y)\in E(H)^{+}$ since $(x,y)\in E(H)^{+}\iff [x<y]\land [x,y\in \mathbb{Q}]\iff (x,y)\in E(H)\implies d_{H}(x,y)=1$. Thus clearly the digraph $H$ is bounded, while as I noted it satisfies the property I mentioned of containing an infinite number of paths of length $n$ for every $n\in \mathbb{N}$. Meaning that this alone isn't enough to characterize which digraphs are not bounded, though as shown earlier it is a necessary condition for a digraph to be not bounded. So to reiterate are there any "nice" or easily enumerable conditions that would tell me if a directed graph was not bounded without forcing me to define a geodesic function like in the original characterization?