加载中…
The domination number of a graph is the smallest possible size of a vertex set that intersects every radius- ball of , and the packing number is the maximum number of pairwise vertex-disjoint radius- balls. We prove that for every planar graph and for every unit disk graph, thus yielding Erdős-Pósa-type bounds for the hypergraph of radius- balls in the two graph classes. This improves upon results of Gutiérrez and Paul, and Dúcz and Gujgiczer, who in turn lowered bounds of Bonamy, Csikós, Gujgiczer and Yuditsky, and Böhme and Mohar. For both graph classes, the best known lower bound on the optimal constant remains .

生成讲解博客的中文版本

生成AI智能校验的中文版本