Some Combinatorial Algorithms on the Edge Cover Number of k-Regular Connected Hypergraphs

For \(k\ge 3\) , let H be a k-regular connected hypergraph on n vertices and m edges. The edge cover number \(\rho (H)\) is the minimum number of edges that intersect every vertex. We prove the following inequality: \(\rho (H)\le \frac{(k-1)n+1}{k}\) . Furthermore, the extremal hypergraphs with equality holds are exactly k-star hypertrees. Based on the proofs, some combinatorial algorithms on the edge cover number are designed.