✦ LIBER ✦

On distinct distance sets in a graph

✍ Scribed by Xiaohui Lin; Minghua Zhu; Zhengguo Yu; Chengxue Zhang; Yuansheng Yang

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 182 KB
Volume: 175
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00126-4

No coin nor oath required. For personal study only.

✦ Synopsis

A distinct distance set (DD set) for a graph G is a vertex subset of G with the property that for ISI = s, we have (~) distinct distances of the pairs of vertices in S.

In this article, it is shown that (a) For 6 ~< k ~< 18 there exists a tree T with DD(T) = k and din(T) = LB(k) < B~(Kk). where LB(k) is the smallest value L for which there are positive integers A and B with (b) For k ~< 10, the minimum order of a tree T with DD(T) = k is BI(Kk), which is the order of the corresponding Colomb ruler for k.

📜 SIMILAR VOLUMES

Distinct distance sets in a graph

✍ Richard A. Gibbs; Peter J. Slater 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 987 KB

The problem of labelling the complete graph K,, as near to graceful as possible is equivalent to the 'Golomb ruler problem' of finding as short a ruler as possible with n integer marks such that the distances between pairs of marks are all distinct. We generalize this to an association between label

Distinct Distances in Homogeneous Sets i

Distinct Distances in Homogeneous Sets in Euclidean Space

✍ Jozsef Solymosi; Csaba D. Toth 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 230 KB

Distance graphs with missing multiples i

Distance graphs with missing multiples in the distance sets

✍ Liu, Daphne D.-F.; Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 3 views

Given positive integers m, k, and s with m > ks, let D m,k,s represent the set {1, 2, . . . , m} -{k, 2k, . . . , sk}. The distance graph G(Z, D m,k,s ) has as vertex set all integers Z and edges connecting i and j whenever |i -j| ∈ D m,k,s . The chromatic number and the fractional chromatic number

Distinct distances determined by subsets

Distinct distances determined by subsets of a point set in space

✍ David Avis; Paul Erdo&#x030B;s; János Pach 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 670 KB

A distinct distance set of 9 nodes in a

A distinct distance set of 9 nodes in a tree of diameter 36

✍ Herbert Taylor 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 151 KB

Taylor, H., A distinct distance set of 9 nodes in a tree of diameter 36, Discrete Mathematics 93 (1991) 167-168.

On distance-regularity in graphs

✍ Paul M Weichsel 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 262 KB