کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872529 | 681651 | 2014 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Rotational circulant graphs
ترجمه فارسی عنوان
نمودار چرخشی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A Frobenius group is a transitive permutation group which is not regular but only the identity element can fix two points. Such a group can be expressed as the semidirect product G=KâH of a nilpotent normal subgroup K and another group H fixing a point. A first-kind G-Frobenius graph is a connected Cayley graph on K with connection set an H-orbit aH on K that generates K, where H has an even order or a is an involution. It is known that the first-kind Frobenius graphs admit attractive routing and gossiping algorithms. A complete rotation in a Cayley graph on a group G with connection set S is an automorphism of G fixing S setwise and permuting the elements of S cyclically. It is known that if the fixed-point set of such a complete rotation is an independent set and not a vertex-cut, then the gossiping time of the Cayley graph (under a certain model) attains the smallest possible value. In this paper we classify all first-kind Frobenius circulant graphs that admit complete rotations, and describe a means to construct them. This result can be stated as a necessary and sufficient condition for a first-kind Frobenius circulant to be 2-cell embeddable on a closed orientable surface as a balanced regular Cayley map. We construct a family of non-Frobenius circulants admitting complete rotations such that the corresponding fixed-point sets are independent and not vertex-cuts. We also give an infinite family of counterexamples to the conjecture that the fixed-point set of every complete rotation of a Cayley graph is not a vertex-cut.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 296-305
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 296-305
نویسندگان
Alison Thomson, Sanming Zhou,