On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\)

DOI10.1016/j.tcs.2008.12.042zbMath1168.68037OpenAlexW2011353132MaRDI QIDQ1019176

Shyue-Ming Tang, Jinn-Shyong Yang, Jou-Ming Chang, Yue-Li Wang

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.042

zbMATH Keywords

independent spanning treesfault-tolerant broadcastinginternally disjoint pathsrecursive circulant graphssecure message distribution

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

Construction independent spanning trees on locally twisted cubes in parallel ⋮ Constructing edge-disjoint spanning trees in twisted cubes ⋮ A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks ⋮ Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs ⋮ Disjoint path covers in recursive circulants \(G(2^m,4)\) with faulty elements ⋮ Conditional diagnosability of matching composition networks under the \(\mathrm{MM}^\ast\) model ⋮ 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 ⋮ Edge-independent spanning trees in augmented 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 ⋮ An improved algorithm to construct edge-independent spanning trees in augmented cubes ⋮ Linear time algorithms for finding independent spanning trees on pyramid networks ⋮ Constructing Node-Independent Spanning Trees in Augmented Cubes ⋮ Independent spanning trees in crossed cubes

Cites Work

• Unnamed Item
• Unnamed Item
• Disjoint Hamiltonian cycles in recursive circulant graphs
• Independent spanning trees of chordal rings
• Edge-pancyclicity of recursive circulants
• Maximum induced subgraph of a recursive circulant
• The multi-tree approach to reliability in distributed networks
• Multiplicative circulant networks. Topological properties and communication algorithms
• Recursive circulants and their embeddings among hypercubes
• Pancyclicity of recursive circulant graphs
• Embedding trees in recursive circulants
• Hamiltonian decomposition of recursive circulant graphs
• The super-connected property of recursive circulant graphs
• Panconnectivity and edge-pancyclicity of faulty recursive circulant \(G(2^m,4)\)
• Application of the special Latin square to a parallel routing algorithm on a recursive circulant network.
• Three tree-paths
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs
• Finding Four Independent Trees
• Independent spanning trees with small depths in iterated line digraphs

This page was built for publication: On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\)