کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949950 | 1440207 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the hyperbolicity of bipartite graphs and intersection graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Hyperbolicity is a measure of the tree-likeness of a graph from a metric perspective. Recently, it has been used to classify complex networks depending on their underlying geometry. Motivated by a better understanding of the structure of graphs with bounded hyperbolicity, we here investigate on the hyperbolicity of bipartite graphs. More precisely, given a bipartite graph B=(V0âªV1,E) we prove it is enough to consider any one side Vi of the bipartition of B to obtain a close approximate of its hyperbolicity δ(B) - up to an additive constant 2. We obtain from this result the sharp bounds δ(G)â1â¤Î´(L(G))â¤Î´(G)+1 and δ(G)â1â¤Î´(K(G))â¤Î´(G)+1 for every graph G, with L(G) and K(G) being respectively the line graph and the clique graph of G. Finally, promising extensions of our techniques to a broader class of intersection graphs are discussed and illustrated with the case of the biclique graph BK(G), for which we prove (δ(G)â3)/2â¤Î´(BK(G))â¤(δ(G)+3)/2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 187-195
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 187-195
نویسندگان
David Coudert, Guillaume Ducoffe,