Next Article in Journal
Complementary Gamma Zero-Truncated Poisson Distribution and Its Application
Next Article in Special Issue
The Diagnosability of the Generalized Cartesian Product of Networks
Previous Article in Journal
Traveling Wave Optical Solutions for the Generalized Fractional Kundu–Mukherjee–Naskar (gFKMN) Model
Previous Article in Special Issue
All-to-All Broadcast Algorithm in Galaxyfly Networks
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Super Spanning Connectivity of the Folded Divide-and-SwapCube

1
School of Information Engineering, Suzhou Industrial Park Institute of Services Outsourcing, Suzhou 215123, China
2
Suzhou Industrial Park Human Resources Development Co., Ltd., Suzhou 215005, China
3
Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, Suzhou 215006, China
4
School of Computer Science and Technology, Soochow University, Suzhou 215006, China
*
Author to whom correspondence should be addressed.
Submission received: 21 April 2023 / Revised: 31 May 2023 / Accepted: 1 June 2023 / Published: 5 June 2023
(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

Abstract

:
A k * -container of a graph G is a set of k disjoint paths between any pair of nodes whose union covers all nodes of G. The spanning connectivity of G, κ * ( G ) , is the largest k, such that there exists a j * -container between any pair of nodes of G for all 1 j k . If κ * ( G ) = κ ( G ) , then G is super spanning connected. Spanning connectivity is an important property to measure the fault tolerance of an interconnection network. The divide-and-swap cube D S C n is a newly proposed hypercube variant, which reduces the network cost from O ( n 2 ) to O ( n log 2 n ) compared with the hypercube and other hypercube variants. The folded divide-and-swap cube F D S C n is proposed based on D S C n to reduce the diameter of D S C n . Both D S C n and F D S C n possess many better properties than hypercubes. In this paper, we investigate the super spanning connectivity of F D S C n where n = 2 d and d 1 . We show that κ * ( F D S C n ) = κ ( F D S C n ) = d + 2 , which means there exists an m-DPC(node-disjoint path cover) between any pair of nodes in F D S C n for all 1 m d + 2 .

1. Introduction

In a parallel computer system, the interconnection network determines the performance of the system. Generally, an interconnection network is denoted by G = ( V ( G ) , E ( G ) ) , where E ( G ) is the edge set and V ( G ) is the node set. We say that two nodes x V ( G ) and y V ( G ) are adjacent if ( x , y ) E ( G ) . A path P is a sequence of n nodes in G, denoted by υ 1 , υ 2 , , υ n where ( υ i , υ i + 1 ) E ( G ) with 1 i n 1 . If the endpoints υ 1 and υ n are the same, then P is a cycle. A Hamiltonian path consists of all the nodes in G. A Hamiltonian cycle traverses all nodes of G exactly once. G is Hamiltonian connected if and only if there exists a Hamiltonian path connecting any two nodes of G, and G is Hamiltonian if there exists a Hamiltonian cycle in G. Two paths between a and b are node-disjoint if they do not have common nodes except a and b.
Let κ ( G ) be the connectivity of G. From Menger’s theorem, there exist k node-disjoint paths between any pair of nodes a and b in G if k κ ( G ) . The node-disjoint path problem has been studied for many networks, such as alternating group networks [1], balanced hypercubes [2], DCell networks [3], and so on. A set of k node-disjoint paths between a and b is called a k-container, denoted by C ( a , b ) . C ( a , b ) is called a spanning k-container, denoted by k * -container, if it covers all nodes of G. A k * -container is also known as a one-to-one disjoint path cover (DPC for short) of G. A disjoint path cover problem of G is to find node-disjoint paths between any two distinct nodes whose union covers all nodes of G [4]. If any two nodes have a k * -container between them, then G is said to be k * -connected. Obviously, if G is Hamiltonian-connected, it is 1 * -connected, and if G is Hamiltonian, then it is 2 * -connected. The spanning connectivity of a graph G, denoted by κ * ( G ) , is the largest k such that G is j * -connected for all 1 j k . If κ * ( G ) = κ ( G ) , then G is super spanning connected.
It is important to study the node-disjoint path problem between any pair of distinct nodes [5,6]. Disjoint paths between nodes can be used to accelerate data transmission by allocating data to different communication paths [7]. Other advantages of adopting such a node-disjoint routing scheme are the improved robustness to node failures, as well as the improved load balancing capability [8,9]. Software testing is another well-known application of multiple disjoint path covers [10]. Node-disjoint path cover or spanning connectivity is an important property to measure the fault tolerance of a network, which has been studied for many networks, such as hypercube-like networks [11], alternating group graphs [12], multi-dimensional toris [13], DCell networks [14], WK-recursive networks [15], generalized Petersen graphs [16], split-star networks [17], and so on.
The n-dimensional divide-and-swap cube, denoted by D S C n ( n = 2 d , d 1 ), was proposed by Kim et al. in [18] as a hypercube variant. Compared with a hypercube, D S C n reduces the network cost from O ( n 2 ) to O ( n log 2 n ) . Moreover, D S C n possesses many other attractive properties. The diameter upper bound of D S C n is 5 n 4 1 and the degree is log 2 n + 1 . D S C n is Hamiltonian and Hamiltonian-connected. In [19], Ning has shown that the connectivity and edge connectivity are both log 2 n + 1 , and the super connectivity and super edge connectivity are both log 2 n 2 . In [20], Zhou et al. studied the 𝘍 -structure connectivity and 𝘍 -substructure connectivity for 𝘍 { K 1 , K 1 , 1 , K 1 , i ( 2 i d + 1 ) , C 4 } . In [21], Zhou et al. showed that the component connectivity c κ r + 1 ( D S C n ) = ( d 1 ) r + 2 and the diagnosability c t r + 1 ( D S C n ) = ( d 1 ) r + d + 1 for 1 r d 1 , d 3 . In [22], Zhao et al. investigated the generalized connectivity κ 4 ( D S C n ) = d for d 1 . The n-dimensional folded divide-and-swap cube, F D S C n ( n = 2 d , d 1 ), was also proposed in [18]. F D S C n is constructed based on D S C n by adding one edge to each node of D S C n . Obviously, the connectivity of F D S C n is log 2 n + 2 = d + 2 [23]. In addition, the diameter upper bound of F D S C n is n 1 and the network cost is O ( n log 2 n ) . F D S C n is also Hamiltonian and Hamiltonian-connected. F D S C n is appropriate as a candidate topology for a data center network. In [24], Chang et al. constructed the dual-CIST for F D S C n . In [23], Zhao and Chang investigated the connectivity, super connectivity and generalized 3-connectivity of F D S C n . We can see that D S C n and F D S C n have many better properties than the hypercube.
In this work, we investigated the super spanning connectivity of F D S C n with n = 2 d and d 1 . We show that there exists an m-DPC between any pair of nodes in F D S C n for all 1 m κ ( F D S C n ) . The remainder of the paper is structured as follows. We formally define D S C n and F D S C n In Section 2, and then provide two basic properties of F D S C n . The proof of super spanning connectivity of F D S C n is given in Section 3. Finally, we summarize the paper.

2. Preliminaries

In this section, we give the formal definition of D S C n and F D S C n . Each node u in D S C n is denoted by an n-bit binary string, where u = x 1 x 2 x n and x i { 0 , 1 } for 1 i n . D S C n is defined as follows.
Definition 1
([18]). For n = 2 d and d 1 , D S C n has 2 n nodes, each of which is represented by an n-bit binary string, where u = x 1 x 2 x n = s 1 s 2 s 3 and x i { 0 , 1 } for 1 i n . For each k with 1 k d , s 1 = x 1 x 2 x n 2 k , s 2 = x n 2 k + 1 x n 2 k + 2 x n 2 k 1 and s 3 = x n 2 k 1 + 1 x n 2 k 1 + 2 x n 2 k 2 . If k = 1 , then u = s 1 s 2 and s 3 is empty. If node v satisfies one of the following conditions, then ( u , v ) E ( D S C n ) .
(1) 
v = x ¯ 1 x 2 x n , where x ¯ 1 is the complement of x 1 . Here, ( u , v ) is called an e ( 1 ) -edge.
(2) 
s ¯ 1 s ¯ 2 s 3   i f   s 1 = s 2 , s 2 s 1 s 3   i f   s 1 s 2 Here, ( u , v ) is called an e ( 2 n 2 k ) -edge.
D S C 2 and D S C 4 are shown in Figure 1. For any integer n with n = 2 d and d 1 , F D S C n is built based on D S C n by adding an edge to each node of D S C n .
Definition 2
([18]).  V ( F D S C n ) = V ( D S C n ) , E ( F D S C n ) = E ( D S C n ) E f , where E f = { ( u , v ) | u = x 1 x 2 x n and v = x 1 x ¯ 2 x n } . An edge in E f is called an e ( f ) -edge.
F D S C n can be divided into 2 n 2 F D S C n 2 , each of which is represented by F D S C n 2 i or F D S C 2 d 1 i , with 0 i 2 n 2 1 . We call F D S C 2 d 1 i a module of F D S C n . Let u = x 1 x 2 x n = A B be any node in F D S C n . We have A = x 1 x 2 x n 2 is the local address in the module and B = x n 2 + 1 x n 2 + 2 x n is the module address. Then, a F D S C 2 d 1 module can also be represented by D B . For example, node 0100 is in D 00 (or D 0 with decimal representation) and node 1111 is in D 11 (or D 3 with decimal representation) in F D S C 4 (see Figure 2).
Property 1
([18]). For modules D B i and D B j with i j , if B i = B ¯ j , then there are two edges, ( B i B i , B j B j ) and ( B j B i , B i B j ) , between D B i and D B j ; otherwise, there exists only one edge, ( B j B i , B i B j ) , between D B i and D B j .
For example, modules D 00 and D 11 are connected by two edges ( 0000 , 1111 ) and ( 1100 , 0011 ) in F D S C 4 , where B i = 00 and B j = 11 . Modules D 00 and D 01 are connected by one edge, ( 0100 , 0001 ) in F D S C 4 , where B i = 00 and B j = 01 . If k = 1 , then u = s 1 s 2 = A B is in D s 2 . By Definition 1, ( 0000 , 1111 ) , ( 1100 , 0011 ) , and ( 0100 , 0001 ) are all e ( n ) -edges with n = 4 . An e ( n ) -edge of node u is denoted by e n u , which is an external edge of u. Obviously, each module has only one node u 1 = s 1 s 2 with s 1 = s 2 . Let u 2 = s ¯ 1 s 2 and S = V ( D s 2 ) { u 1 } . Since each node in the same module has the same module address and the different local address, then each node in S is connected to a different module of F D S C n and u 2 is connected to s 2 s ¯ 1 in module D s ¯ 1 . Since u 1 is connected to node s ¯ 1 s ¯ 2 = s ¯ 1 s ¯ 1 , then u 1 and u 2 are both connected to module D s ¯ 1 . Let h = 2 n 2 . According to Property 1, we have the following property.
Property 2.
Let D 0 , D 1 , , D h 1 be the h modules of F D S C n each of which has h nodes. Let u = s 1 s 2 be the node with s 1 = s 2 in D i with 0 i h 1 . Then each node in V ( D i ) { u } is connected to a different D j with 0 i j h 1 with an e ( n ) -edge. Let v = s ¯ 1 s 2 . Then both u and v are connected to D s ¯ 1 with an e ( n ) -edge.
If the local addresses of two nodes u and v are complemented, e n u and e n v are connected to the same module of F D S C n .

3. The Super Spanning Connectivity of FDSC n

In this section, we will give some terminologies of D S C n and F D S C n . We list some symbols in Table 1. Throughout this paper, let h = 2 n 2 .
Lemma 1
([18]).  D S C n is Hamiltonian-connected for n = 2 d and d 1 .
Lemma 2
([18]).  D S C n is Hamiltonian for n = 2 d and d 1 .
Based on the definition of F D S C n , we have two lemmas below.
Lemma 3.
F D S C n is Hamiltonian-connected for n = 2 d and d 1 .
Lemma 4
([18]).  F D S C n is Hamiltonian for n = 2 d and d 1 .
By Lemmas 3 and 4, we have Lemma 5.
Lemma 5.
For any integer n with n = 2 d and d 1 , there is a 1-DPC and a 2-DPC between any pair of nodes μ and ν.
Lemma 6.
Given F D S C n and its h modules D 0 , D 1 , , D h 1 where n = 2 d and d 2 , let T = i = 1 r D B i where 2 r h 1 and 0 B i h 1 , which consists of r modules and the e ( n ) -edges between them. If u and v are two nodes in different modules of T with e n u , e n v E ( T ) , then there exists a Hamiltonian path between u and v, which covers all the nodes of T.
Proof. 
We present the cases as follows.
Case 1. r = 2 .
Suppose u V ( D B 1 ) and v V ( D B 2 ) . Since e n u , e n v E ( T ) , by Property 2, we can find a node x V ( D B 1 ) u and a node y V ( D B 2 ) v such that ( x , y ) E ( T ) . Since D B 1 and D B 2 are both Hamiltonian-connected, there exists a Hamiltonian path u , P 1 , x in D B 1 and a Hamiltonian path y , P 2 , v in D B 2 . Combining the paths constructed above, we obtain the required Hamiltonian path S = u , P 1 , x , y , P 2 , v .
Case 2. r 3 .
Suppose u V ( D B 2 ) and v V ( D B 1 ) . For each module D B j with 3 j r 1 , we can find two nodes x j and y j such that x j is connected to y j 1 in D B j 1 and y j is connected to x j + 1 in D B j + 1 . For module D B r , we can find two nodes, x r and y r , such that y r is connected to x 1 in D B 1 . Hence, we can construct the required Hamiltonian path, S = u , P 2 , y 2 , x 3 , P 3 , y 3 , , x r , P r , y r , x 1 , P 1 , v (see Figure 3). □
Lemma 7.
Given F D S C n and its h modules D 0 , D 1 , , D h 1 , where n = 2 d and d 2 , let T = i = 1 r D B i , where h 2 < r h 1 and 0 B i h 1 , which consists of r modules and the e ( n ) -edges between them. If u and v are two nodes in the same module of T with e n u , e n v E ( T ) , then there exists a Hamiltonian path between u and v, which covers all the nodes of T.
Proof. 
Suppose u , v V ( D B 1 ) . Since r > h 2 and e n u , e n v E ( T ) , by Property 2, we can build a Hamiltonian path u , P 0 , x , y , P 1 , v in D B 1 such that x and y are connected to different modules of T and ( x , y ) E ( T ) . Suppose x is connected to x in D B i and y is connected to y in D B j , where 2 i j r . By Lemma 6, there is a Hamiltonian path x , S , y , which covers all the nodes of V ( T ) V ( D B 1 ) . Combining the paths constructed above, we obtain the required Hamiltonian path, S = u , P 0 , x , x , S , y , y , P 1 , v (see Figure 4). □
Lemma 8.
Let μ be any node in F D S C 4 . We can find a node set T = { t i | 1 i r } with 1 r 4 such that there exists a one-to-many node disjoint path cover between μ and T in F D S C 4 and the node labels in T + { μ } are not complementary with each other.
Proof. 
For r = 1 , since F D S C 4 is Hamiltonian connected, it is easy to construct a one-to-many node disjoint path cover between μ and T = { t 1 } in F D S C 4 where t 1 is not complementary with μ . For 2 r 4 , W.L.O.G., suppose μ is in D 0 . Let T 0 = { t i | 1 i m , t i V ( D 0 ) } where 1 m 3 . It is obvious the node labels are not complementary with each other in T 0 + { μ } . Since D 0 is a complete graph with four nodes, then there is a one-to-many node disjoint path cover between μ and T 0 in D 0 . Suppose μ is connected to x in D i with 1 i 3 . We can find at least one node y V ( D j ) , of which the label is not complementary with those in T 0 + { μ } , where 1 i j 3 . By Lemma 6, there exists a Hamiltonian path between x and y, which covers all the nodes of V ( F D S C 4 ) V ( D 0 ) . Hence, T = T 0 + { y } is the required node set for 2 r 4 . □
Lemma 9.
Let μ be any node in F D S C n for d 2 and n = 2 d . We can find a node set T = { t i | 1 i r } with 1 r d + 2 , such that there exists a one-to-many node disjoint path cover between μ and T in F D S C n and the node labels are not complementary with each other in T + { μ } .
Proof. 
To prove this lemma, we proceed by induction on d. According to Lemma 8, this lemma holds for d = 2 and n = 4 . Suppose that this lemma holds for F D S C 2 d 1 for d 3 , we will prove that this lemma holds for F D S C 2 d .
For r = 1 , it is easy to find a node set T = { t 1 } to meet the condition this lemma holds. For 2 r d + 2 , W.L.O.G., suppose μ is in D 0 . According to the hypothesis, there is a one-to-many node disjoint path cover between μ and T 0 = { t i | 1 i m } in D 0 where 1 m d + 1 . Suppose that μ is connected to x in D i with 1 i h 1 . Let y be any vertex in D j where 1 i j h 1 and y is not complementary with each node in T 0 + { μ } . By Lemma 6, we can construct a path between x and y covering all the nodes of V ( F D S C n ) V ( D 0 ) . Hence, T = T 0 { y } is the required node set for 2 r d + 2 (see Figure 5). □
Lemma 10.
Let μ and ν be any two nodes in F D S C n for integer d { 1 , 2 } and n = 2 d . There exists an m-DPC between μ and ν in F D S C n where 1 m d + 2 .
Proof. 
By Lemma 5, there exists an m-DPC between μ and ν in F D S C n for 1 m 2 . For d = 1 and n = 2 , F D S C 2 is a complete graph. Obviously, there exists a 3-DPC between any two distinct nodes in F D S C 2 . For F D S C 4 , we need to prove there exists an m-DPC between μ and ν for 3 m 4 . We consider the following three cases.
Case 1. μ , ν V ( D i ) where 0 i 3 .
Suppose that μ , ν V ( D 0 ) . Since D 0 is a complete graph, there exists an m-DPC between μ and ν in D 0 with 2 m 3 .
Case 1.1. e 4 μ and e 4 ν are connected to the same D j with 1 j 3 .
Suppose that μ is connected to x and ν is connected to y in D j . By Lemma 7, there exists a ( x , y ) -Hamiltonian path covering all the nodes of V ( F D S C 4 ) V ( D 0 ) . Hence, there exists a ( m + 1 ) -DPC between μ and ν where 3 m + 1 4 .
Case 1.2. e 4 μ is connected to D j and e 4 ν is connected to D k with 1 j k 3 .
Suppose that μ is connected to x in D j and ν is connected to y in D k . By Lemma 6, there exists a ( x , y ) -Hamiltonian path covering all the nodes of V ( F D S C 4 ) V ( D 0 ) . Hence, there exists a ( m + 1 ) -DPC between μ and ν where 3 m + 1 4 .
Case 2. μ V ( D i ) and ν V ( D j ) and D i and D j are connected with two e ( 4 ) -edges where 0 i j 3 .
We can suppose i = 0 , j = 3 , and 1 k l 2 . Let H = F D S C 4 V ( D 0 ) V ( D 3 ) . furthermore let U = { s a | 1 a m } V ( D i ) and V = { t a | 1 a m } V ( D j ) with 2 m 3 . Since D i and D j are complete graphs, there exists a one-to-many disjoint path cover between μ and U in D i , and a one-to-many disjoint path cover between ν and V in D j .
Case 2.1. e 4 μ and e 4 ν are connected to μ V ( D k ) and ν V ( D k ) , respectively.
For m = 2 , we can have ( s 1 , t 1 ) E ( F D S C 4 ) , s 2 and t 2 are connected to s 2 V ( D l ) and t 2 V ( D l ) , respectively. Then we construct the 3-DPC as follows: P 1 = μ , S 1 , s 1 , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , s 2 , Q l , t 2 , t 2 , T 2 , ν , and P 3 = μ , μ , Q k , ν , ν .
For m = 3 , we can have ( s 1 , t 1 ) , ( s 2 , t 2 ) E ( F D S C 4 ) , s 3 and t 3 are connected to s 3 V ( D l ) and t 3 V ( D l ) , respectively. Then we construct the 4-DPC as follows: P 1 = μ , S 1 , s 1 , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , t 2 , T 2 , ν , P 3 = μ , S 3 , s 3 , s 3 , Q l , t 3 , t 3 , T 3 , ν , and P 4 = μ , μ , Q k , ν , ν .
Case 2.2. e 4 μ and e 4 ν are connected to μ V ( D k ) and ν V ( D l ) , respectively.
By Lemma 6, there is a path P 3 = μ , μ , Q , ν , ν which covers all the nodes of V ( H ) . For m = 2 , we can have ( s 1 , t 1 ) , ( s 2 , t 2 ) E ( F D S C 4 ) . Then we construct the 3-DPC as follows: P 1 = μ , S 1 , s 1 , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , t 2 , T 2 , ν , and P 3 .
For m = 3 , we can have ( s 1 , t 1 ) , ( s 2 , t 2 ) E ( F D S C 4 ) , s 3 and t 3 are connected to s 3 V ( D l ) and t 3 V ( D k ) , respectively. Then we construct the 4-DPC as follows: P 1 = μ , S 1 , s 1 , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , t 2 , T 2 , ν , P 3 = μ , μ , Q k , t 3 , t 3 , T 3 , ν , and P 4 = μ , S 3 , s 3 , s 3 , Q l , ν , ν .
Case 2.3. e 4 μ and e 4 ν are connected to t 1 V ( D j ) and ν V ( D k ) , respectively.
For m = 2 , we can have ( s 2 , t 2 ) E ( F D S C 4 ) , s 1 is connected to s 1 V ( D l ) . By Lemma 6, there is a path P 3 = μ , S 1 , s 1 , s 1 , Q , ν , ν which covers all the nodes of V ( H ) . Then we construct the 3-DPC as follows: P 1 = μ , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , t 2 , T 2 , ν , and P 3 .
For m = 3 , we can have ( s 2 , t 2 ) E ( F D S C 4 ) , s 1 is connected to s 1 V ( D k ) , s 3 and t 3 are connected to s 3 V ( D l ) and t 3 V ( D l ) , respectively. Then we construct the 4-DPC as follows: P 1 = μ , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , t 2 , T 2 , ν , P 3 = μ , S 3 , s 3 , s 3 , Q l , t 3 , t 3 , T 3 , ν , and P 4 = μ , S 1 , s 1 , s 1 , Q k , ν , ν .
Case 2.4. e 4 μ and e 4 ν are connected to μ V ( D k ) and s 1 V ( D i ) respectively.
The proof of this case is similar to Case 2.3.
Case 2.5. ( μ , ν ) E ( F D S C 4 ) .
For m = 2 , we can have ( s 1 , t 1 ) E ( F D S C 4 ) , s 2 and t 2 are connected to s 2 V ( D l ) and t 2 V ( D k ) , respectively. Then we construct the 3-DPC as follows: P 1 = μ , S 1 , s 1 , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , s 2 , Q , t 2 , t 2 , T 2 , ν , and P 3 = μ , ν .
For m = 3 , we can have ( s 1 , t 1 ) E ( F D S C 4 ) , s 2 and t 2 are connected to s 2 V ( D k ) and t 2 V ( D k ) , s 3 and t 3 are connected to s 3 V ( D l ) and t 3 V ( D l ) , respectively. Then we construct the 4-DPC as follows: P 1 = μ , S 1 , s 1 , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , s 2 , Q 2 , t 2 , t 2 , T 2 , ν , P 3 = μ , S 3 , s 3 , s 3 , Q 3 , t 3 , t 3 , T 3 , ν , and P 4 = μ , ν .
Case 2.6. e 4 μ and e 4 ν are connected to t 1 V ( D j ) and s 1 V ( D i ) , respectively.
For m = 2 , we can have s 2 and t 2 are connected to s 2 V ( D l ) and t 2 V ( D k ) , respectively. Then we construct the 3-DPC as follows: P 1 = μ , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , s 2 , Q , t 2 , t 2 , T 2 , ν , and P 3 = μ , S 1 , s 1 , ν .
For m = 3 , we can have s 2 and t 2 are connected to s 2 V ( D k ) and t 2 V ( D k ) , s 3 and t 3 are connected to s 3 V ( D l ) and t 3 V ( D l ) , respectively. Then we construct the 4-DPC as follows: P 1 = μ , t 1 , T 1 , ν , P 2 = μ , S 2 , s 2 , s 2 , Q k , t 2 , t 2 , T 2 , ν , P 3 = μ , S 3 , s 3 , s 3 , Q l , t 3 , t 3 , T 3 , ν , and P 3 = μ , S 1 , s 1 , ν .
Case 3. μ V ( D i ) and ν V ( D j ) and D i and D j are connected with one e ( 4 ) -edge where 0 i j 3 .
We can suppose i = 0 and j = 1 . When ν = 0001 , we list the 3-DPC and 4-DPC between μ V ( D 0 ) and ν in Table 2. Similarly, there is a 3-DPC and a 4-DPC between every two nodes μ V ( D i ) and ν V ( D j ) .
Hence, there exists an m-DPC between μ and ν for 1 m d + 2 in F D S C n for integer d { 1 , 2 } and n = 2 d . □
Lemma 11.
Let μ and ν be any two nodes in F D S C n for any integer d 1 and n = 2 d . There exists an m-DPC between μ and ν in F D S C n with 1 m d + 2 .
Proof. 
To prove this lemma, we proceed by induction on d. The base case is given in Lemma 10 for d { 1 , 2 } . Suppose this lemma holds for F D S C 2 d 1 when d 3 , we will prove that this lemma holds for F D S C 2 d with d 3 . By Lemma 5, there exists an m-DPC between μ and ν in F D S C n for 1 m 2 , so we need to prove this lemma holds for 3 m d + 2 . Considering the locations of μ and ν in F D S C n , we have the cases as follows.
Case 1. μ , ν V ( D k ) with 0 k h 1 .
W.L.O.G., suppose μ and ν are in D 0 . According to the hypothesis, there exists an m-DPC between μ and ν in D 0 where 2 m d + 1 .
Case 1.1. e n μ and e n ν are connected to different modules of F D S C n .
Suppose that μ is connected to x V ( D i ) and ν is connected to y V ( D j ) , where 1 i j h 1 . By Lemma 6, there exists a Hamiltonian path covering all nodes of V ( F D S C n ) V ( D 0 ) . Hence, there exists a ( m + 1 ) -DPC between μ and ν in F D S C n where 3 m + 1 d + 2 (see Figure 6).
Case 1.2. μ and ν are connected to the same module of F D S C n .
Suppose that μ and ν are connected to D i with 1 i h 1 . By Lemma 7, there exists a Hamiltonian path covering all nodes of V ( F D S C n ) V ( D 0 ) . Hence, there exists a ( m + 1 ) -DPC between μ and ν in F D S C n where 3 m + 1 d + 2 .
Case 2. μ V ( D i ) and ν V ( D j ) with 0 i j h 1 .
Let H = F D S C n V ( D i ) V ( D j ) .
Case 2.1. e n μ and e n ν are connected to H.
By Property 1, we can find two nodes s V ( D i ) and t V ( D j ) such that ( s , t ) E ( F D S C n ) . According to the hypothesis, there exists an m-DPC between μ and s in D i and an m-DPC between ν and t in D j where 2 m d + 1 . Let S = { s 1 , s 2 , , s m } and T = { t 1 , t 2 , , t m } be the neighbor set of s and t in the m-DPC. By Property 1, D i and D j have at most two edges between them. Let ( x , y ) be another edge between D i and D j if it exists. Suppose that x is in path μ , S 1 , s 1 , s and y is in path ν , T 1 , t 1 , t . We can construct a path μ , S 1 , s 1 , s , t , t 1 , T 1 , ν between μ and ν whether or not x, y exist. Then, for each k with 2 k m , t k (resp. s k ) is connected to a different module in H. We can find m 1 node pairs between { s k | 2 k m } and { t l | 2 l m } to build paths μ , S k , s k , s k , P k , l , t l , t l , T l , ν which covers 1 or 2 module(s) of H. Let M be the module set consisting of modules covered by the paths between { s k | 2 k m } and { t l | 2 l m } . Then | M | 2 ( m 1 ) 2 d < h 2 . By Lemmas 6 and 7, there exists a path μ , μ , P , μ , ν which covers all the modules of H M . Hence, there exists a ( m + 1 ) -DPC between μ and ν where 3 m + 1 d + 2 (see Figure 7).
Case 2.2. e n μ is connected to D j and e n ν is connected to H.
Let ( μ , t ) E ( F D S C n ) and t V ( D j ) . According to the hypothesis, there exists an m-DPC between ν and t in D j where 2 m d + 1 . We have T = { t 1 , t 2 , , t m } be the neighbor set of t in the m-DPC. By Lemma 9, we can find a vertex set S = { s 1 , s 2 , , s m } such that there exists a one-to-many node disjoint path cover between μ and S in D i and the vertex labels are not complementary with each other in S + { μ } . Hence, each s i with 1 i m is connected to a different module of H. Let y V ( D j ) be connected to D i if exists. Suppose that y is in path ν , T 1 , t 1 , t . We can construct a path μ , t , t 1 , T 1 , ν between μ and ν whether or not y exists. For { s k | 2 k m } and { t l | 2 l m } , we can construct m 1 paths μ , S k , s k , s k , P k , l , t l , t l , T l , ν between them, the union of which covers module set M. Then | M | 2 ( m 1 ) 2 d < h 2 . By Lemmas 6 and 7, there exists a path μ , S 1 , s 1 , s 1 , P , ν , ν which covers all the modules of H M . Hence, there exists a ( m + 1 ) -DPC between μ and ν where 3 m + 1 d + 2 (see Figure 8).
Case 2.3. e n ν is connected to D i and e n μ is connected to H.
This case is similar to Case 2.2.
Case 2.4. ( μ , ν ) E ( F D S C n ) .
By Lemma 9, we can find a vertex set S = { s 1 , s 2 , , s m } such that there exists a one-to-many node-disjoint path cover between μ and S in D i and the vertex labels are not complementary with each other in S + { μ } . Similarly, we can find a vertex set T = { t 1 , t 2 , , t m } such that there exists a one-to-many node disjoint path cover between ν and T in D j , and the vertex labels are not complementary with each other in T + { ν } . We can construct m 1 paths μ , S k , s k , s k , P k , l , t l , t l , T l , ν between { s k | 2 k m } and { t l | 2 l m } the union of which covers module set M. By Lemmas 6 and 7, there exists a path μ , S 1 , s 1 , s 1 , P 1 , t 1 , t 1 , T 1 , ν , which covers all the modules of H M . Including path μ , ν , we get a ( m + 1 ) -DPC between μ and ν (see Figure 9).
Case 2.5. ( μ , t ) , ( ν , s ) E ( F D S C n ) , t V ( D j ) and s V ( D i ) .
According to the hypothesis, there exists an m-DPC between μ and s in D i and an m-DPC between ν and t in D j where 2 m d + 1 . Let S = { s 1 , s 2 , , s m } and T = { t 1 , t 2 , , t m } be the neighbor set of s and t in the m-DPC. We have two paths, μ , S 1 , s 1 , s , ν and μ , t , t 1 , T 1 , ν , between μ and ν . Then, for each k with 2 k m , t k (resp. s k ) is connected to a different module in H. We can find m 2 node pairs between { s k | 2 k m 1 } and { t l | 2 l m 1 } to build paths μ , S k , s k , s k , P k , l , t l , t l , T l , ν whose union covers module set M. Then | M | 2 ( m 2 ) 2 ( d 1 ) < h 2 . By Lemma 6 and Lemma 7, there exists a path μ , S m , s m , s m , P m , t m , t m , T m , ν which covers all the modules of H M . Hence, there exists a ( m + 1 ) -DPC between μ and ν where 3 m + 1 d + 2 (see Figure 10).
Hence, there exists an m-DPC between μ and ν in F D S C n where 1 m d + 2 . □
For all 1 j d + 2 , F D S C n is j * -connected, then F D S C n is super spanning connected. We have Theorem 1.
Theorem 1.
κ * ( F D S C n ) = κ ( F D S C n ) = d + 2 for d 1 and n = 2 d .
With Theorem 1, we show that there exist m disjoint paths between any pair of nodes for all 1 m d + 2 . Since each node of F D S C n has d + 2 neighbors, the result is optimal.

4. Conclusions

D S C n and F D S C n are newly proposed hypercube variants, which reduce the network cost from O ( n 2 ) to O ( n log 2 n ) compared with the hypercube and other hypercube variants. Both D S C n and F D S C n possess many superior properties than hypercubes. In this work, we investigated the super spanning connectivity of F D S C n . We show that κ * ( F D S C n ) = κ ( F D S C n ) = d + 2 , which means there exists an m-DPC between any pair of nodes in F D S C n for all 1 m d + 2 . Since the degree of F D S C n is d + 2 , then d + 2 is the maximal integer of node-disjoint paths that can be built in F D S C n . In future work, the one-to-many node-disjoint path cover problem of F D S C n could be considered. In addition, the diagnosability [25,26,27] of F D S C n is another research topic that could be considered.

Author Contributions

Conceptualization, L.Y.; methodology, Y.H.; investigation, J.J.; writing—original draft preparation, L.Y. and J.J.; writing—review and editing, Y.H. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by the Research Project of Suzhou Industrial Park Institute of Services Outsourcing (No. SISO-ZD202202).

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Zhou, S.; Xiao, W.; Parhami, B. Construction of vertex-disjoint paths in alternating group networks. J. Supercomput. 2010, 54, 206–228. [Google Scholar] [CrossRef] [Green Version]
  2. Cheng, D.; Hao, R.; Feng, Y. Two node-disjoint paths in balanced hypercubes. Appl. Math. Comput. 2014, 242, 127–142. [Google Scholar] [CrossRef]
  3. Wang, X.; Fan, J.; Lin, C.-K.; Jia, X. Vertex-disjoint paths in dcell networks. J. Parallel Distrib. Comput. 2016, 96, 38–44. [Google Scholar] [CrossRef]
  4. Lai, P.-L.; Hsu, H.-C. On the two-equal-disjoint path cover problem of crossed cubes. In Proceedings of the 9th Joint Conference on Information Sciences, JCIS, Kaohsiung, Taiwan, 8–11 October 2006; pp. 603–606. [Google Scholar]
  5. Gomes, T.; Craveirinha, J.; Jorge, L. An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs. Comput. Oper. Res. 2009, 36, 1670–1682. [Google Scholar] [CrossRef] [Green Version]
  6. Liu, C.; Yarvis, M.; Conner, W.S.; Guo, X. Guaranteed on-demand discovery of node-disjoint paths in Ad Hoc networks. Comput. Commun. 2007, 30, 2917–2930. [Google Scholar] [CrossRef]
  7. Day, K.; Al-Ayyoub, A.E. Fault diameter of k-ary n-cube networks. IEEE Trans. Parallel Distrib. Syst. 1997, 8, 903–907. [Google Scholar] [CrossRef]
  8. Shih, Y.-K.; Kao, S.-S. One-to-one disjoint path covers on k-ary n-cubes. Theoret. Comput. Sci. 2011, 412, 4513–4530. [Google Scholar] [CrossRef] [Green Version]
  9. Lai, P.-L.; Hsub, H.-C. The two-equal-disjoint path cover problem of Matching Composition Network. Inform. Process. Lett. 2008, 107, 18–23. [Google Scholar] [CrossRef]
  10. Ntafos, S.C.; Hakimi, S.L. On path cover problems in digraphs and applications to program testing. IEEE Trans. Softw. Eng. 1979, 5, 520–529. [Google Scholar] [CrossRef]
  11. Lin, C.K.; Tan, J.J.; Hsu, D.F.; Hsu, L.H. On the spanning connectively and spanning laceability of hypercube-like networks. Theor. Comput. Sci. 2007, 381, 218–229. [Google Scholar] [CrossRef] [Green Version]
  12. You, L.; Fan, J.; Han, Y.; Jia, X. One-to-one disjoint path covers on alternating group graphs. Theoret. Comput. Sci. 2015, 562, 146–164. [Google Scholar] [CrossRef]
  13. Li, J.; Liu, D.; Yang, Y.; Yuan, J. One-to-one disjoint path covers on multi-dimensional tori. Int. J. Comput. Math. 2015, 92, 1114–1123. [Google Scholar] [CrossRef]
  14. Wang, X.; Fan, J.; Jia, X.; Lin, C.-K. An efficient algorithm to construct disjoint path covers of DCell networks. Theoret. Comput. Sci. 2016, 609, 197–210. [Google Scholar] [CrossRef]
  15. You, L.; Fan, J.; Han, Y. Super spanning connectivity on WK-recursive networks. Theor. Comput. Sci. 2018, 713, 42–55. [Google Scholar] [CrossRef]
  16. Wang, J.-J.; Hsu, L.-H. On the spanning connectivity of the generalized Petersen graphs P(n, 3). Discret. Math. 2018, 341, 672–690. [Google Scholar] [CrossRef]
  17. Li, J.; Li, X.; Cheng, E. Super spanning connectivity of split-star networks. Inf. Process. Lett. 2021, 166, 106037. [Google Scholar] [CrossRef]
  18. Kim, J.S.; Kim, D.Y.; Qiu, K.; Lee, H.O. The divide-and-swap cube: A new hypercube variant with small network cost. J. Supercomput. 2019, 75, 3621–3639. [Google Scholar] [CrossRef]
  19. Ning, W. Connectivity and super connectivity of the divide-and-swap cube. Theor. Comput. Sci. 2020, 842, 1–5. [Google Scholar] [CrossRef]
  20. Zhou, Q.; Zhou, S.; Liu, J.; Liu, X. Structure and substructure connectivity of divide-and-swap cube. Theor. Comput. Sci. 2021, 880, 20–36. [Google Scholar] [CrossRef]
  21. Zhou, Q.; Zhou, S.; Liu, X.; Yu, Z. Reliability of divide-and-swap cube based on r-component connectivity and diagnosability. J. Interconnect. Netw. 2022, 22, 2142021. [Google Scholar] [CrossRef]
  22. Zhao, S.; Chang, J. Reliability assessment of the divide-and-swap cube in terms of generalized connectivity. Theor. Comput. Sci. 2023, 943, 1–15. [Google Scholar] [CrossRef]
  23. Zhao, S.-L.; Chang, J.-M. Connectivity, super connectivity and generalized 3-connectivity of folded divide-and-swap cubes. Inf. Process. Lett. 2023, 182, 106377. [Google Scholar] [CrossRef]
  24. Chang, Y.-H.; Pai, K.-J.; Hsu, C.-C.; Yang, J.-S.; Chang, J.-M. Constructing dual-CISTs of folded divide-and-swap cubes. Theor. Comput. Sci. 2021, 856, 75–87. [Google Scholar] [CrossRef]
  25. Li, X.; Fan, J.; Lin, C.-K.; Jia, X. Diagnosability Evaluation of the Data Center Network DCell. Comput. J. 2018, 61, 129–143. [Google Scholar] [CrossRef]
  26. Gu, M.; Hao, R.; Jiang, L. Fault-tolerance and diagnosability of hierarchical star networks. Int. J. Comput. Math. Comput. Syst. Theory 2018, 3, 106–121. [Google Scholar] [CrossRef]
  27. Zhang, H.; Zhou, S.; Liu, X.; Yu, Z. Extra (component) connectivity and diagnosability of bubble sort networks. Theor. Comput. Sci. 2023, 940, 180–189. [Google Scholar] [CrossRef]
Figure 1. D S C 2 and D S C 4 .
Figure 1. D S C 2 and D S C 4 .
Mathematics 11 02581 g001
Figure 2. F D S C 2 and F D S C 4 .
Figure 2. F D S C 2 and F D S C 4 .
Mathematics 11 02581 g002
Figure 3. Illustration for Case 2 of Lemma 6.
Figure 3. Illustration for Case 2 of Lemma 6.
Mathematics 11 02581 g003
Figure 4. Illustration for Lemma 7.
Figure 4. Illustration for Lemma 7.
Mathematics 11 02581 g004
Figure 5. Illustration for Lemma 9.
Figure 5. Illustration for Lemma 9.
Mathematics 11 02581 g005
Figure 6. Illustration for Case 1.1 of Lemma 11.
Figure 6. Illustration for Case 1.1 of Lemma 11.
Mathematics 11 02581 g006
Figure 7. Illustration for Case 2.1 of Lemma 11.
Figure 7. Illustration for Case 2.1 of Lemma 11.
Mathematics 11 02581 g007
Figure 8. Illustration for Case 2.2 of Lemma 11.
Figure 8. Illustration for Case 2.2 of Lemma 11.
Mathematics 11 02581 g008
Figure 9. Illustration for Case 2.4 of Lemma 11.
Figure 9. Illustration for Case 2.4 of Lemma 11.
Mathematics 11 02581 g009
Figure 10. Illustration for Case 2.5 of Lemma 11.
Figure 10. Illustration for Case 2.5 of Lemma 11.
Mathematics 11 02581 g010
Table 1. Acronyms and Notation.
Table 1. Acronyms and Notation.
SymbolDefinition
D S C n the n-dimensional divide-and-swap cube where n = 2 d and d is any positive integer
F D S C n the n-dimensional folded divide-and-swap cube
D P C disjoint path cover
D i the ith module of F D S C n with 0 i 2 n 2 1
κ * ( G ) the spanning connectivity of a graph G
Table 2. The 3-DPC and 4-DPC between μ and ν .
Table 2. The 3-DPC and 4-DPC between μ and ν .
3-DPC4-DPC
μ = 0100 0100 , 0001 0100 , 0001
ν = 0001 0100 , 1100 , 0011 , 1111 , 1011 , 0111 , 1101 , 0101 , 0001 0100 , 1100 , 0011 , 0111 , 1101 , 0001
0100 , 0000 , 1000 , 0010 , 1110 , 1010 , 0110 , 1001 , 0001 0100 , 1000 , 0010 , 0110 , 1001 , 0001
0100 , 0000 , 1111 , 1011 , 1110 , 1010 , 0101 , 0001
μ = 1100 1100 , 0100 , 0001 1100 , 0100 , 0001
ν = 0001 1100 , 0011 , 1111 , 1011 , 0111 , 1101 , 0101 , 0001 1100 , 0011 , 0111 , 1101 , 0001
1100 , 0000 , 1000 , 0010 , 1110 , 1010 , 0110 , 1001 , 0001 1100 , 1000 , 0010 , 0110 , 1001 , 0001
1100 , 0000 , 1111 , 1011 , 1110 , 1010 , 0101 , 0001
μ = 1000 1000 , 0100 , 0001 1000 , 0100 , 0001
ν = 0001 1000 , 0000 , 1100 , 0011 , 1111 , 1011 , 0111 , 1101 , 0001 1000 , 1100 , 0011 , 0111 , 1101 , 0001
1000 , 0010 , 1110 , 1010 , 0110 , 1001 , 0101 , 0001 1000 , 0010 , 0110 , 1001 , 0001
1000 , 0000 , 1111 , 1011 , 1110 , 1010 , 0101 , 0001
μ = 0000 0000 , 0100 , 0001 0000 , 0100 , 0001
ν = 0001 0000 , 1100 , 0011 , 1111 , 1011 , 0111 , 1101 , 0001 0000 , 1100 , 0011 , 0111 , 1101 , 0001
0000 , 1000 , 0010 , 1110 , 1010 , 0110 , 1001 , 0101 , 0001 0000 , 1000 , 0010 , 0110 , 1001 , 0001
0000 , 1111 , 1011 , 1110 , 1010 , 0101 , 0001
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Share and Cite

MDPI and ACS Style

You, L.; Jiang, J.; Han, Y. Super Spanning Connectivity of the Folded Divide-and-SwapCube. Mathematics 2023, 11, 2581. https://0-doi-org.brum.beds.ac.uk/10.3390/math11112581

AMA Style

You L, Jiang J, Han Y. Super Spanning Connectivity of the Folded Divide-and-SwapCube. Mathematics. 2023; 11(11):2581. https://0-doi-org.brum.beds.ac.uk/10.3390/math11112581

Chicago/Turabian Style

You, Lantao, Jianfeng Jiang, and Yuejuan Han. 2023. "Super Spanning Connectivity of the Folded Divide-and-SwapCube" Mathematics 11, no. 11: 2581. https://0-doi-org.brum.beds.ac.uk/10.3390/math11112581

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop