CONTAINMENT OF BUTTERFLIES IN NETWORKS CONSTRUCTED BY THE LINE DIGRAPH OPERATION

Let G be a digraph. Let L(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(k)(G)) for some d igraph G and some integer k, where L(k)(G) = L(L(k-1)(G)). Let delta(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(delta(G)-1,r) are contained in U(L(r)(G)) such that they are ver tex-disjoint. Also it is proved that k(Sigma(1 less than or equal to i <[delta(G)/k]i(r) + [delta(G)/k](r){delta(G)/k}) vertex-disjoint copie s of b(k,r) are contained in U(L(r)(G)), where for a real x, [x] and { x} stand for the greatest integer not exceeding x and the fractional p art of x, respectively. As corollaries of these results, we can get re sults on the containment of butterflies in the de Bruijn and Kautz gra phs.