Convex geometries over induced paths with bounded length

2022/03/10 by Gutierrez, Marisa, Protti, Fábio, Tondato, Silvia B.
#05C76 #05C85 #52A37 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2203.05588

Abstract

Graph convexity spaces have been studied in many contexts. In particular, some studies are devoted to determine if a graph equipped with a convexity space is a \em convex geometry. It is well known that chordal and Ptolemaic graphs can be characterized as convex geometries with respect to the geodesic and monophonic convexities, respectively. Weak polarizable graphs, interval graphs, and proper interval graphs can also be characterized in this way. In this paper we introduce the notion of \em l^k-convexity, a natural restriction of the monophonic convexity. Let G be a graph and k≥ 2 an integer. A subset S⊆ V(G) is l^k-convex if and only if for any pair of vertices x,y of S, each induced path of length \em at most k connecting x and y is completely contained in the subgraph induced by S. The \em l^k-convexity consists of all l^k-convex subsets of G. In this work, we characterize \em l^k-convex geometries (graphs that are convex geometries with respect to the l^k-convexity) for k∈\2,3\. We show that a graph G is an l²-convex geometry if and only if G is a chordal P₄-free graph, and an l³-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 l³-convex geometries is the first example of a non-hereditary class of convex geometries.

Related

• Characterizations of graph classes via convex geometries: a survey
• A general framework for path convexities
• Cycle convexity and the tunnel number of links
• Geometric graphs on convex point sets
• Half-space separation in monophonic convexity