首页 | 本学科首页   官方微博 | 高级检索  
     


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 View the MathML source of subgraphs of X, all isomorphic with G, such that (i) every edge of X occurs in exactly two members of View the MathML source and (ii) View the MathML source and View the MathML source 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号