Transversals and independence in linear hypergraphs with maximum degree two (Q2363113)

Summary: For \(k \geq 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 [\textit{M. Dorfling} and \textit{M. A. Henning}, Eur. J. Comb. 36, 231--236 (2014; Zbl 1284.05188)] that if \(H \in \mathcal{H}_k\), then \((k+1)\tau(H) \leq 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 \geq 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)\leq (k-2)(k+1)n+(k-1)^2m + k-1\) and \(k(k^2-3)\alpha(H) \geq (k^2+k-4)n-(k-1)^2 m-(k-1)\). Similar bounds are proven in the case when \(k \geq 2\) is even.