TY - JOUR
A2 - Isaak, G.
A2 - Tarhio, J.
AU - Malvestuto, Francesco M.
AU - Mezzini, Mauro
AU - Moscarini, Marina
PY - 2011
DA - 2012/01/15
TI - Equivalence between Hypergraph Convexities
SP - 806193
VL - 2011
AB - 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.
SN - null
UR - https://doi.org/10.5402/2011/806193
DO - 10.5402/2011/806193
JF - ISRN Discrete Mathematics
PB - International Scholarly Research Network
KW -
ER -