Reference : Connecting face hitting sets in planar graphs
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Connecting face hitting sets in planar graphs
Schweitzer, Pascal mailto [Max-Planck-Institute for Computer Science, Saarbrücken, Germany]
Schweitzer, Patrick mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > > ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)]
Information Processing Letters
Yes (verified by ORBilu)
[en] Combinatorial problems ; Planar graph ; Face hitting set
[en] 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.

File(s) associated to this reference

Fulltext file(s):

Limited access
schweitzer_schweitzer_planar_CFVS.pdfAuthor postprint117.29 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.