کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420389 683930 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Orthogonal double covers of Cayley graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Orthogonal double covers of Cayley graphs
چکیده انگلیسی

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
نویسندگان
, , ,