✦ LIBER ✦

Distinct distance sets in a graph

✍ Scribed by Richard A. Gibbs; Peter J. Slater

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 987 KB
Volume: 93
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90251-v

No coin nor oath required. For personal study only.

✦ Synopsis

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 labellings of K,, with m-tuples and 'distinct distance sets' in m-dimensional grids. More generally, we define distinct distance sets for any graph G and investigate the parameter DD(G) which is the maximum size of a distinct distance set in G.

📜 SIMILAR VOLUMES

On distinct distance sets in a graph

✍ Xiaohui Lin; Minghua Zhu; Zhengguo Yu; Chengxue Zhang; Yuansheng Yang 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 182 KB

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(

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.

Distance-regular Subgraphs in a Distance

Distance-regular Subgraphs in a Distance-regular Graph, III

✍ Akira Hiraki 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Let ⌫ be a distance-regular graph with l (1 , a 1 , b 1 ) ϭ 1 and c s ϩ 1 ϭ 1 for some positive integer s . We show the existence of a certain distance-regular graph of diameter s , containing given two vertices at distance s , as a subgraph in ⌫ .