zbMATH — the first resource for mathematics

The cutwidth and the vertex separation number of hypergraphs and their König’s representations. (English. Russian original) Zbl 0854.05080
Discrete Math. Appl. 5, No. 3, 243-248 (1995); translation from Diskretn. Mat. 7, No. 2, 88-94 (1995).
The author considers two invariants of hypergraphs which are determined by some optimal enumerations of the vertices with respect to various criteria. These are the cutwidth and the vertex separation number. He gives some estimates of these invariants expressed in terms of the same invariants of their König representation. Among similar results, he proves that \(\text{vs}(K(H))\leq \text{cw}(H)\leq \lfloor D/2\rfloor \text{vs}(K(H))+ 1\), where \(H\) is a hypergraph without edges of degree one, \(K(H)\) its König representation and \(D\) the maximal degree among vertices of \(H\); cw denotes the cutwidth and vs the vertex separation number. The author points out that the estimates given can be used to calculate these invariants for hypergraphs without cycles, with small vertex or edge degrees, by polynomial algorithms with sufficient accuracy. In addition, he expresses the cutwidth of a hypergraph in terms of the vertex separation number of the dual hypergraph.
05C65 Hypergraphs
Full Text: DOI