Minimally Connected Hypergraphs
From MaRDI portal
Abstract: Graphs and hypergraphs are foundational structures in discrete mathematics. They have many practical applications, including the rapidly developing field of bioinformatics, and more generally, biomathematics. They are also a source of interesting algorithmic problems. In this paper, we define a extit{construction process} for minimally connected -uniform hypergraphs, which captures the intuitive notion of building a hypergraph piece-by-piece, and a numerical invariant called the extit{tightness}, which is independent of the construction process used. Using these tools, we prove some fundamental properties of minimally connected hypergraphs. We also give bounds on their chromatic numbers and provide some results involving edge colorings. We show that every connected -uniform hypergraph contains a minimally connected spanning subhypergraph and provide a polynomial-time algorithm for identifying such a subhypergraph.
This page was built for publication: Minimally Connected Hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312462)
