Convex geometries over induced paths with bounded length

Abstract

In this paper we introduce the notion of lk-convexity, a natural restriction of the monophonic convexity. Let G be a graph and k≥2 an integer. A subset S⊆V(G) is lk-convex if and only if for any pair of vertices x,y of S, each induced path of length at most k connecting x and y is completely contained in the subgraph induced by S. The lk-convexity consists of all lk-convex subsets of G. In this work, we characterize lk-convex geometries (graphs that are convex geometries with respect to the lk-convexity) for k∈{2,3}. We show that a graph G is an l2-convex geometry if and only if G is a chordal P4-free graph, and an l3-convex geometry if and only if G is a chordal graph with diameter at most three such that its induced gems satisfy a special “solving” property. As far as the authors know, the class of l3-convex geometries is the first example of a non-hereditary class of convex geometries.