✦ LIBER ✦

Every Graph Is an Integral Distance Graph in the Plane

✍ Scribed by Hiroshi Maehara; Katsuhiro Ota; Norihide Tokushige

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 290 KB
Volume: 80
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1997.2826

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that every finite simple graph can be drawn in the plane so that any two vertices have an integral distance if and only if they are adjacent. The proof is constructive.

📜 SIMILAR VOLUMES

Subdividing a Graph Toward a Unit-distan

Subdividing a Graph Toward a Unit-distance Graph in the Plane

✍ Severino V. Gervacio; Hiroshi Maehara 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 150 KB

The subdivision number of a graph G is defined to be the minimum number of extra vertices inserted into the edges of G to make it isomorphic to a unit-distance graph in the plane. Let t (n) denote the maximum number of edges of a C 4 -free graph on n vertices. It is proved that the subdivision numbe