| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427384 | Information Processing Letters | 2010 | 5 Pages |
We show that any face hitting set of size n of a connected planar graph with a minimum degree of at least 3 is contained in a connected subgraph of size 5n−65n−6. Furthermore we show that this bound is tight by providing a lower bound in the form of a family of graphs. This improves the previously known upper and lower bound of 11n−1811n−18 and 3n respectively by Grigoriev and Sitters. Our proof is valid for simple graphs with loops and generalizes to graphs embedded in surfaces of arbitrary genus.
Research highlights► Size comparison of face hitting sets (FHS) and connected face hitting sets (CFHS) in planar graphs of minimum degree 3. ► Tight upper bound for size of largest CFHS to size of largest FHS ratio. ► Tight lower bound in form of a family of graphs with maximal size of largest CFHS to size of largest FHS ratio.
