کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420389 | 683930 | 2009 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Orthogonal double covers of Cayley graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let XX and GG be graphs, such that GG is isomorphic to a subgraph of XX.An orthogonal double cover (ODC) of XX by GG is a collection B={P(x):x∈V(X)}B={P(x):x∈V(X)} of subgraphs of XX, all isomorphic with GG, such that (i) every edge of XX occurs in exactly two members of BB and (ii) P(x)P(x) and P(y)P(y) share an edge if and only if xx and yy are adjacent in XX. The main question is: given the pair (X,G)(X,G), is there an ODC of XX by GG? An obvious necessary condition is that XX is regular.A technique to construct ODCs for Cayley graphs is introduced. It is shown that for all (X,G)(X,G) where XX is a 3-regular Cayley graph on an abelian group there is an ODC, a few well known exceptions apart.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 14, 28 July 2009, Pages 3111–3118
Journal: Discrete Applied Mathematics - Volume 157, Issue 14, 28 July 2009, Pages 3111–3118
نویسندگان
R. Scapellato, R. El-Shanawany, M. Higazy,