无向圆盘图中最大r跳独立邻居数的估计

摘要

In this paper, we consider the maximum r-hop(r≥2) independent neighborhood vertex of disk graph. Given a disk graph G=(V,E), letNr(V) be the set of vertices which distance is at most r-hop fromv. For any independent setI of G,HereK is a ratio between largest disk radius and smallest disk radius.%本文考虑无向圆盘图中的最大r-跳独立邻居数(r≥2)。给定一个圆盘图G=(V,E)，对任意v∈V，用Nr(V)表示所有距节点v跳数最多为r的节点集合，则对G中任何一个r-跳独立集I，其在Nr(V)内最多有β个节点，(此处公式省略)这里K是圆盘图的最大圆盘半径与最小圆盘半径的比值。