کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653137 | 1632607 | 2006 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Small separations in vertex-transitive graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A rough structure theorem for small separations in symmetric graphs is developed. Let G=(V,E) be a vertex transitive graph, let A⊆V be finite with set k=|{v∈V\A:u∼v for some u∈A}|. We show that whenever the diameter of G is at least 312(k+1), either |A|⩽2k3, or G has a (bounded) ring-like structure and A is efficiently contained in an interval. This theorem has applications to the study of product sets and expansion in groups.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 24, 15 July 2006, Pages 165-172
Journal: Electronic Notes in Discrete Mathematics - Volume 24, 15 July 2006, Pages 165-172