A property on reinforcing edge-disjoint spanning hypertrees in uniform hypergraphs

作者：Gu Xiaofeng^*; Lai Hong Jian

来源：Discrete Mathematics, 2018, 341(2): 400-404.

DOI：10.1016/j.disc.2017.09.007

• Spanning hypertrees
• Partition connectivity
• Uniformly dense

Suppose that H is a simple uniform hypergraph satisfying vertical bar E(H)vertical bar = k(vertical bar V(H)vertical bar - 1). A k-partition pi = (X-1,X-2,..,X-k) of E(H) such that vertical bar X-i vertical bar = vertical bar V(H)vertical bar - 1 for 1 <= i <= k is a uniform k-partition. Let P-k(H) be the collection of all uniform k-partitions of E(H) and define epsilon(pi)=Sigma(k)(i=1) c(H(X-1))-k, where c(H) denotes the number of maximal partition-connected sub-hypergraphs of H. Let epsilon(H) = min(pi is an element of Pk(H))epsilon(pi). Then epsilon(H) >= 0 with equality holds if and only if H is a union of k edge-disjoint spanning hypertrees. The parameter epsilon(H) is used to measure how close His being from a union of k edge-disjoint spanning hypertrees.
We prove that if H is a simple uniform hypergraph with vertical bar E(H)vertical bar = k(vertical bar V(H)vertical bar - 1) and epsilon(H) > 0, then there exist e is an element of E(H) and e' is an element of E(H-c) such that epsilon(H - e + e') < epsilon(H). This generalizes a former result, which settles a conjecture of Payan. The result iteratively defines a finite epsilon-decreasing sequence of uniform hypergraphs H-0,H-1, H-2,..., H-m such that H-0 = H, H-m is the union of k edge-disjoint spanning hypertrees, and such that two consecutive hypergraphs in the sequence differ by exactly one hyperedge.

• 出版日期2018-2