|
|||||
|
|
Independent spanning trees with small depths in iterated line digraphs |
|
| Authors: | Toru Hasunuma and Hiroshi Nagamochi |
| Institution: | a Department of Computer Science, University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan b Department of Information and Computer Sciences, Toyohashi University of Technology, Tenpaku, Toyohashi, Aichi 441-8580, Japan |
| Abstract: | 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. |
| Keywords: | Independent spanning trees Line digraphs Vertex connectivity De Bruijn digraphs Kautz digraphs Interconnection networks Broadcasting |
| 本文献已被 ScienceDirect 等数据库收录！ | |