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

    Identifiers