Generalized chordality, vertex separators and hyperbolicity on graphs (Q2333406)

This paper studies the relationship between several graph concepts including generalized chordality, vertex separators, and hyperbolicity. It is shown that each minimal vertex separator in a \((k,1)\)-chordal graph has a uniformly-bounded diameter. If each minimal vertex separator in a uniform graph has a uniformly-bounded diameter, then it is a hyperbolic graph. It is shown that a graph satisfies bottleneck property if and only if it is \(\varepsilon\)-densely \((k,m)\)-choral. If a graph is \((k,1)\)-chordal then it satisfies bottleneck property. A generalized concept of neighbor separators is introduced to extend that of the vertex separators. On the basis of neighbor obstructors, graphs with stable geodesics between vertices are characterized. It is further shown that geodesics are stable if and only if a graph is \(\varepsilon\)-densely \((k,m)\)-choral on the bigons.