Article ID Journal Published Year Pages File Type
420389 Discrete Applied Mathematics 2009 8 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,