Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #97014 (December, 1997)

Independent spannig trees with small depths in iterated line digraphs
by Toru Hasunuma and Hiroshi Nagamochi


We show that the independent spanning tree conjecture on digraphs is true if we restrict ourselves to line digraphs. Also, we construct independent spanning trees with small depths in iterated line digraphs. From the results, we can obtain independent spanning trees with small depths in de Bruijn and Kautz digraphs that improve the previously known upper bounds on the depths.