Equivalence between hypergraph convexities

Summary: Let \(G\) be a connected graph on \(V\). A subset \(X\) of \(V\) is all-paths convex (or a p -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 \(\gamma\)-acyclic hypergraphs.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Equivalence between hypergraph convexities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q410668)