On the independence number of minimum distance graphs

被引：7

作者：

Csizmadia, G ^{[1
]}

机构：

[1] NYU, Courant Inst, New York, NY 10012 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1998年 / 20卷 / 02期

关键词：

Minimum Distance; Discrete Comput Geom; Common Neighbor; Special Pair; Independence Number;

D O I：

10.1007/PL00009381

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let F = F(n) denote the largest number such that any set of n points in the plane with minimum distance 1 has at least F elements, no two of which are at unit distance. Improving a result by Pollack, we show that F(n) greater than or equal to 9/35n. We also give an O(n log n) time algorithm for selecting at least 9/35n elements in a set of n points with minimum distance 1 so that no two selected points are at distance 1.

引用

页码：179 / 187

页数：9