Name
Abstract | ||
|---|---|---|
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 digraph 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 vertex-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 copies 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 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. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0020-0190(96)00183-4 | Inf. Process. Lett. |
Keywords | Field | DocType |
line digraph operation,de bruijn graph,containment,parallel processing | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Parallel processing,De Bruijn sequence,Butterfly graph,Fractional part,Mathematics,Digraph | Journal |
Volume | Issue | ISSN |
61 | 1 | 0020-0190 |
Citations | PageRank | References |
2 | 0.43 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toru Hasunuma | 1 | 142 | 16.00 |
| Yukio Shibata | 2 | 2 | 0.43 |