MISC

2001年5月6日

Completely independent spanning trees in the underlying graph of a line digraph

Discrete Mathematics
  • Toru Hasunuma

234
1-3
開始ページ
149
終了ページ
157
記述言語
英語
掲載種別
DOI
10.1016/S0012-365X(00)00377-0

In this note, we define completely independent spanning trees. We say that T1,T2,...,Tk are completely independent spanning trees in a graph H if for any vertex r of H, they are independent spanning trees rooted at r. We present a characterization of completely independent spanning trees. Also, we show that for any k-vertex-connected line digraph L(G), there are k completely independent spanning trees in the underlying graph of L(G). At last, we apply our results to de Bruijn graphs, Kautz graphs, and wrapped butterflies. © 2001 Elsevier Science B.V. All rights reserved.

リンク情報
DOI
https://doi.org/10.1016/S0012-365X(00)00377-0

エクスポート
BibTeX RIS