Toll convexity

A walk WW between two non-adjacent vertices in a graph GG is called tolled if the first vertex of WW is among vertices from WW adjacent only to the second vertex of WW, and the last vertex of WW is among vertices from WW adjacent only to the second-last vertex of WW. In the resulting interval convexity, a set S⊂V(G)S⊂V(G) is toll convex if for any two non-adjacent vertices x,y∈Sx,y∈S any vertex in a tolled walk between xx and yy is also in SS. The main result of the paper is that a graph is a convex geometry (i.e. satisfies the Minkowski–Krein–Milman property stating that any convex subset is the convex hull of its extreme vertices) with respect to toll convexity if and only if it is an interval graph. Furthermore, some well-known types of invariants are studied with respect to toll convexity, and toll convex sets in three standard graph products are completely described.