Annulus Graphs in $$\mathbb R^d$$
Discrete & Computational Geometry · 2024-07 · 72 (1) · 379-401
DOI: 10.1007/s00454-024-00649-7 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete & Computational Geometry, online erschienen am 16.05.2024. Verfasst von Lyuben Lichev und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 37 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
A d -dimensional annulus graph with radii $$R_1$$ R 1 and $$R_2$$ R 2 (here $$R_2\ge R_1\ge 0$$ R 2 ≥ R 1 ≥ 0 ) is a graph embeddable in $$\mathbb R^d$$ R d so that two vertices u and v form an edge if and only if their images in the embedding are at distance in the interval $$[R_1, R_2]$$ [ R 1 , R 2 ] . In this paper we show that the family $$\mathcal A_d(R_1,R_2)$$ A d ( R 1 , R 2 ) of d -dimensional annulus graphs with radii $$R_1$$ R 1 and $$R_2$$ R 2 is uniquely characterised by $$R_2/R_1$$ R 2 / R 1 when this ratio is sufficiently large. Moreover, as a step towards a better understanding of the structure of $$\mathcal A_d(R_1,R_2)$$ A d ( R 1 , R 2 ) , we show that $$\sup _{G\in \mathcal A_d(R_1,R_2)} \chi (G)/\omega (G)$$ sup G ∈ A d ( R 1 , R 2 ) χ ( G ) / ω ( G ) is given by $$\exp (O(d))$$ exp ( O ( d ) ) for all $$R_1,R_2$$ R 1 , R 2 satisfying $$R_2\ge R_1 > 0$$ R 2 ≥ R 1 > 0 and also $$\exp (\Omega (d))$$ exp ( Ω ( d ) ) if moreover $$R_2/R_1\ge 1.2$$ R 2 / R 1 ≥ 1.2 .
Zitieren
APA
Lichev, L., & Mihaylov, T. (2024). Annulus Graphs in $$\mathbb R^d$$. Discrete & Computational Geometry, 72(1), 379-401. https://doi.org/10.1007/s00454-024-00649-7
Vancouver
Lichev L, Mihaylov T. Annulus Graphs in $$\mathbb R^d$$. Discrete & Computational Geometry. 2024;72(1):379-401. doi:10.1007/s00454-024-00649-7
BibTeX
@article{Lichev2024,
author = {Lichev, Lyuben and Mihaylov, Tsvetomir},
title = {Annulus Graphs in $$\mathbb R^d$$},
journal = {Discrete & Computational Geometry},
year = {2024},
volume = {72},
number = {1},
pages = {379--401},
doi = {10.1007/s00454-024-00649-7}
}
EUVIMED