On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes

Baolei Cheng; Dajin Wang; Jianxi Fan; Xiaorui Li; Yan Wang

arxiv: 2401.01585 · v4 · submitted 2024-01-03 · 💻 cs.DC · cs.DM

On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes

Xiaorui Li , Baolei Cheng , Jianxi Fan , Yan Wang , Dajin Wang This is my paper

Pith reviewed 2026-05-24 04:21 UTC · model grok-4.3

classification 💻 cs.DC cs.DM

keywords locally twisted cubecompletely edge-independent spanning treesedge-disjoint spanning treesinterconnection networksnetwork broadcastingfault toleranceLTQ_nspanning trees

0 comments

The pith

The n-dimensional locally twisted cube admits floor(n/2) completely edge-independent spanning trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes that the maximum number of completely edge-independent spanning trees in the n-dimensional locally twisted cube LTQ_n is floor(n/2). It supplies an explicit algorithm that builds exactly floor(n/2) pairwise edge-disjoint spanning trees on the same vertex set. These trees supply multiple edge-disjoint routes between any pair of nodes, which supports simultaneous fault-tolerant transmission and parallel broadcasting. The authors verify the construction by implementation and compare broadcast latency when using the full set versus a single tree.

Core claim

In LTQ_n the largest possible collection of completely edge-independent spanning trees has size floor(n/2), and an algorithm exists that produces precisely that many trees whose edge sets are pairwise disjoint.

What carries the argument

Recursive construction algorithm that assigns edges from paired dimensions of the twisted-cube definition to separate spanning trees without overlap.

If this is right

Broadcasting latency drops when the floor(n/2) trees are used in parallel rather than a single tree.
The construction saturates the upper bound on the number of CEISTs.
Any two nodes remain connected by floor(n/2) edge-disjoint paths inside the chosen trees.
Network functions that rely on edge-disjoint routes, such as load-balanced routing, become feasible up to that multiplicity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same recursive pairing technique may extend to other hypercube variants whose edge rules preserve similar dimension independence.
The achieved multiplicity floor(n/2) supplies a concrete lower bound on the edge-connectivity usable for simultaneous message passing.
In a faulty LTQ_n the remaining trees continue to span after up to floor(n/2)-1 edge failures that hit distinct trees.

Load-bearing premise

The twisting rules that connect vertices across dimensions in LTQ_n leave enough unused edges at each recursive step to complete floor(n/2) edge-disjoint spanning trees.

What would settle it

An explicit listing, for some n greater than 2, of fewer than floor(n/2) pairwise edge-disjoint spanning trees in LTQ_n, or a proof that no larger set exists.

Figures

Figures reproduced from arXiv: 2401.01585 by Baolei Cheng, Dajin Wang, Jianxi Fan, Xiaorui Li, Yan Wang.

**Figure 2.** Figure 2: CEIST T1 in LT Q2. For n ≥ 3 and n is odd, LT Qn consists of two subcubes LT Q0 n−1 and LT Q1 n−1 , denoted by A and B. If there are ⌊ n 2 ⌋ CEISTs in A, we can construct ⌊ n 2 ⌋ CEISTs that are one-to-one isomorphic with ⌊ n 2 ⌋ trees of A in B accordingly. Then, for every two isomorphic trees in LT Qn, we expect to connect them through specific edges to obtain ⌊ n 2 ⌋ CEISTs in LT Qn. Based on the above … view at source ↗

**Figure 3.** Figure 3: CEIST T1 in LT Q3. For n ≥ 4 and n is even, LT Qn consists of four subcubes LT Q00 n−2 , LT Q10 n−2 , LT Q11 n−2 and LT Q01 n−2 , denoted by A, B, C and D, which have the common prefix 00, 10, 11 and 01, respectively. If there are n−2 2 CEISTs in A, we can construct n−2 2 CEISTs that are one-to-one isomorphic with n−2 2 trees of A in B accordingly, and so are C and D. Then, for every four isomorphic trees … view at source ↗

**Figure 4.** Figure 4: Two CEISTs T1 and T2 in LT Q5. Algorithm Even CEISTs Input: γA (n − 2) and PA : v 1 A -v 2 A -· · · -v n 2 A . (PA is constructed recursively by algorithm CEISTs LT Q). Output: γ (n), and P : v 1-v 2-· · · -v n 2 +1 . Begin Step 1. For 1 ≤ i ≤ n−2 2 , construct T B i , T C i , T D i , PB, PC, PD. 1: for i = 1 to n−2 2 do 2: Construct T B i , T C i , T D i by adding 2 n−1 , 3 ∗ 2 n−2 , 2 n−2 to each vertex … view at source ↗

**Figure 5.** Figure 5: Two CEISTs T1 and T2 in LT Q4. Example 2. By algorithm Even CEISTs, [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗

**Figure 6.** Figure 6: Three CEISTs T1, T2 and T3 in LT Q6 [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗

**Figure 7.** Figure 7: The topology of LT Qn. (a) T1 (b) T2 (c) T3 [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗

**Figure 8.** Figure 8: Three CEISTs in LT Q7 [PITH_FULL_IMAGE:figures/full_fig_p017_8.png] view at source ↗

**Figure 9.** Figure 9: Four CEISTs in LT Q8 [PITH_FULL_IMAGE:figures/full_fig_p018_9.png] view at source ↗

**Figure 10.** Figure 10: The comparisons of ABL and MBL between ⌊ n 2 ⌋ CEISTs and a single spanning tree [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗

read the original abstract

A network can contain numerous spanning trees. If two spanning trees $T_i,T_j$ do not share any common edges, $T_i$ and $T_j$ are said to be pairwisely edge-disjoint. For spanning trees $T_1, T_2, ..., T_m$, if every two of them are pairwisely edge-disjoint, they are called completely edge-independent spanning trees (CEISTs for short). CEISTs can facilitate many network functionalities, and constructing CEISTs as maximally allowed as possible in a given network is a worthy undertaking. In this paper, we establish the maximal number of CEISTs in the locally twisted cube network, and propose an algorithm to construct $\lfloor \frac{n}{2} \rfloor$ CEISTs in $LTQ_n$, the $n$-dimensional locally twisted cube. The proposed algorithm has been actually implemented, and we present the outputs. Network broadcasting in the $LTQ_n$ was simulated using $\lfloor\frac{n}{2}\rfloor$ CEISTs, and the performance compared with broadcasting using a single tree.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives an explicit floor(n/2) construction for CEISTs in LTQ_n plus working code and a broadcast simulation.

read the letter

The main thing to know is that this paper supplies a concrete algorithm to build floor(n/2) pairwise edge-disjoint spanning trees in the n-dimensional locally twisted cube and has actually run the code to produce examples, then tested broadcast performance against a single tree. The construction uses the recursive definition of LTQ_n and its twist edges, which fits the topology. The implementation and simulation outputs are the practical part that stands out for people who care about interconnection networks in distributed systems. That moves the work past a pure existence result and gives something others can check or extend. The bound itself is new for this specific graph family even if the general idea of edge-independent trees is older. The soft spot is the maximality argument. The abstract states floor(n/2) is the maximum, but the summary does not show the edge-counting or induction steps that would confirm why more trees cannot exist, so the upper bound is harder to assess without the full proof. The stress test saw no internal contradictions once the construction is in place, and the implementation adds some reproducibility. This paper is for specialists working on hypercube variants and network topologies for parallel machines. A reader focused on fault-tolerant routing or broadcasting in those graphs would find the explicit trees and the simulation useful. It deserves a serious referee because the claim is specific, the code is there, and the subfield values concrete constructions even if the proof details need checking.

Referee Report

2 major / 1 minor

Summary. The paper claims that the maximum number of completely edge-independent spanning trees (CEISTs) in the n-dimensional locally twisted cube LTQ_n is floor(n/2). It proposes and implements an algorithm to construct exactly this number of pairwise edge-disjoint spanning trees, presents the algorithm outputs, and simulates network broadcasting performance using floor(n/2) CEISTs versus a single spanning tree.

Significance. If the maximality claim and construction hold, the result supplies an explicit, linear-size set of edge-disjoint spanning trees for a standard hypercube variant used in interconnection networks, together with an implemented construction and a concrete broadcasting simulation; these elements directly support improved fault tolerance and communication primitives in distributed systems.

major comments (2)

[Abstract] Abstract: the assertion that floor(n/2) is both the maximal number and achievable via the proposed algorithm is stated without any proof sketch, edge-counting argument, or pointer to the section containing the upper-bound derivation; the maximality claim therefore cannot be checked against the manuscript's derivations.
[Construction section (presumed §3)] The recursive definition of LTQ_n and the inductive construction of the floor(n/2) CEISTs are invoked to support achievability, yet no inductive step, edge-disjointness verification, or spanning-tree coverage argument is visible; this leaves the central construction claim load-bearing but unverifiable from the supplied text.

minor comments (1)

[Abstract] The adverb 'pairwisely' (Abstract) is nonstandard; replace with 'pairwise'.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed comments on our manuscript. We address each major comment below and will make the indicated revisions to improve clarity and verifiability of the claims.

read point-by-point responses

Referee: [Abstract] Abstract: the assertion that floor(n/2) is both the maximal number and achievable via the proposed algorithm is stated without any proof sketch, edge-counting argument, or pointer to the section containing the upper-bound derivation; the maximality claim therefore cannot be checked against the manuscript's derivations.

Authors: We agree that the abstract lacks pointers to the relevant sections. In the revised version we will add explicit references to the section proving the upper bound (via edge-counting argument) and the section presenting the construction, so that the maximality claim can be directly located and verified. revision: yes
Referee: [Construction section (presumed §3)] The recursive definition of LTQ_n and the inductive construction of the floor(n/2) CEISTs are invoked to support achievability, yet no inductive step, edge-disjointness verification, or spanning-tree coverage argument is visible; this leaves the central construction claim load-bearing but unverifiable from the supplied text.

Authors: The manuscript contains a recursive definition of LTQ_n and an inductive construction in Section 3. However, we acknowledge that the inductive step, the explicit verification of pairwise edge-disjointness, and the argument that each constructed tree spans all vertices are not presented with sufficient detail or separation. We will revise Section 3 to include a clear inductive proof, a separate lemma establishing edge-disjointness, and a coverage argument for each tree. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes maximality of floor(n/2) CEISTs in LTQ_n and supplies an explicit construction algorithm based on the standard recursive definition of the locally twisted cube. No load-bearing step reduces a claimed result to a fitted parameter, self-citation chain, or definitional tautology; the argument proceeds by direct inductive construction on the graph's edge rules and is externally verifiable via the stated implementation and simulation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, background axioms, or newly postulated entities; the result rests on standard graph-theoretic definitions of spanning trees and the given recursive structure of LTQ_n.

pith-pipeline@v0.9.0 · 5739 in / 1062 out tokens · 24840 ms · 2026-05-24T04:21:14.691994+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We propose a recursive algorithm, named CEISTs LTQ, that constructs floor(n/2) CEISTs T1,... in the LTQn
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

LTQn is built from two disjoint copies of LTQn-1 ... connected by an edge where ui = vi and ui-1 = vi-1 ⊕ u0

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

Optimal broadcasting and personalized communication in hypercubes

Johnsson SL, Ho CT. Optimal broadcasting and personalized communication in hypercubes. IEEE Trans- actions on Computing, 1989, 38(9):1249-1268. doi:10.1109/12.29465

work page doi:10.1109/12.29465 1989
[2]

Edge-disjoint spanning trees on the star network with applications to fault toler- ance

Fragopoulou P, Akl SG. Edge-disjoint spanning trees on the star network with applications to fault toler- ance. IEEE Transactions on Computing, 1996, 45(2):174-185. doi:10.1109/12.485370

work page doi:10.1109/12.485370 1996
[3]

Reliable broadcasting and secure distributing in channel networks

Bao F, Funyu Y , Hamada Y , Igarashi Y . Reliable broadcasting and secure distributing in channel networks. Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN’97), 1997, pp. 472-478

work page 1997
[4]

Independent spanning trees in networks: A survey

Cheng B, Wang D, Fan J. Independent spanning trees in networks: A survey. ACM Computing Surveys, 2023, 55(14s):1-29. doi:10.1145/3591110

work page doi:10.1145/3591110 2023
[5]

A survey of the theory of hypercube graphs

Harary F, Hayes JP, Wu HJ. A survey of the theory of hypercube graphs. Computers & Mathematics with Applications, 1988, 15(4):277-289

work page 1988
[6]

Parallel construction of optimal independent spanning trees on hypercubes

Yang J-S, Tang S-M, Chang J-M, Wang Y-L. Parallel construction of optimal independent spanning trees on hypercubes. Parallel Computing, 2007, 33(1):73-79. doi:10.1016/j.parco.2006.12.001. 24 X. Li et al. / On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes

work page doi:10.1016/j.parco.2006.12.001 2007
[7]

Optimal independent spanning trees on hypercubes

Tang S-M, Wang Y-L, Leu Y . Optimal independent spanning trees on hypercubes. Journal of Information Science and Engineering, 2004, 20(1):143-155

work page 2004
[8]

On edge-disjoint spanning trees in hypercubes

Barden B, Libeskind-Hadas R, Davis J, Williams W. On edge-disjoint spanning trees in hypercubes. In- formation Processing Letters, 1999, 70(1):13-16. doi:10.1016/S0020-0190(99)00033-2

work page doi:10.1016/s0020-0190(99)00033-2 1999
[9]

Araya-Polo, J

Ku S-C, Wang B-E, Hung T-K. Constructing edge-disjoint spanning trees in product networks. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(3):213-221. doi:10.1109/TPDS. 2003.1189580

work page doi:10.1109/tpds 2003
[10]

Edge-disjoint spanning trees and forests of graphs

Zhou J, Bu C, Lai H-J. Edge-disjoint spanning trees and forests of graphs. Discrete Applied Mathematics, 2021, 299:74-81. doi:10.1016/j.dam.2021.04.024

work page doi:10.1016/j.dam.2021.04.024 2021
[11]

Edge-disjoint spanning trees for the generalized butterfly networks and their applications

Touzene A, Day K, Monien B. Edge-disjoint spanning trees for the generalized butterfly networks and their applications. Journal of Parallel and Distributed Computing, 2005, 65(11):1384-1396. doi:10.1016/j.jpdc.2005.05.009

work page doi:10.1016/j.jpdc.2005.05.009 2005
[12]

Distributed calculation of edge-disjoint spanning trees for robustify- ing distributed algorithms against Man-in-the-Middle attacks

Oliva G, Cioaba S, Hadjicosyis CN. Distributed calculation of edge-disjoint spanning trees for robustify- ing distributed algorithms against Man-in-the-Middle attacks. IEEE Transactions on Control of Network Systems, 2018, 5(4):1646-1656. doi:10.1109/TCNS.2017.2746344

work page doi:10.1109/tcns.2017.2746344 2018
[13]

Edge-disjoint spanning trees and the number of maximum state circles of a graph

Ma X, Wu B, Jin X. Edge-disjoint spanning trees and the number of maximum state circles of a graph. Journal of Combinatorial Optimization, 2018, 35(4):997-1008. doi:10.1007/s10878-018-0249-y

work page doi:10.1007/s10878-018-0249-y 2018
[14]

Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs

Gu X, Lai H-J, Li P, Yao S. Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs. Journal of Graph Theory, 2016, 81(1):16-29. doi:10.1002/jgt.21857

work page doi:10.1002/jgt.21857 2016
[15]

An algorithm to construct completely independent spanning trees in line graphs

Wang Y , Cheng B, Fan J, Qian Y , Jiang R. An algorithm to construct completely independent spanning trees in line graphs. The Computer Journal, 2022, 65(12):2979-2990. doi:10.1093/comjnl/bxab120

work page doi:10.1093/comjnl/bxab120 2022
[16]

An efficient fault-tolerant routing algorithm in bijective connection net- works with restricted faulty edges

Fan J, Jia X, Cheng B, Yu J. An efficient fault-tolerant routing algorithm in bijective connection net- works with restricted faulty edges. Theoretical Computer Science, 2011, 412(29):3440-3450. doi:10.1016/ j.tcs.2011.02.014

work page 2011
[17]

Dimensional-permutation-based independent spanning trees in bijective connection networks

Cheng B, Fan J, Jia K. Dimensional-permutation-based independent spanning trees in bijective connection networks. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(1):45-53. doi:10.1109/TPDS.2014.2307871

work page doi:10.1109/tpds.2014.2307871 2015
[18]

Constructing edge-disjoint spanning trees in several cube- based networks with applications to edge fault-tolerant communication

Zhang H, Wang Y , Fan J, Han Y , Cheng B. Constructing edge-disjoint spanning trees in several cube- based networks with applications to edge fault-tolerant communication. The Journal of Supercomputing, doi:10.1007/s11227-023-05546-z

work page doi:10.1007/s11227-023-05546-z
[19]

The locally twisted cubes

Yang X, Evans DJ, Megson GM. The locally twisted cubes. International Journal of Computer Mathemat- ics, 2005, 82(4):401-413. doi:10.1080/0020716042000301752

work page doi:10.1080/0020716042000301752 2005
[20]

Fault-free Hamiltonian cycles in locally twisted cubes under conditional edge faults

Hsieh S-Y , Wu C-Y , Lee C-W. Fault-free Hamiltonian cycles in locally twisted cubes under conditional edge faults. Proceedings of the 13th International Conference on Parallel and Distributed Systems, 2007, pp. 1-8

work page 2007
[21]

Constructing edge-disjoint spanning trees in locally twisted cubes

Hsieh S-Y , Tu C-J. Constructing edge-disjoint spanning trees in locally twisted cubes. Theoretical Com- puter Science, 2009, 410(8):926-932. doi:10.1016/j.tcs.2008.12.025

work page doi:10.1016/j.tcs.2008.12.025 2009
[22]

Independent spanning trees vs

Lin J-C, Yang J-S, Hsu C-C, Chang J-M. Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes. Information Processing Letters, 2010, 110(10):414-419. doi:10.1016/ j.ipl.2010.03.012. X. Li et al. / On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes 25

work page 2010
[23]

Three edge-disjoint Hamiltonian cycle in crossed cubes with applications to fault-tolerant data broadcasting

Pai K-J, Wu R-J, Peng S-L, Chang J-M. Three edge-disjoint Hamiltonian cycle in crossed cubes with applications to fault-tolerant data broadcasting. The Journal of Supercomputing, 2023, 79:4126-4145. doi:10.1007/s11227-022-04825-5

work page doi:10.1007/s11227-022-04825-5 2023
[24]

Constructive algorithm of independent spanning trees on M¨obius cubes

Cheng B, Fan J, Jia X, Zhang S, Chen B. Constructive algorithm of independent spanning trees on M¨obius cubes. The Compute Journal, 2013, 56(11):1347-1362. doi:10.1093/comjnl/bxs123

work page doi:10.1093/comjnl/bxs123 2013
[25]

Reliability assessment of the divide-and-swap cube in terms of generalized con- nectivity

Zhao S-L, Chang J-M. Reliability assessment of the divide-and-swap cube in terms of generalized con- nectivity. Theoretical Computer Science, 2023, 943:1-15. doi:10.1016/j.tcs.2022.12.005

work page doi:10.1016/j.tcs.2022.12.005 2023
[26]

Relationship between extra connectivity and component connectivity in networks

Li X, Lin C-K, Fan J, Jia X, Cheng B, Zhou J. Relationship between extra connectivity and component connectivity in networks. The Compute Journal, 2021, 833:41-55

work page 2021
[27]

Independent spanning trees vs

Lin J-C, Yang J-S, Hsu C-C, Chang J-M. Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes. Information Processing Letters, 2010, 110(10):414-419. doi:10.1016/ j.ipl.2010.03.012

work page 2010
[28]

BC interconnection networks and their properties

Fan J, He L. BC interconnection networks and their properties. Chinese Journal of Computers, 2003, 26(1):84-90. 26 X. Li et al. / On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes (a) T1 (b) T2 (c) T3 Figure 6. Three CEISTs T1, T2 and T3 in LT Q6. X. Li et al. / On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes 27...

work page 2003

[1] [1]

Optimal broadcasting and personalized communication in hypercubes

Johnsson SL, Ho CT. Optimal broadcasting and personalized communication in hypercubes. IEEE Trans- actions on Computing, 1989, 38(9):1249-1268. doi:10.1109/12.29465

work page doi:10.1109/12.29465 1989

[2] [2]

Edge-disjoint spanning trees on the star network with applications to fault toler- ance

Fragopoulou P, Akl SG. Edge-disjoint spanning trees on the star network with applications to fault toler- ance. IEEE Transactions on Computing, 1996, 45(2):174-185. doi:10.1109/12.485370

work page doi:10.1109/12.485370 1996

[3] [3]

Reliable broadcasting and secure distributing in channel networks

Bao F, Funyu Y , Hamada Y , Igarashi Y . Reliable broadcasting and secure distributing in channel networks. Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN’97), 1997, pp. 472-478

work page 1997

[4] [4]

Independent spanning trees in networks: A survey

Cheng B, Wang D, Fan J. Independent spanning trees in networks: A survey. ACM Computing Surveys, 2023, 55(14s):1-29. doi:10.1145/3591110

work page doi:10.1145/3591110 2023

[5] [5]

A survey of the theory of hypercube graphs

Harary F, Hayes JP, Wu HJ. A survey of the theory of hypercube graphs. Computers & Mathematics with Applications, 1988, 15(4):277-289

work page 1988

[6] [6]

Parallel construction of optimal independent spanning trees on hypercubes

Yang J-S, Tang S-M, Chang J-M, Wang Y-L. Parallel construction of optimal independent spanning trees on hypercubes. Parallel Computing, 2007, 33(1):73-79. doi:10.1016/j.parco.2006.12.001. 24 X. Li et al. / On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes

work page doi:10.1016/j.parco.2006.12.001 2007

[7] [7]

Optimal independent spanning trees on hypercubes

Tang S-M, Wang Y-L, Leu Y . Optimal independent spanning trees on hypercubes. Journal of Information Science and Engineering, 2004, 20(1):143-155

work page 2004

[8] [8]

On edge-disjoint spanning trees in hypercubes

Barden B, Libeskind-Hadas R, Davis J, Williams W. On edge-disjoint spanning trees in hypercubes. In- formation Processing Letters, 1999, 70(1):13-16. doi:10.1016/S0020-0190(99)00033-2

work page doi:10.1016/s0020-0190(99)00033-2 1999

[9] [9]

Araya-Polo, J

Ku S-C, Wang B-E, Hung T-K. Constructing edge-disjoint spanning trees in product networks. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(3):213-221. doi:10.1109/TPDS. 2003.1189580

work page doi:10.1109/tpds 2003

[10] [10]

Edge-disjoint spanning trees and forests of graphs

Zhou J, Bu C, Lai H-J. Edge-disjoint spanning trees and forests of graphs. Discrete Applied Mathematics, 2021, 299:74-81. doi:10.1016/j.dam.2021.04.024

work page doi:10.1016/j.dam.2021.04.024 2021

[11] [11]

Edge-disjoint spanning trees for the generalized butterfly networks and their applications

Touzene A, Day K, Monien B. Edge-disjoint spanning trees for the generalized butterfly networks and their applications. Journal of Parallel and Distributed Computing, 2005, 65(11):1384-1396. doi:10.1016/j.jpdc.2005.05.009

work page doi:10.1016/j.jpdc.2005.05.009 2005

[12] [12]

Distributed calculation of edge-disjoint spanning trees for robustify- ing distributed algorithms against Man-in-the-Middle attacks

Oliva G, Cioaba S, Hadjicosyis CN. Distributed calculation of edge-disjoint spanning trees for robustify- ing distributed algorithms against Man-in-the-Middle attacks. IEEE Transactions on Control of Network Systems, 2018, 5(4):1646-1656. doi:10.1109/TCNS.2017.2746344

work page doi:10.1109/tcns.2017.2746344 2018

[13] [13]

Edge-disjoint spanning trees and the number of maximum state circles of a graph

Ma X, Wu B, Jin X. Edge-disjoint spanning trees and the number of maximum state circles of a graph. Journal of Combinatorial Optimization, 2018, 35(4):997-1008. doi:10.1007/s10878-018-0249-y

work page doi:10.1007/s10878-018-0249-y 2018

[14] [14]

Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs

Gu X, Lai H-J, Li P, Yao S. Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs. Journal of Graph Theory, 2016, 81(1):16-29. doi:10.1002/jgt.21857

work page doi:10.1002/jgt.21857 2016

[15] [15]

An algorithm to construct completely independent spanning trees in line graphs

Wang Y , Cheng B, Fan J, Qian Y , Jiang R. An algorithm to construct completely independent spanning trees in line graphs. The Computer Journal, 2022, 65(12):2979-2990. doi:10.1093/comjnl/bxab120

work page doi:10.1093/comjnl/bxab120 2022

[16] [16]

An efficient fault-tolerant routing algorithm in bijective connection net- works with restricted faulty edges

Fan J, Jia X, Cheng B, Yu J. An efficient fault-tolerant routing algorithm in bijective connection net- works with restricted faulty edges. Theoretical Computer Science, 2011, 412(29):3440-3450. doi:10.1016/ j.tcs.2011.02.014

work page 2011

[17] [17]

Dimensional-permutation-based independent spanning trees in bijective connection networks

Cheng B, Fan J, Jia K. Dimensional-permutation-based independent spanning trees in bijective connection networks. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(1):45-53. doi:10.1109/TPDS.2014.2307871

work page doi:10.1109/tpds.2014.2307871 2015

[18] [18]

Constructing edge-disjoint spanning trees in several cube- based networks with applications to edge fault-tolerant communication

Zhang H, Wang Y , Fan J, Han Y , Cheng B. Constructing edge-disjoint spanning trees in several cube- based networks with applications to edge fault-tolerant communication. The Journal of Supercomputing, doi:10.1007/s11227-023-05546-z

work page doi:10.1007/s11227-023-05546-z

[19] [19]

The locally twisted cubes

Yang X, Evans DJ, Megson GM. The locally twisted cubes. International Journal of Computer Mathemat- ics, 2005, 82(4):401-413. doi:10.1080/0020716042000301752

work page doi:10.1080/0020716042000301752 2005

[20] [20]

Fault-free Hamiltonian cycles in locally twisted cubes under conditional edge faults

Hsieh S-Y , Wu C-Y , Lee C-W. Fault-free Hamiltonian cycles in locally twisted cubes under conditional edge faults. Proceedings of the 13th International Conference on Parallel and Distributed Systems, 2007, pp. 1-8

work page 2007

[21] [21]

Constructing edge-disjoint spanning trees in locally twisted cubes

Hsieh S-Y , Tu C-J. Constructing edge-disjoint spanning trees in locally twisted cubes. Theoretical Com- puter Science, 2009, 410(8):926-932. doi:10.1016/j.tcs.2008.12.025

work page doi:10.1016/j.tcs.2008.12.025 2009

[22] [22]

Independent spanning trees vs

Lin J-C, Yang J-S, Hsu C-C, Chang J-M. Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes. Information Processing Letters, 2010, 110(10):414-419. doi:10.1016/ j.ipl.2010.03.012. X. Li et al. / On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes 25

work page 2010

[23] [23]

Three edge-disjoint Hamiltonian cycle in crossed cubes with applications to fault-tolerant data broadcasting

Pai K-J, Wu R-J, Peng S-L, Chang J-M. Three edge-disjoint Hamiltonian cycle in crossed cubes with applications to fault-tolerant data broadcasting. The Journal of Supercomputing, 2023, 79:4126-4145. doi:10.1007/s11227-022-04825-5

work page doi:10.1007/s11227-022-04825-5 2023

[24] [24]

Constructive algorithm of independent spanning trees on M¨obius cubes

Cheng B, Fan J, Jia X, Zhang S, Chen B. Constructive algorithm of independent spanning trees on M¨obius cubes. The Compute Journal, 2013, 56(11):1347-1362. doi:10.1093/comjnl/bxs123

work page doi:10.1093/comjnl/bxs123 2013

[25] [25]

Reliability assessment of the divide-and-swap cube in terms of generalized con- nectivity

Zhao S-L, Chang J-M. Reliability assessment of the divide-and-swap cube in terms of generalized con- nectivity. Theoretical Computer Science, 2023, 943:1-15. doi:10.1016/j.tcs.2022.12.005

work page doi:10.1016/j.tcs.2022.12.005 2023

[26] [26]

Relationship between extra connectivity and component connectivity in networks

Li X, Lin C-K, Fan J, Jia X, Cheng B, Zhou J. Relationship between extra connectivity and component connectivity in networks. The Compute Journal, 2021, 833:41-55

work page 2021

[27] [27]

Independent spanning trees vs

Lin J-C, Yang J-S, Hsu C-C, Chang J-M. Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes. Information Processing Letters, 2010, 110(10):414-419. doi:10.1016/ j.ipl.2010.03.012

work page 2010

[28] [28]

BC interconnection networks and their properties

Fan J, He L. BC interconnection networks and their properties. Chinese Journal of Computers, 2003, 26(1):84-90. 26 X. Li et al. / On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes (a) T1 (b) T2 (c) T3 Figure 6. Three CEISTs T1, T2 and T3 in LT Q6. X. Li et al. / On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes 27...

work page 2003