2023/08/05 by Botler, Fábio, Fernandes, Cristina G., Gutiérrez, Juan
#05C10 #05C69 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2308.02754
In 1996, Matheson and Tarjan proved that every near planar triangulation on n vertices contains a dominating set of size at most n/3, and conjectured that this upper bound can be reduced to n/4 for planar triangulations when n is sufficiently large. In this paper, we consider the analogous problem for independent dominating sets: What is the minimum ε for which every near planar triangulation on n vertices contains an independent dominating set of size at most εn? We prove that 2/7 ≤ ε≤ 5/12. Moreover, this upper bound can be improved to 3/8 for planar triangulations, and to 1/3 for planar triangulations with minimum degree 5.