On geometric properties of directed vertex-symmetric graphs (Q2488837)

Let \(\Gamma\) denote a directed locally finite vertex-symmetric graph such that the underlying graph \(\overline\Gamma\) is connected. Let \(\alpha_\Gamma(n)\) be the smallest integer such that there exists a directed path of \(\Gamma\) of length \(\alpha_\Gamma(n)+1\) whose initial and terminal vertices are at distance \(n+1\) in the underlying graph \(\overline\Gamma\). The author proves that, in the case \(\Gamma\) is infinite, there is a positive integer \(k\), depending only on \(\min\{\deg^+ (\Gamma),\deg^-(\Gamma)\}\), such that \(\alpha_\Gamma(n)\leq kn^2\) for all positive integers \(n\). An analogous result is proved in the case that \(\Gamma\) is finite and \(n<\frac{\text{diam}(\overline\Gamma)}{2} +1\). The proofs are based on isoperimetric type inequalities for cones in directed vertex-symmetric graphs.