## Abstract

For k ≥ 2, let H be a k-uniform hypergraph on n vertices and m edges. Let S be a set of vertices in a hypergraph H. The set S is a transversal if S intersects every edge of H, while the set S is strongly independent if no two vertices in S belong to a common edge. The transversal number, τ (H), of H is the minimum cardinality of a transversal in H, and the strong independence number of H, α(H), is the maximum cardinality of a strongly independent set in H. The hypergraph H is linear if every two distinct edges of H intersect in at most one vertex. Let H_{k} be the class of all connected, linear, k-uniform hypergraphs with maximum degree 2. It is known [European J. Combin. 36 (2014), 231–236] that if H ∈ H_{k}, then (k + 1)τ (H) 6 ≤ n + m, and there are only two hypergraphs that achieve equality in the bound. In this paper, we prove a much more powerful result, and establish tight upper bounds on τ (H) and tight lower bounds on α(H) that are achieved for infinite families of hypergraphs. More precisely, if k ≥ 3 is odd and H ∈ H_{k} has n vertices and m edges, then we prove that k(k^{2} −3)τ (H) ≤ (k−2)(k+ 1)n+ (k−1)^{2}m+k−1 and k(k^{2} −3)α(H) ≥ (k^{2} +k −4)n−(k −1)^{2}m−(k −1). Similar bounds are proven in the case when k ≥ 2 is even.

Original language | English |
---|---|

Article number | #P2.50 |

Journal | Electronic Journal of Combinatorics |

Volume | 24 |

Issue number | 2 |

DOIs | |

Publication status | Published - 30 Jun 2017 |

## Keywords

- Hypergraph
- Linear hypergraph
- Strong independence
- Transversal

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics