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 ismonophonically convex orm-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.

Francesco, M., Mezzini, M., Moscarini, M. (2011). Equivalence between hypergraph convexities. ISRN DISCRETE MATHEMATICS, 2011 [10.5402/2011/806193].

### Equivalence between hypergraph convexities

#### Abstract

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 ismonophonically convex orm-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.
##### Scheda breve Scheda completa Scheda completa (DC)
2011
Francesco, M., Mezzini, M., Moscarini, M. (2011). Equivalence between hypergraph convexities. ISRN DISCRETE MATHEMATICS, 2011 [10.5402/2011/806193].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11590/138375`
##### Citazioni
• ND
• ND
• ND