MISC

2001年6月15日

Independent spanning trees with small depths in iterated line digraphs

Discrete Applied Mathematics
  • Toru Hasunuma
  • ,
  • Hiroshi Nagamochi

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.

リンク情報
DOI
https://doi.org/10.1016/S0166-218X(00)00269-9

エクスポート
BibTeX RIS