کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418487 | 681674 | 2012 | 8 صفحه PDF | دانلود رایگان |
The arboricity of a hypergraph HH is the minimum number of acyclic hypergraphs that partition HH. The determination of the arboricity of hypergraphs is a problem motivated by database theory. The exact arboricity of the complete kk-uniform hypergraph of order nn is previously known only for k∈{1,2,n−2,n−1,n}k∈{1,2,n−2,n−1,n}. The arboricity of the complete kk-uniform hypergraph of order nn is determined asymptotically when k=n−O(log1−δn)k=n−O(log1−δn), δδ positive, and determined exactly when k=n−3k=n−3. This proves a conjecture of Wang (2008) [20] in the asymptotic sense.
► We study the arboricity of hypergraphs, the minimum number of acyclic hypergraphs that partition a given hypergraph.
► The arboricity of the complete kk-uniform hypergraph is determined when k=n−3k=n−3.
► The arboricity of the complete kk-uniform hypergraph of order nn is determined asymptotically when k=n=O(log1−δn)k=n=O(log1−δn), δδ positive.
Journal: Discrete Applied Mathematics - Volume 160, Issues 1–2, January 2012, Pages 100–107