Unit Ball Graphs on Geodesic Spaces

preprint2020arXivOpen access

Abstract

Consider finitely many points in a geodesic space. If the distance of two points is less than a fixed threshold, then we regard these two points as "near". Connecting near points with edges, we obtain a simple graph on the points, which is called a unit ball graph. If the space is the real line, then it is known as a unit interval graph. Unit ball graphs on a geodesic space describe geometric characteristics of the space in terms of graphs. In this article, we show that every unit ball graph on a geodesic space is (strongly) chordal if and only if the space is an R \mathbb{R} -tree and that every unit ball graph on a geodesic space is (claw, net)-free if and only if the space is a connected manifold of dimension at most 1 1 . As a corollary, we prove that the collection of unit ball graphs essentially characterizes the real line and the unit circle.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.