给定距离数的有限点集直径图的研究

打开文本图片集

摘要：

给定一平面点集[WTBX]X，若点集X确定k个互异距离，则称X为k距离集，其中最长距离称为直径D。XD表示所有直径端点构成的集合，m=m（X）="XD|表示XD中的元素个数。DG（XD）表示X中的所有直径构成的图形。令g（k）表示确定k个距离的最大点集所含点的个数，目前对k≤6的g（k）取值有了确切的结果。研究了距离数k≥7的平面点集。首先，对m=|XD|=2k-1的k距离直径图DG（XD）中所有顶点的度值d（v）分析判断，得出d（v）≤2。在此基础上研究了7距离集的情形，证明当7距离集的直径图为DG（XD）=P10∪P2时，必有XD=R15-3。这是研究最大7距离集的基础。

关键词：组合数学；互异距离；直径图；k距离集[WT]

中图分类号：O157.3[WTHZ][STHZ]MSC（2010）主题分类[ST]：51K05文献标志码：A

收稿日期：20140624；修回日期：20140917；责任编辑：张军

基金项目：河北省自然科学基金（A201420809（5）

作者简介：魏祥林（1974—），女，河北张家口人，教授，博士，主要从事离散与组合几何方面的研究。

给定一平面点集[WTBX]X，如果X中的任意两点确定的互异距离数为k，则称X为k距离集。 用d（x，y）表示平面上互异两点x，y之间的距离，记X中的最大距离为直径D。令XD={x，y∈X：d（x，y）=D}。用m=m（X）=|XD|表示XD中的元素个数。文献[1]引入了直径图DG（XD）的概念，直径图DG（XD）是由X中所有直径构成的图。d（v）表示直径图DG（XD）中与v关联的边数，称之为v的度。Pn表示由n个顶点构成的一条路，Cn表示由n个顶点构成的一个圈。当有n个点时，加法运算在模n的条件下进行。定义Rn为正n边形顶点所构成的集合，R+n为正n边形顶点和中心所组成的集合，Rn-i表示正n边形中n-i个顶点组成的集合。[WT]ERDOS和FISHBURN在文献[2]中讨论了确定[WTBX]k距离的最大点集，记最大点集所含点数为g（k），并给出g（1）=3， g（2）=5， g（3）=7， g（（4）=9， g（（5）=12，对最大5距离集给出了详细的讨论，提出两大猜想：g（（6）=13且这样的十三点集只有3个；确定了g（k）（k≥（7）的最大点集只[WT]能在三角形格点上。文献[3]论证了3距离集的构造。SHINOHARA在文献[1]中论证了12点5距离集的构造唯一性。文献[4]—文献[8]中给出的11点5距离集的构造，7点4距离集的构造，证明了最大6距离集为13点集的猜想， 即[WTBX]g（（6）=13。文献[8]对直径图为圈C2k-3的k距离集进行了分析，相关的研究见文献[9]—文献[14]。本文通过对直径图中d（v）的分析，给出了m=12时一类特殊的7距离集直径图，这是研究最大7距离集的基础。[WT]

参考文献：

[1]SHINOHARA M. Uniqueness of maximum planar fivedistance sets [J]. Discrete Mathematics， 2008， 308（1（4）： 30483055.

[2]ERDOS P， FISHBURN P. Maximum planar sets that determine kdistance [J]. Discrete Mathematics， 1996， 160（1/2/3）： 115125.

[3]SHINOHARA M. Classification of threedistance sets in two dimensional Euclidean space [J]. European Journal of Combinatorics， 2004， 25（（7）： 10391058.

[4]FISHBURN P. Convex polygons with few intervertex distance [J]. Computational Geometry， 1995， 5（2）： 6593.

[5]WEI Xianglin. Classification of elevenpoint fivedistance sets in the plane [J]. Ars Combinatoria， 2011， 102： 505515.

[6]WEI Xianglin. A proof of ErdosFishburn"s conjecture for g（（6）=13[J]. The Electronic Journal of Combinatorics， 2012，19（（4）：117.

[7]LAN Wenhua， WEI Xianglin. Classfication of sevenpoint fourdistance sets in the plane [J]. Mathematical Notes， 2013， 93（（4）： 510522.

[8]WEI Xianglin， LI Guogang， CONG Yue，et al.Distance sets with diameter graph being cycle [J]. Taiwanese Journal of Mathematics，2014，18（（6）：19811990.

[9]魏祥林，张玉琴. 一类4等腰6元集[J]. 河北师范大学学报（自然科学版），2004， 28（（5）： 455456.

WEI Xianglin，ZHANG Yuqin.A type of 4isosceles set with 6point[J].Journal of Hebei Normal University（Natural Science Edition），2004，28（（5）：455456.

[10]NOZAKI H， SHINOHRAR M. On a generalization of distance sets [J]. Journal of Combinatorial Theory， Series A， 2010， 117（（7）： 810826.

[11]KIDO H. Classification of isosceles eightpoint sets in threedimensional Euclidean space [J]. European Journal of Combinatorics， 2006， 27： 329341.

[12]CHUNG F， SZEMEREDI E，TROTTER W.The number of different distance determined by a set of points in the Euclidean plane[J]. Discrete & Computational Geometry， 1992， 7： 111.

[13]KIDO H. Classification of isosceles 7point 3distance sets in 3dimensional Euclidean space [J]. European Journal of Combinatorics， 2007， 28： 685704.

[14]LISONEK P. New maximal twodistance sets [J]. Journal of Combinatorial Theory， Series A， 1997， 77（2）：318338.

[15]ALTMAN E. On a problem of P.Erdos[J]. American Mathematical Monthly， 1963， 70（2）： 148157.

推荐访问： 给定 直径 距离 研究 有限