Characterization of Gromov hyperbolic short graphs

被引：0
作者：
José Manuel Rodríguez
机构：
[1] Universidad Carlos III de Madrid,Departamento de Matemáticas
来源：
Acta Mathematica Sinica, English Series | 2014年 / 30卷
关键词：
Short graph; Gromov hyperbolicity; Gromov hyperbolic graph; infinite graphs; geodesics; 05C10; 05C12; 05C75; 05A20;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
To decide when a graph is Gromov hyperbolic is, in general, a very hard problem. In this paper, we solve this problem for the set of short graphs (in an informal way, a graph G is r-short if the shortcuts in the cycles of G have length less than r): an r-short graph G is hyperbolic if and only if S9r(G) is finite, where SR(G):= sup{L(C): C is an R-isometric cycle in G} and we say that a cycle C is R-isometric if dC(x, y) ≤ dG(x, y) + R for every x, y ∈ C.
引用
收藏
页码：197 / 212
页数：15
相关论文
共 76 条
[1]  
Balogh Z M(2003)Geometric characterizations of Gromov hyperbolicity Invent. Math. 153 261-301
[2]  
Buckley S M(2011)Computing the hyperbolicity constant Comput. Math. Appl. 62 4592-4595
[3]  
Bermudo S(2011)Hyperbolicity and complement of graphs Appl. Math. Letters 24 1882-1887
[4]  
Rodríguez J M(1996)Quasi-geodesics segments and Gromov hyperbolic spaces Geometriae Dedicata 62 281-298
[5]  
Sigarreta J M(2001)Uniformizing Gromov hyperbolic spaces Astérisque 270 99pp-69
[6]  
Bermudo S(2001)On the hyperbolicity of chordal graphs Ann. Comb. 5 61-170
[7]  
Rodríguez J M(2012)Distortion of the hyperbolicity constant of a graph Electr. J. Comb. 19 P67-234
[8]  
Sigarreta J M(2011)Gromov hyperbolicity of line graphs Electr. J. Comb. 18 P210-149
[9]  
Bonk M(2001)Graph homotopy and Graham homotopy Discrete Math. 241 153-1142
[10]  
Bonk M.(2008)Notes on diameters, centers, and approximating trees of Electr. Notes Discr. Math. 31 231-261
12345678