Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs

DOI10.1137/S0097539793244198zbMath0874.05020OpenAlexW1974997494MaRDI QIDQ4337433

Zhengyu Ge, S. Louis Hakimi

Publication date: 9 November 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539793244198

zbMATH Keywords

Kautz digraphspanning treesdeBruijn digraph

Mathematics Subject Classification ID

Trees (05C05) Network design and communication in computer systems (68M10) Directed graphs (digraphs), tournaments (05C20) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (17)

Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees ⋮ Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs ⋮ Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes ⋮ Construction of optimal independent spanning trees on folded hypercubes ⋮ Completely independent spanning trees in torus networks ⋮ Completely independent spanning trees in some regular graphs ⋮ Constructing independent spanning trees for locally twisted cubes ⋮ Independent spanning trees on even networks ⋮ Independent spanning trees with small depths in iterated line digraphs ⋮ CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2) ⋮ Broadcasting secure messages via optimal independent spanning trees in folded hypercubes ⋮ Independent spanning trees on folded hyper-stars ⋮ On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\) ⋮ An improved algorithm to construct edge-independent spanning trees in augmented cubes ⋮ Constructing Node-Independent Spanning Trees in Augmented Cubes ⋮ Miscellaneous Digraph Classes ⋮ Independent spanning trees in crossed cubes

This page was built for publication: Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs