Equivalence between Hypergraph Convexities
2011
Let ? be a connected graph on ?. A subset ? of ? is all-paths convex (or ap-convex) if ? contains each vertex on every path joining two vertices in ? and is monophonically convex (or ?-convex) if ? contains each vertex on every chordless path joining two vertices in ?. First of all, we prove that ap-convexity and ?-convexity coincide in ? if and only if ? is a tree. Next, in order to generalize this result to a connected hypergraph ?, in addition to the hypergraph versions of ap-convexity and ?-convexity, we consider canonical convexity (or ?-convexity) and simple-path convexity (or sp-convexity) for which it is well known that ?-convexity is finer than both ?-convexity and sp-convexity and sp-convexity is finer than ap-convexity. After proving sp-convexity is coarser than ?-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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
26
References
5
Citations
NaN
KQI