Containment of butterflies in networks constructed by the line digraph operation

✍ Scribed by Toru Hasunuma; Yukio Shibata

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 484 KB
• Volume: 61
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(96)00183-4

✦ Synopsis

Let G be a digraph. Let ,5(G) and U(G) denote the line digraph of G and the underlying graph of G, respectively. A network constructed by the line digraph operation means a graph defined by U( L'( G) ) for some digraph G and some integer k, where Lk( G) = L( Lk-' (G)). Let S(G) be the minimum degree of the vertices of G. Let b( k, r) denote the r-dimensional k-ary butterfly graph. It is proved that b( 1, r) , b( 2, r) , . . . , b( 6( G) -1, I) are contained in U( L'( G) ) such that they are vertex-disjoint. Also it is proved that k( ~l~i<LslGj,kJ i' + [S( G)/kJ'{S( G)/k}) vertex-disjoint copies of b( k, r) are contained in U( L'( G) )

, where for a real x, 1x1 and {x} stand for the greatest integer not exceeding x and the fractional part of X, respectively, As corollaries of these results, we can get results on the containment of butterflies in the de Bruijn and Kautz graphs.