Ordered \(h\)-hypertrees
type: Item
instance of: scholarly article
title: Ordered \(h\)-hypertrees
zbMATH Open document ID: 0772.05075
DOI: 10.1016/0012-365X(92)90146-7
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: In a previous paper [J. Comb. Theory, Ser. B 41, 209-217 (1986; Zbl 0577.05052)] the author introduced a combinatorial structure, called \(h\)- hypertree, which is an \(h\)-uniform hypergraph satisfying some conditions, in order to improve Bonferroni inequalities by including an additional term determined by such a hypertree. In this paper a special class of \(h\)-hypertrees, called \(\mu\)-ordered \(h\)-hypertrees relatively to a total order \(\mu\) on the vertex set, is introduced. Seven other equivalent definitions of such hypertrees are proposed involving the notions of \(\mu\)-ordered path and \(\mu\)-ordered cycle, some of them being similar to well-known characterizations of trees (case \(h=2)\). It is also proved that for a fixed order \(\mu\), the sets of edges of \(\mu\)-ordered \(h\)- hypertrees with the same vertex set is the set of bases of a graphic matroid and every \(h\)-hypertree can be recognized in polynomial time. However the problem of deciding whether there exists a spanning \(h\)- hypertree of the complete \(h\)-hypergraph \(K^ h_ n\) having the cost less than \(k\) is an NP-complete problem even for \(h=3\) [\textit{I. Tomescu} and \textit{M. Zimand}, Minimum spanning hypertrees, to be published in Discrete App. Math.].
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 06F99
zbMATH DE Number: 94361
zbMATH Keywords: \(h\)-hypertree
zbMATH Keywords: ordered path
zbMATH Keywords: ordered cycle
zbMATH Keywords: graphic matroid
author: Ioan Tomescu
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Hypertrees and Bonferroni inequalities
cites work: Minimum spanning hypertrees
cites work: Q4168637
Recommended article: Q3698832
Recommended article: Q4201567
Recommended article: Hypertrees
Recommended article: Sharpened Bonferroni inequalities
Recommended article: Minimum spanning hypertrees
Recommended article: Hypergraphs and sharpened sieve inequalities
Recommended article: Bounds on the number of edges in hypertrees
Recommended article: Asymptotic sharpness of bounds on hypertrees
Recommended article: Q3708050
Recommended article: Q4821209
description: scientific article; zbMATH DE number 94361