Equivalence between hypergraph convexities (Q410668): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 6 users not shown) | |||
Property / author | |||
Property / author: Francesco Mario Malvestuto / rank | |||
Property / author | |||
Property / author: Francesco Mario Malvestuto / rank | |||
Normal rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C65 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 52A20 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6021227 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(c\)-convexity | |||
Property / zbMATH Keywords: \(c\)-convexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
sp-convexity | |||
Property / zbMATH Keywords: sp-convexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
ap-convexity | |||
Property / zbMATH Keywords: ap-convexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(m\)-convexity | |||
Property / zbMATH Keywords: \(m\)-convexity / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q58689730 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.5402/2011/806193 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2124914243 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convexity in Graphs and Hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Canonical and monophonic convexities in hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convex sets in graphs. II: Minimal path convexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The All-Paths Transit Function of a Graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convex sets in a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Degrees of acyclicity for hypergraphs and relational database schemes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of acyclic conjunctive queries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A comparison of structural CSP decomposition methods / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4089657 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4382293 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5572939 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Characterizations of totally balanced matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4871755 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Desirability of Acyclic Database Schemes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On hypergraph acyclicity and graph chordality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3315548 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal decomposition by clique separators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A fast algorithm for query optimization in universal-relation databases / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Decomposition of a hypergraph by partial-edge separators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On triangle path convexity in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithmic Aspects of Monophonic Convexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pruning processes and a new characterization of convex geometries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5506514 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Connections in acyclic hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing simple-path convex hulls in hypergraphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:45, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equivalence between hypergraph convexities |
scientific article |
Statements
Equivalence between hypergraph convexities (English)
0 references
3 April 2012
0 references
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.
0 references
\(c\)-convexity
0 references
sp-convexity
0 references
ap-convexity
0 references
\(m\)-convexity
0 references