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


De Bruijn digraphs and affine transformations
Authors:Aiping Deng  Yaokun Wu  
Affiliation:aDepartment of Mathematics, Shanghai Jiao Tong University, Shanghai, 200240, China;bCollege of Advanced Science and Technology, Dalian University of Technology, Dalian, 116024, China
Abstract:
Let be the additive group of 1×n row vectors over . For an n×n matrix T over  and , the affine transformation FT,ω of sends x to xT+ω. Let α be the cyclic group generated by a vector . The affine transformation coset pseudo-digraph has the set of cosets of α in as vertices and there are c arcs from x+α to y+α if and only if the number of zx+α such that FT,ω(z)y+α is c. We prove that the following statements are equivalent: (a)  is isomorphic to the d-nary (n−1)-dimensional De Bruijn digraph; (b) α is a cyclic vector for T; (c)  is primitive. This strengthens a result conjectured by C.M. Fiduccia and E.M. Jacobson [Universal multistage networks via linear permutations, in: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, ACM Press, New York, 1991, pp. 380–389]. Under the further assumption that T is invertible we show that each component of is a conjunction of a cycle and a De Bruijn digraph, namely a generalized wrapped butterfly. Finally, we discuss the affine TCP digraph representations for a class of digraphs introduced by D. Coudert, A. Ferreira and S. Perennes [Isomorphisms of the De Bruijn digraph and free-space optical networks, Networks 40 (2002) 155–164].
Keywords:Affine transformation   De Bruijn digraph   Wrapped butterfly   Transformation coset pseudo-digraph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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