Unit Ball Graphs on Geodesic Spaces
- PDF / 513,129 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 194 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Unit Ball Graphs on Geodesic Spaces Masamichi Kuroda1 • Shuhei Tsujie2 Received: 10 June 2019 / Revised: 1 September 2020 / Accepted: 9 September 2020 Ó Springer Japan KK, part of Springer Nature 2020
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-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. As a corollary, we prove that the collection of unit ball graphs essentially characterizes the real line and the unit circle. Keywords Geodesic space R -tree Real tree 0-hyperbolic space Unit ball graph Unit interval graph Intersection graph Chordal graph Strongly chordal graph (claw, net) -free graph Hamiltonian-hereditary graph
Mathematics Subject Classification 51D20 05C62 05C75
1 Introduction Let (X, d) be a metric space. Consider finitely many points x1 ; . . .; xn in X and fix a threshold d [ 0. If dðxi ; xj Þ d, we regard xi and xj as ‘‘near’’. We can construct a simple graph on the set fx1 ; . . .; xn g with edges between near points. It might be & Shuhei Tsujie [email protected] Masamichi Kuroda [email protected] 1
Faculty of Engineering, Nippon Bunri University, Oita 870-0316, Japan
2
Department of Education, Hokkaido University of Education, Hokkaido 070-8621, Japan
123
Graphs and Combinatorics
expected that we could obtain some information about X from graphs constructed in such a way. However, it seems difficult to study metric spaces with unit ball graphs without any other assumptions. For example, let (X, d) be a metric space defined by p 11p X :¼ ðcos h; sin hÞ 2 R2 j h 6 6 and d is the restriction of the Euclidean metric in R2 . Take points 11p x ¼ ðcos p6 ; sin p6Þ; y ¼ ðcos 11p 6 ; sin 6 Þ, and z ¼ ð1; 0Þ and suppose that d ¼ 1 (see Fig. 1). Then x is ‘‘near’’ to y but not to z, which seems counterintuitive. It is natural to regard x and y as the ‘‘furthest’’ points in X and z is the midpoint between x and y. If we define a metric on X by arc length, then it fits our intuition. Thus, from now on, our interest focus on geodesic spaces defined as follows. Definition 1.1 Let (X, d) be a metric space and x; y 2 X. A geodesic from x to y is a distance-preserving map c from a closed interval ½0; dðx; yÞ R to X with cð0Þ ¼ x and cðdðx; yÞÞ ¼ y. Its image is said to be a geodesic segment with endpoints x and y. We say that (X, d) is a geodesic space if every two points
Data Loading...
