Distinct distance sets in a graph (Q1182889): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3892270 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3916587 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4044627 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5589124 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Odd Path Sums in an Edge-Labeled Tree / rank | |||
Normal rank |
Latest revision as of 15:33, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distinct distance sets in a graph |
scientific article |
Statements
Distinct distance sets in a graph (English)
0 references
28 June 1992
0 references
The authors introduce the concept of a distinct distance set (\(DD\) set) for a graph \(G\) as a vertex subset \(S\) of \(V(G)\) with the property that for \(s=| S|\) there are \(s\choose 2\) distinct distances for the pairs of vertices in \(S\). Considering the maximum size of a \(DD\) set for \(G\) --- denoted by \(DD(G)\) --- they want to determine certain classes of graphs \(G\) with the property that \(DD(G)=k\in\mathbb{N}\). They can completely settle this problem in case of bipartite graphs. Finally, the two authors deal with the set of \(m\)-dimensional grid graphs and define the notion of an \(m\)-fold numbering and give certain \(m\)-fold labellings of grid graphs and complete graphs. They conclude their paper by giving some remarkable conjectures. At the end of this brief review I'd like to mention that this note is very well legible because the authors explain the relationship between their \(DD\) problem and the Golomb ruler and graceful numberings of \(K_ n\) in an excellent way.
0 references
distinct distance sets
0 references
distances
0 references
bipartite graphs
0 references
grid graphs
0 references
labellings
0 references
complete graphs
0 references