Independent spanning trees with small depths in iterated line digraphs

DOI10.1016/S0166-218X(00)00269-9zbMath0983.05023OpenAlexW2063585532MaRDI QIDQ5936460

Hiroshi Nagamochi, Toru Hasunuma

Publication date: 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00269-9

zbMATH Keywords

line digraphindependent spanning trees

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items (22)

Improving the diameters of completely independent spanning trees in locally twisted cubes ⋮ Constructing two completely independent spanning trees in hypercube-variant networks ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ Two completely independent spanning trees of claw-free graphs ⋮ Ore's condition for completely independent spanning trees ⋮ Two completely independent spanning trees of split graphs ⋮ Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees ⋮ Two completely independent spanning trees of \(P_4\)-free graphs ⋮ Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes ⋮ Spanning trees: A survey ⋮ Independent spanning trees on twisted cubes ⋮ 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 ⋮ Structural properties of subdivided-line graphs ⋮ 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 ⋮ Constructing dual-CISTs with short diameters using a generic adjustment scheme on bicubes ⋮ On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\) ⋮ Miscellaneous Digraph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• The multi-tree approach to reliability in distributed networks
• On independent spanning trees
• A good algorithm for edge-disjoint branching
• On two minimax theorems in graph
• Independent trees in planar graphs
• Independent branchings in acyclic digraphs
• Independent trees in graphs
• Methods and problems of communication in usual networks
• A faster algorithm for finding edge-disjoint branchings
• A matroid approach to finding edge connectivity and packing arborescences
• Diameter vulnerability of iterated line digraphs
• On the diameter vulnerability of Kautz digraphs
• Line Digraph Iterations and the (d, k) Digraph Problem
• Three tree-paths
• Vertex-disjoint paths and edge-disjoint branchings in directed graphs
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Broadcasting and Gossiping in de Bruijn Networks
• Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs
• Counting small cycles in generalized de Bruijn digraphs
• Disproof of a conjecture about independent branchings in k‐connected directed graphs

This page was built for publication: Independent spanning trees with small depths in iterated line digraphs