Equivalence between Hypergraph Convexities. (11th January 2012) - Malvestuto Malvestuto, Francesco M. Francesco M.; Mezzini Mezzini, Mauro Mauro; Moscarini Moscarini, Marina Marina
Abstract : Let G be a connected graph on V . A subset X of V is all-paths convex (or ap -convex) if X contains each vertex on every path joining two vertices in X and is monophonically convex (or m -convex) if X contains each vertex on every chordless path joining two vertices in X . First of all, we prove that ap -convexity and m -convexity coincide in G if and only if G is a tree. Next, in order to generalize this result to a connected hypergraph H, in addition to the hypergraph versions of ap -convexity and m -convexity, we consider canonical convexity (or c -convexity) and simple-path convexity (or sp -convexity) for which it is well known that m -convexity is finer than both c -convexity and sp -convexity and sp -convexity is finer than ap -convexity. After proving sp -convexity is coarser than c -convexity, we characterize the hypergraphs in which each pair of the four convexities above is equivalent. As a result, we obtain a convexity-theoretic characterization of Berge-acyclic hypergraphs and of γ -acyclic hypergraphs.