The width of a hypergraph

Mathematics Asked by Erel Segal-Halevi on August 16, 2020

In this paper, the width of a hypergraph $H$ is defined as the minimum integer $t$ for which there exists a subset $T$ of $t$ hyperedges in $H$, such that every hyperedge of $H$ intersects at least one hyperedge of $T$.

To better understand this notion, I am trying to relate it to terms related to graphs. I found many "width" terms related to graphs, such as: tree-width, path-width, branch-width and bandwidth. But I could not understand which of these terms, if any, is equivalent to the above definition. Is this "width of a hypergraph" a well-known term in graph theory? Does it have a counterpart for simple graphs, maybe in another name?

One Answer

The exact analogue of this width for simple graphs, where your 'hyperedges' are all normal edges between two vertices, is the 'minimum size of a maximal matching'. wikipedia - matching

Hyper-edges can be 'large' as subsets of the vertex set, where as edges are quite constrained. So the most 'spiritually similar' concept to this width that is well studied is probably the 'vertex cover number'. This is the size of the smallest subset of vertices that is incident with every edge of the graph. wikipedia - vertex cover

Correct answer by Brandon du Preez on August 16, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP