Abstract: In this paper we consider two natural notions of connectivity for hypergraphs: weak and strong. We prove that the strong vertex connectivity of a connected hypergraph is bounded by its weak edge connectivity, thereby extending a theorem of Whitney from graphs to hypergraphs. We find that while determining a minimum weak vertex cut can be done in polynomial time and is equivalent to finding a minimum vertex cut in the 2-section of the hypergraph in question, determining a minimum strong vertex cut is NP-hard for general hypergraphs. Moreover, the problem of finding minimum strong vertex cuts remains NP-hard when restricted to hypergraphs with maximum edge size at most 3. We also discuss the relationship between strong vertex connectivity and the minimum transversal problem for hypergraphs, showing that there are classes of hypergraphs for which one of the problems is NP-hard while the other can be solved in polynomial time.
Recommendations
Cited in
(36)- Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
- Sufficient conditions for maximally edge-connected hypergraphs
- Relating hypergraph parameters of generalized power graphs
- Edge-connectivity in hypergraphs
- Connectivity of Cartesian product of hypergraphs
- On the sizes of \((k, l)\)-edge-maximal \(r\)-uniform hypergraphs
- On the sizes of \(k\)-edge-maximal \(r\)-uniform hypergraphs
- Finding a minimal spanning hypertree of a weighted hypergraph
- Degree sequence conditions for maximally edge-connected and super edge-connected hypergraphs
- The geometry connectivity of hypergraphs
- On the sizes of vertex-k-maximal r-uniform hypergraphs
- Maximally connected \(p\)-partite uniform hypergraphs
- High connectivity keeping sets in graphs and digraphs
- Investigating the connectivity of hypergraphs via their spectra
- Bridges in Highly Connected Graphs
- scientific article; zbMATH DE number 5534553 (Why is no real title available?)
- Vector connectivity in graphs
- The cutwidth and the vertex separation number of hypergraphs and their König’s representations
- Whitney's connectivity inequalities for directed hypergraphs
- Minimally connected \(r\)-uniform hypergraphs
- The weak hyperedge tenacity of the hypercycles
- Connection and separation in hypergraphs
- On \(c\)-spaces and hypergraphs
- Finding the shortest path for a hypergraph
- The edge‐connectivity of vertex‐transitive hypergraphs
- Extending simplicial complexes: topological and combinatorial properties
- Connectoids. I: A universal end space theory
- Results on the vertex connectivity of hypergraphs
- On forcibly k-connected uniform hypergraphic sequences
- Super edge-connectivity of transitive hypergraphs
- A survey on the vertex-(edge-)k-maximal graphs and the k-vertex-(edge-)connected graphs with redundant subgraphs
- On the sizes of bi-k-edge-maximal r-uniform hypergraphs
- Convex geometries yielded by transit functions
- Existential closure in uniform hypergraphs
- Extending graph burning to hypergraphs
- Cut vertex transit functions of hypergraphs
This page was built for publication: Connectivity in hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4569602)
