Equivalence between Hypergraph Convexities. (11th January 2012) - Malvestuto, Francesco M.; Mezzini, Mauro; Moscarini, Marina
Abstract : LetG be a connected graph onV . A subsetX ofV is all-paths convex (orap -convex) ifX contains each vertex on every path joining two vertices inX and is monophonically convex (orm -convex) ifX contains each vertex on every chordless path joining two vertices inX . First of all, we prove thatap -convexity andm -convexity coincide inG if and only ifG is a tree. Next, in order to generalize this result to a connected hypergraphH, in addition to the hypergraph versions ofap -convexity andm -convexity, we consider canonical convexity (orc -convexity) and simple-path convexity (orsp -convexity) for which it is well known thatm -convexity is finer than bothc -convexity andsp -convexity andsp -convexity is finer thanap -convexity. After provingsp -convexity is coarser thanc -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.