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

Abstract 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.

• Publication year

  2000

• Venue

  Discrete Mathematics

• Publication date

  2000-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0012-365X(00)00377-0
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Embedding iterated line digraphs in books

  2002cited by this paper
• Submodular Functions, Matroids, and Certain Polyhedra

  2001cited by this paper
• Independent spanning trees with small depths in iterated line digraphs

  2001cited by this paper
• Independent Trees in Planar Graphs Independent trees

  1999cited by this paper
• Independent branchings in acyclic diagraphs

  1999cited by this paper
• On Edge-Disjoint Spanning Trees in Hypercubes

  1999cited by this paper
• Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs

  1997cited by this paper
• Independent Spanning Trees of Chordal Rings

  1997cited by this paper
• Independent Spanning Trees of Product Graphs and Their Construction

  1996cited by this paper
• Three tree-paths

  1989cited by this paper
• Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs

  1988cited by this paper
• Vertex-disjoint paths and edge-disjoint branchings in directed graphs

  1987cited by this paper
• The Multi-Tree Approach to Reliability in Distributed Networks

  1984cited by this paper
• Line digraph iterations and the (d,k) problem for directed graphs

  1983influential reference

• Completely independent spanning trees in the line graph of complete multipartite graphs

  2026cites this paper
• The existence condition of k completely independent spanning tree for some graphs

  2026cites this paper
• DACS: Distributed adjustable computation scheme in highly scalable data center networks based on multi-protection routing

  2026cites this paper
• Completely independent Steiner trees and corresponding tree connectivity

  2025cites this paper
• Completely Independent Spanning Trees in Folded Hypercube-Variant Networks

  2025cites this paper
• Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity

  2025cites this paper
• Parallel construction of multiple independent spanning trees on 3-ary n -cube networks

  2025cites this paper
• The completely independent spanning trees in P4-free graphs

  2025cites this paper
• Completely independent spanning trees in kth power of 2-connected graphs

  2025cites this paper
• Reliable Communication Scheme Based on Completely Independent Spanning Trees in Data Center Networks

  2025cites this paper
• Completely Independent Spanning Trees in the Line Graphs of Complete Bipartite Graphs

  2025cites this paper
• Exponentiation of Graphs

  2025cites this paper
• Every 2-connected {claw, Z2}-free graph with minimum degree at least 4 contains two CISTs

  2025cites this paper
• A Note on the 4-Connected Line Graph of a Planar Triangulation Containing Two CISTs

  2025cites this paper
• Fan-type condition for two completely independent spanning trees

  2025cites this paper
• Completely independent spanning trees in the hypercube

  2024cites this paper
• Construction and Conditions for Completely Independent Spanning Trees in Hypercubes and Regular Bipartite Graphs

  2024influential citation
• Two Completely Independent Spanning Trees of $$P_4$$ P 4 -Free Graphs

  2023cites this paper
• Dual Protection Routing Trees on Graphs

  2023cites this paper
• Two completely independent spanning trees of split graphs

  2023cites this paper
• Independent Spanning Trees in Networks: A Survey

  2023influential citation
• Constructing Multiple CISTs on BCube-Based Data Center Networks in the Occurrence of Switch Failures

  2023cites this paper
• A High-Performantal and Server-Centric Based Data Center Network

  2023cites this paper
• Degree Conditions for Completely Independent Spanning Trees of Bipartite Graphs

  2022cites this paper
• Constructing tri-CISTs in shuffle-cubes

  2022cites this paper
• Two completely independent spanning trees of claw-free graphs

  2022cites this paper
• Completely Independent Spanning Trees in Line Graphs

  2022cites this paper
• Reliability analysis based on the dual-CIST in shuffle-cubes. (English)

  2022cites this paper
• An Algorithm to Construct Completely Independent Spanning Trees in Line Graphs

  2021cites this paper
• Reliability analysis based on the dual-CIST in shuffle-cubes

  2021cites this paper
• New comments on "A Hamilton sufficient condition for completely independent spanning tree"

  2021cites this paper
• Augmenting a Tree to a k-Arbor-Connected Graph with Pagenumber k

  2021cites this paper
• Constructing Completely Independent Spanning Trees in Data Center Network Based on Augmented Cube

  2021cites this paper
• Constructing dual-CISTs with short diameters using a generic adjustment scheme on bicubes

  2021cites this paper
• Transmission Failure Analysis of Multi-Protection Routing in Data Center Networks With Heterogeneous Edge-Core Servers

  2021cites this paper
• Completely Independent Spanning Trees on BCCC Data Center Networks with an Application to Fault-Tolerant Routing

  2021cites this paper
• Construction of Dual-CISTs on an Infinite Class of Networks

  2021cites this paper
• A Hamilton sufficient condition for completely independent spanning tree

  2020cites this paper
• Construction of Completely Independent Spanning Tree Based on Vertex Degree

  2020cites this paper
• Constructing dual-CISTs of folded divide-and-swap cubes

  2020cites this paper
• Constructing dual-CISTs of pancake graphs and performance assessment of protection routings on some Cayley networks

  2020cites this paper
• The Existence of Completely Independent Spanning Trees for Some Compound Graphs

  2020cites this paper
• A protection routing with secure mechanism in Möbius cubes

  2020cites this paper
• Constructing Two Completely Independent Spanning Trees in Balanced Hypercubes

  2019cites this paper
• Improving the diameters of completely independent spanning trees in locally twisted cubes

  2019cites this paper
• Constructing Three Completely Independent Spanning Trees in Locally Twisted Cubes

  2019cites this paper
• A two-stages tree-searching algorithm for finding three completely independent spanning trees

  2019cites this paper
• Dual-CISTs: Configuring a Protection Routing on Some Cayley Networks

  2019influential citation
• Constructing dual-CISTs of DCell data center networks

  2019cites this paper
• Three Completely Independent Spanning Trees of Crossed Cubes with Application to Secure-Protection Routing

  2019cites this paper
• A well-equalized 3-CIST partition of alternating group graphs

  2019cites this paper
• Designing an Algorithm to Improve the Diameters of Completely Independent Spanning Trees in Crossed Cubes

  2018cites this paper
• Completely Independent Spanning Trees in k-Th Power of Graphs

  2018cites this paper
• Constructing spanning trees in augmented cubes

  2018cites this paper
• Constructing completely independent spanning trees in crossed cubes

  2017cites this paper
• Completely Independent Spanning Trees on 4-Regular Chordal Rings

  2017cites this paper
• Construction of Four Completely Independent Spanning Trees on Augmented Cubes

  2017influential citation
• Almost disjoint spanning trees: Relaxing the conditions for completely independent spanning trees

  2017cites this paper
• Completely independent spanning trees for enhancing the robustness in ad-hoc Networks

  2017influential citation
• Toward the completely independent spanning trees problem on BCube

  2017cites this paper
• Almost disjoint spanning trees

  2016cites this paper
• Degree condition for completely independent spanning trees

  2016cites this paper
• Constructing two completely independent spanning trees in hypercube-variant networks

  2016cites this paper
• A Reliable Broadcasting Algorithm in Locally Twisted Cubes

  2015cites this paper
• Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees

  2015cites this paper
• Completely Independent Spanning Trees in (Partial) k-Trees

  2015influential citation
• A Note on the Degree Condition of Completely Independent Spanning Trees

  2015cites this paper
• Dirac's Condition for Completely Independent Spanning Trees

  2014influential citation
• Ore's condition for completely independent spanning trees

  2014cites this paper
• Completely independent spanning trees in some regular graphs

  2014influential citation
• Finding Totally Independent Spanning Trees with Linear Integer Programming

  2014cites this paper
• Recherche d'arbres couvrants complètement indépendants dans des graphes réguliers

  2014cites this paper
• Connecting Vertices by Independent Trees

  2014cites this paper
• Completely Independent Spanning Trees in Some Regular Graphs

  2014influential citation
• Completely Independent Spanning Trees on Some Interconnection Networks

  2014influential citation
• Structural properties of subdivided-line graphs

  2013cites this paper
• Completely Independent Spanning Trees on Complete Graphs, Complete Bipartite Graphs and Complete Tripartite Graphs

  2013influential citation
• Two counterexamples on completely independent spanning trees

  2012cites this paper
• Completely independent spanning trees in torus networks

  2012cites this paper
• Sufficient conditions for protection routing in IP networks

  2012influential citation
• Multisource Broadcasting on de Bruijn and Kautz Digraphs Using Isomorphic Factorizations into Cycle-Rooted Trees

  2009cites this paper
• Broadcasting Multiple Messages Using Cycle-Rooted Trees

  2009cites this paper
• On the k-tuple domination of de Bruijn and Kautz digraphs

  2007cites this paper
• Completely Independent Spanning Trees in Maximal Planar Graphs

  2002cites this paper
• Factorization of de Bruijn digraphs by cycle-rooted trees

  2001cites this paper
• MINIMAL GRAPHS FOR COMPLETELY INDEPENDENT SPANNING TREES AND COMPLETELY INDEPENDENT SPANNING TREES IN COMPLETE T -PARTITE GRAPH

  year unknowninfluential citation
• ( 𝒕, 𝒔 ) -completely Independent Spanning Trees

  year unknowncites this paper