Uniqueness of maximum planar five-distance sets

DOI10.1016/J.DISC.2007.08.028MaRDI QIDQ924997zbMATH OpenOpenAlexFDO

Authors Masashi Shinohara

Publication date 29 May 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.08.028

zbMATH Keywords

distance setsEuclidean plane

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Extremal problems in graph theory (05C35)

Review text

A set of points in the plane is called \(k\)-distance if there are exactly \(k\) different distances between two distinct points in the set. Two subsets are considered the same if they are related by an isometry and/or a similarity transformation. Let \(g(k)\) denote the maximum possible size of a \(k\)-distance set. It is known that \(g(k)=5,7,9,12\) for \(k=2,3,4,5\) respectively. Moreover, the 5-point 2-distance set is unique, there are exactly two 7-point 3-distance sets, and exactly four 9-point 4-distance sets. It was conjectured that the known 12-point 5-distance set is unique. In this paper the author proves that the 12-point 5-distance set is indeed unique. All 8-point 4-distance sets are shown, these include vertex deleted subgraphs of the 9-point 4-distance graphs and three sporadic examples. Diameter graphs of a planar set are introduced, these have vertex set the points in the given set with two vertices adjacent if and only if their distance is the diameter of the set. These graphs are studied and characterized.

Recommendations

• A proof of Erdős-Fishburn's conjecture for \(g(6)=13\)
• scientific article; zbMATH DE number 6107252
• Maximum planar sets that determine k distances
• Classification of seven-point four-distance sets in the plane
• Distance sets with diameter graph being cycle

Cites work

• An upper bound for the cardinality of an s-distance subset in real Euclidean space. II
• Classification of three-distance sets in two dimensional Euclidean space
• Convex nonagons with five intervertex distances
• Convex polygons with few intervertex distances
• scientific article; zbMATH DE number 3815662 (Why is no real title available?)
• scientific article; zbMATH DE number 3234139 (Why is no real title available?)
• Maximum planar sets that determine k distances
• On A Problem of P. Erdos

Cited in

(20)

• Maximum planar sets that determine k distances
• Classification of three-distance sets in two dimensional Euclidean space
• A proof of a dodecahedron conjecture for distance sets
• Sets in \(\mathbb{R}^d\) determining \(k\) taxicab distances
• Maximal 2-distance sets containing the regular simplex
• Characterizing optimal point sets determining one distinct triangle
• Classification of seven-point four-distance sets in the plane
• scientific article; zbMATH DE number 4010627 (Why is no real title available?)
• Sparse distance sets in the triangular lattice
• scientific article; zbMATH DE number 1290179 (Why is no real title available?)
• Distance Sets on Circles
• scientific article; zbMATH DE number 6107252 (Why is no real title available?)
• Complex spherical codes with two inner products
• Distance sets with diameter graph being cycle
• Lattice Configurations Determining Few Distances
• Optimal point sets determining few distinct triangles
• Euclidean sets with only one distance modulo a prime ideal
• Maximal \(m\)-distance sets containing the representation of the Hamming graph \(H(n, m)\)
• The 22 minimal dichotomy decompositions of the \(K_5\)-distance
• On a generalization of distance sets

This page was built for publication: Uniqueness of maximum planar five-distance sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q924997)