## Abstract

A set S of vertices in a hypergraph H is strongly independent if no two vertices in S belong to a common edge. The strong independence number of H, denoted α(H), is the maximum cardinality of a strongly independent set in H. The rank of H is the size of a largest edge in H. The hypergraph H is k-uniform if every edge of H has size k. The transversal number, denoted τ(H), of H is the minimum number of vertices that intersect every edge. Our main result is that for all K ≥ 2, the strong independence ratio of a hypergraph H with rank k and maximum degree 3 satisfies α(H)/n(H) ≥ 3/7K and this bound is achieved for all k ≡ 0(mod 3). In particular, this bound is achieved for the Fano plane. As an application of our result, we show that if H is a k-uniform hypergraph on n vertices with m edges and with maximum degree 3 and n_{3} vertices of degree 3, then τ (H) ≤ (2n + km)/(3k) - 2n_{3}/(7k^{2}). This improves a result due to Chvátal and McDiarmid [Combinatorica 12 (1992), 19–26] who proved that τ (H) ≤ (n + ⌊K/2⌋ m)/(⌊3K/2⌋) in the case when K ≥ 2 is even and H has maximum degree 3.

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

Pages (from-to) | 196-208 |

Number of pages | 13 |

Journal | Journal of Graph Theory |

Volume | 83 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 Oct 2016 |

## Keywords

- Fano plane
- hypergraph
- strong independence
- transversal

## ASJC Scopus subject areas

- Geometry and Topology
- Discrete Mathematics and Combinatorics