Unit ball graphs on geodesic spaces

DOI10.1007/S00373-020-02231-3MaRDI QIDQ2657071zbMATH OpenOpenAlexFDO

Authors Masamichi Kuroda, Shuhei Tsujie

Publication date 17 March 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.08608

zbMATH Keywords

(claw0-hyperbolic space\(\mathbb{R}\)-treechordal graphgeodesic spaceHamiltonian-hereditary graphintersection graphnet)-free graphreal treestrongly chordal graphunit ball graphunit interval graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

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 $mathbbR$-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.

Recommendations

• scientific article; zbMATH DE number 866045
• A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)
• Minimal graphs with respect to geometric distance realizability
• Unit-distance graphs in rational n-spaces
• Random geometric graph diameter in the unit ball

Cites work

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Characterizations of strongly chordal graphs
• Graph Classes: A Survey
• Graph isomorphism for unit square graphs
• scientific article; zbMATH DE number 3730183 (Why is no real title available?)
• scientific article; zbMATH DE number 1535858 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Length functions of group actions on -trees
• On forbidden induced subgraphs for unit disk graphs
• Structure theorems for some circular-arc graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Unit disk graph recognition is NP-hard

Cited in

(1)

• MAT-free graphic arrangements and a characterization of strongly chordal graphs by edge-labeling

This page was built for publication: Unit ball graphs on geodesic spaces

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