Orthogonal double covers of Cayley graphs |
| |
Authors: | R. Scapellato R. El-Shanawany M. Higazy |
| |
Affiliation: | aDipartimento di Matematica, Politecnico di Milano, Milan, Italy;bDepartment of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufiya University, Menouf, Egypt |
| |
Abstract: | Let X and G be graphs, such that G is isomorphic to a subgraph of X.An orthogonal double cover (ODC) of X by G is a collection of subgraphs of X, all isomorphic with G, such that (i) every edge of X occurs in exactly two members of and (ii) and share an edge if and only if x and y are adjacent in X. The main question is: given the pair (X,G), is there an ODC of X by G? An obvious necessary condition is that X is regular.A technique to construct ODCs for Cayley graphs is introduced. It is shown that for all (X,G) where X is a 3-regular Cayley graph on an abelian group there is an ODC, a few well known exceptions apart. |
| |
Keywords: | Cayley graph Graph decomposition Orthogonal double cover Symmetric starter |
本文献已被 ScienceDirect 等数据库收录! |
|