The Independence Number for De Bruijn networks and Kautz networks

Let DD be a directed graph; the (l,ω)(l,ω)-Independence Number of graph DD, denoted by αl,ω(D)αl,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n)B(d,n) and K(d,n)K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,nl=1,2,…,n, this paper shows that αl,d−1(B(d,n))=dn,αl,d−1(K(d,n))=αl,d(K(d,n))=dn+dn−1αl,d−1(B(d,n))=dn,αl,d−1(K(d,n))=αl,d(K(d,n))=dn+dn−1 if d≥3d≥3 and n≤d−2n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1)B(d,1) and B(d,2)B(d,2) for any dd. For the generalized situation, the paper obtains a lower bound αl,d−1(B(d,n))≥d2αl,d−1(B(d,n))≥d2 if n≥3n≥3 and d≥5d≥5.