Transversals and Independence in Linear Hypergraphs with Maximum Degree Two

Abstract

For $k \ge 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, $\tau(H)$, of $H$ is the minimum cardinality of a transversal in $H$, and the strong independence number of $H$, $\alpha(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 $\mathcal{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 \in \mathcal{H}_k$, then $(k+1)\tau(H) \le 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 $\tau(H)$ and tight lower bounds on $\alpha(H)$ that are achieved for  infinite families of hypergraphs. More precisely, if $k \ge 3$ is odd and $H \in \mathcal{H}_k$ has $n$ vertices and $m$ edges, then we prove that $k(k^2 - 3)\tau(H) \le (k-2)(k+1)n + (k - 1)^2m + k-1$ and $k(k^2 - 3)\alpha(H) \ge  (k^2 + k - 4)n  - (k-1)^2 m - (k-1)$. Similar bounds are proven in the case when $k \ge 2$ is even.