Equivalence between Hypergraph Convexities. (11th January 2012)

• Record Type: Journal Article
• Authors: Malvestuto, Francesco M.; Mezzini, Mauro; Moscarini, Marina
• Other Names: Isaak G. Academic Editor.; Tarhio J. Academic Editor.
• Is Part Of: ISRN discrete mathematics. Volume 2011(2011)
• Publication Date: 2012-01-11
• Subjects: Discrete mathematics -- Periodicals; Computer science -- Mathematics; Computer science -- Mathematics; Periodicals; 511.1
• DOI: 10.5402/2011/806193
• Languages: English
• ISSNs: 2090-7788

Abstract

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.