Annulus Graphs in $\mathbb R^d$

期刊论文
出版模式：

开放获取
发表日期：

2024年5月16日

查看全文

Lyuben Lichev,
Tsvetomir Mihaylov

摘要

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} \geq R_{1} \geq 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 \in 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} \geq R_{1} > 0$ and also $\exp (\Omega (d))$ $exp (Ω (d))$ if moreover $R_2/R_1\ge 1.2$ $R_{2} / R_{1} \geq 1.2$ .

Annulus Graphs in \(\mathbb R^d\)

摘要