On all-path convex, gated and Chebyshev sets in graphs

Abstract

We present new characterizations for trees, block graphs, and geodetic graphs using all-path convex, gated and Chebyshev sets. Specifically, we prove that trees are exactly the graphs in which all-path convexity is a convex geometry. Block graphs are characterized as graphs in which all balls are all-path convex (equivalently, gated), and geodetic graphs are exactly those graphs where all balls (equivalently, closed neighborhoods) are Chebyshev. Additionally, we prove that almost all graphs have geodesically convex Chebyshev sets, provide a characterization of bipartite graphs with connected Chebyshev sets, and establish a criterion for graphs with trivial Chebyshev sets in the class of graph joins. Finally, we show that graphs of odd order with maximal number of edges under the Seidel switching operation always have trivial Chebyshev sets.