On geometric properties of directed vertex-symmetric graphs (Q2488837)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On geometric properties of directed vertex-symmetric graphs |
scientific article |
Statements
On geometric properties of directed vertex-symmetric graphs (English)
0 references
16 May 2006
0 references
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.
0 references
isoperimetric type inequalities
0 references
cones
0 references