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

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