On the span and extent of unit-distance graphs in the plane

College

College of Science

Department/Unit

Mathematics and Statistics Department

Document Type

Article

Source Title

Applied Mathematical Sciences

Volume

10

Issue

33-36

First Page

1611

Last Page

1618

Publication Date

1-1-2016

Abstract

Let G be a unit-distance graph in R2. For each unit-distance representation of G in R2, there is a smallest circumscribing circle. The infimum of the diameters of these circles, taken over all unit-distance representations of G, is called the span of G. On the other hand, the supremum of the diameters of all such circles is called the extent of G. We show that the ratio of the extent to the diameter can be made arbitrarily small. Also, we prove that the extent of G does not exceed 2/3√3 times the graph theoretic diameter of G. We further show that for every integer d ≥ 1, there exists a unit-distance graph G in R2 with diameter d and extent equal to 2/3√3d. © 2015 Severino V. Gervacio, Hiroshi Maehara and Joselito A. Uy.

html

Digitial Object Identifier (DOI)

10.12988/ams.2016.512728

Disciplines

Mathematics

Keywords

Graph theory; Combinatorial geometry

Upload File

wf_yes

This document is currently not available here.

Share

COinS