On All-Path Convex, Gatedand Chebyshev Sets In Graphs

We present new characterizations for trees, block graphs, and geode-tic graphs using all-path convex, gated and Chebyshev sets. Specifically,we prove that trees are exactly the graphs in which all-path convexity isa convex geometry. Block graphs are characterized as graphs in whichall balls are all-path convex (equivalently, gated), and geodetic graphsare exactly those graphs where all balls (equivalently, closed neighbor-hoods) are Chebyshev. Additionally, we prove that almost all graphs havegeodesically convex Chebyshev sets, provide a characterization of bipar-tite graphs with connected Chebyshev sets, and establish a criterion forgraphs with trivial Chebyshev sets in the class of graph joins. Finally, weshow that graphs of odd order with maximal number of edges under theSeidel switching operation always have trivial Chebyshev sets