Connecting face hitting sets in planar graphs

Abstract:  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−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−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.

Keyword(s):  Combinatorial problems ; Planar graph ; Face hitting set

Publication Year:   2010

Research Unit:   University of Luxembourg, FSTC & SNT, CSC

Reference:  Information Processing Letters, 111 (2010), no. 1, pp. 11-15

Full text available on :   http://www.mpi-inf.mpg.de/%7Epascal/docs/schweitzer_schweitzer_planar_CFVS.pdf (This access could be restricted and is not under UL responsibility); http://dx.doi.org/DOI: 10.1016/j.ipl.2010.10.008 (This access could be restricted and is not under UL responsibility)