EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Annulus Graphs in $$\mathbb R^d$$

Lyuben Lichev, Tsvetomir Mihaylov

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →