Reference : Connecting face hitting sets in planar graphs
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/10993/11458
Connecting face hitting sets in planar graphs
English
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)]
2010
Information Processing Letters
Elsevier
111
1
11-15
Yes (verified by ORBilu)
International
0020-0190
[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.
http://hdl.handle.net/10993/11458
10.1016/j.ipl.2010.10.008
http://www.mpi-inf.mpg.de/%7Epascal/docs/schweitzer_schweitzer_planar_CFVS.pdf

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
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.