Completely independent spanning trees in some regular graphs

DOI10.1016/J.DAM.2016.09.007zbMath1358.05053arXiv1409.6002OpenAlexW2962923546MaRDI QIDQ516807

Benoit Darties, Nicolas Gastineau, Olivier Togni

Publication date: 15 March 2017

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

Full work available at URL: https://arxiv.org/abs/1409.6002

zbMATH Keywords

spanning treeCartesian productcompletely independent spanning tree

Mathematics Subject Classification ID

Trees (05C05) Graph operations (line graphs, products, etc.) (05C76)

Related Items (10)

Improving the diameters of completely independent spanning trees in locally twisted cubes ⋮ Constructing completely independent spanning trees in crossed cubes ⋮ A well-equalized 3-CIST partition of alternating group graphs ⋮ Constructing dual-CISTs of DCell data center networks ⋮ Constructing tri-CISTs in shuffle-cubes ⋮ Constructing tri-CISTs in shuffle-cubes ⋮ Three completely independent spanning trees of crossed cubes with application to secure-protection routing ⋮ A two-stages tree-searching algorithm for finding three completely independent spanning trees ⋮ Degree conditions for completely independent spanning trees of bipartite graphs ⋮ Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)

Cites Work

• Unnamed Item
• Unnamed Item
• Independent spanning trees of chordal rings
• Ore's condition for completely independent spanning trees
• Two counterexamples on completely independent spanning trees
• Approximation algorithms for connected dominating sets
• Edge-disjoint trees containing some given vertices in a graph
• On edge-disjoint spanning trees in hypercubes
• Completely independent spanning trees in (partial) \(k\)-trees
• Degree condition for completely independent spanning trees
• Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees
• Dirac's Condition for Completely Independent Spanning Trees
• Connected Domatic Number in Planar Graphs
• Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs
• Completely independent spanning trees in torus networks
• Completely independent spanning trees in the underlying graph of a line digraph
• Independent spanning trees with small depths in iterated line digraphs
• Multicast in wormhole-switched torus networks using edge-disjoint spanning trees.

This page was built for publication: Completely independent spanning trees in some regular graphs