2001年6月15日
Independent spanning trees with small depths in iterated line digraphs
Discrete Applied Mathematics
- ,
- 巻
- 110
- 号
- 2-3
- 開始ページ
- 189
- 終了ページ
- 211
- 記述言語
- 英語
- 掲載種別
- DOI
- 10.1016/S0166-218X(00)00269-9
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. © 2001 Elsevier Science B.V.