Connection and separation in hypergraphs

Abstract

In this paper we study various fundamental connectivity properties of hypergraphs from a graph-theoretic perspective, with the emphasis on cut edges, cut vertices, and blocks. We prove a number of new results involving these concepts. In particular, we describe the exact relationship between the block decomposition of a hypergraph and the block decomposition of its incidence graph.

Keywords

• hypergraph
• incidence graph
• walk
• trail
• path
• cycle
• connected hypergraph
• cut edge
• cut vertex
• separating vertex
• block