کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777085 1632570 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A simple approach for lower-bounding the distortion in any Hyperbolic embedding
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A simple approach for lower-bounding the distortion in any Hyperbolic embedding
چکیده انگلیسی
We answer open questions of [Verbeek and Suri, SOCG'14] on the relationships between Gromov hyperbolicity and the optimal stretch of graph embeddings in Hyperbolic space. Then, based on the relationships between hyperbolicity and Cops and Robber games, we turn necessary conditions for a graph to be Cop-win into sufficient conditions for a graph to have a large hyperbolicity (and so, no low-stretch embedding in Hyperbolic space). In doing so we derive lower-bounds on the hyperbolicity in various graph classes - such as Cayley graphs, distance-regular graphs and generalized polygons, to name a few. It partly fills in a gap in the literature on Gromov hyperbolicity, for which few lower-bound techniques are known.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 293-299
نویسندگان
, ,