Combinatorial problems; Planar graph; Face hitting set
Résumé :
[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.
Disciplines :
Mathématiques
Identifiants :
UNILU:UL-ARTICLE-2010-879
Auteur, co-auteur :
Schweitzer, Pascal; Max-Planck-Institute for Computer Science, Saarbrücken, Germany
SCHWEITZER, Patrick ; 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)
