Research on diameter graphs of finite point sets defined by the number of distance

Abstract

A planar point set X is called a k-distance set if there are exactly k distinct distances defined by every two points in X, and the longest distance is called diameter D. The set of the endpoints of all diameters is denoted by XD . Let m=m(X)=|XD| be the number of elements of XD, and the diameter graph DG(XD) be all diameters in X. There are many results on determining the value of g(k) when k≤6, where g(k) is the number of points of the largest point set having k distinct distances. We consider planar point sets for the case of k≥7. Firstly, we perform an analysis on the degree value d(v) of all vertices in k-distance DG(XD) for m=|XD|=2k-1, and obtain that d(v)≤2. Based on this result, we research the case of 7-distance. We get XD=R15-3 when the 7-distance sets DG(XD)=P10∪P2. The result provides a theoretical foundation for further discussions on 7-distance sets.

Keywords

• combinatorial mathematics
• distinct distance
• diameter graph
• k-distance sets