Zhejiang Daxue xuebao. Lixue ban (Sep 2005)

Spectra of the directed de Bruijn graphs(有向de Bruijn图的谱)

  • YINJian-hong(殷剑宏)

DOI
Journal volume & issue
Vol. 32, no. 5
pp. 536 – 539

Abstract

Read online

首先分析了n维d进位有向de Bruijn图B（d，n）(d≥2，n≥1)及其邻接矩阵A的结构，证明了从B（d，n）的顶点x到y只有一条长度为n的有向链，从而证得了An=J（其中J为dn×dn阶矩阵，且其全部元素均为1）.文章最后获得了有向de Bruijn图B（d，n）的谱，B(d,n)的特征值为0与d，且它们所对应的重数分别为dn-1和1.

Keywords