The hypercube serves as a high-performance interconnection network employed in various fields, including data center networks, network-on-chips, and wireless sensor networks. As the number of processing elements rapidly increases, these application fields are facing significant challenges in preserving communication efficiency with robust fault-tolerant mechanisms. Paths and cycles are two effective and popular tools for improving the communication efficiency of large-scale networks. Fault-tolerant path/cycle embedding is recognized as a solution to maintain communication efficiency and fault tolerance simultaneously. In this paper, we aim to enhance the fault-tolerant path/cycle embedding capability of hypercube networks by an emerging fault model, namely thePartitionedEdgeFault (PEF) model. Under this model, we put forward four distinct fault-tolerant path/cycle embedding algorithms that can handle large-scale faulty edges. Moreover, by proving the upper bound of these algorithms’ fault tolerance, we derive the optimal fault-tolerant Hamiltonian laceability and bipancyclicity of hypercubes under the PEF model. Furthermore, we conduct both theoretical and experimental analyses to show our algorithms’ outstanding fault-tolerant capability compared to the state-of-the-art. To validate the practical applicability of our theoretical results, we also develop a deadlock-free routing strategy leveraging the proposed embedding algorithm and compare its performance with benchmark routing algorithms.

Data center networks (DCNs) are the essential backbone connecting servers, storage, and networking devices, enabling vast data processing and seamless transmission. Among these competing platforms, BCube stands out due to its exceptional scalability and fault tolerance. For a graphGas the underlying topology of a network, the neighbor connectivity (resp. edge-neighbor connectivity) refers to the minimum number of vertices (resp. edges) that the removal of their closed neighborhoods (which is called subversion) results in becoming disconnected, complete, or empty (resp. trivial). These two connectivities provide more precise evaluations of network reliability and fault tolerance. In this paper, we explore these two specific connectivities of BCube and conduct a series of experiments to evaluate the effects of subversion across various scales. Specifically, we compare the experimental outcomes of random failures with those of cascade failures at varying failure rates. Additionally, we conduct a comparative analysis of the average path length (APL) of BCube and other networks, including thek-aryn-cube and DCell, in residual networks after subversion. These experiments enhance our understanding of the complexities of neighbor connectivity and subversion behaviors within BCube, demonstrating its superior fault tolerance.

Cloud computing has become essential to various application services, requiring robust data center networks (DCNs) to support its infrastructure. This paper explores the establishment of a three-party proprietary communication channel and its related applications in a highly scalable data center network (HSDC). This novel research topic involves third-party authentication (TPA) in cloud applications. With the increasing demand for secure and reliable communication, we investigate the implementation of internally disjoint 3-Steiner paths (ID-3SPs), which facilitate message transmission with the involvement of a trusted third party. By explicitly constructing ID-3SPs and developing a definitive algorithm, we incorporate 3-path connectivity with TPA-related applications to enhance transmission efficiency caused by multi-paths while ensuring fault tolerance in the event of network component failures. Extensive experiments conducted in HSDC have shown that our findings significantly improve the reliability and efficiency of communication in DCNs, demonstrating their potential for practical applications that will benefit diverse fields, ranging from e-commerce to supply chains.

Thek-aryn-cubeQknis a widely employed interconnection network for data center networks (DCNs) due to its favorable properties, including node/edge symmetry, recursive structure, regularity, and ease of deployment. Among the numerous structures studied inQkn, the cycle is fundamental for addressing various graph-related problems in DCNs. This has motivated extensive research on fault-tolerant cycle embedding withinQkn. However, existing methods for cycle embedding often exhibit limited fault tolerance since they fail to account for the dimension-oriented nature of edge faults inQkn. In this paper, we overcome this limitation by using the partitioned edge fault (PEF) model, a recently developed model that explicitly considers dimension-specific fault distributions. Under the PEF model, we propose a new indicator called partition-edge fault-tolerant bipancyclicity, which accurately reflects the practical fault characteristics ofQkn. ForQknwith even k ≥ 4, we determine the exact value of this indicator and prove its optimality under the PEF model. Moreover, forQknwith odd k ≥ 3, we develop three fault-tolerant embedding algorithms that establish a lower bound for this indicator. Furthermore, we conduct numerical evaluations and simulation experiments to analyze the bipancyclicity ofQknunder varying scales of edge faults.

Fault diagnosis is essential for maintaining the regular operation of multiprocessor systems. In this paper, we introduce a novel concept of$r$-component$H$-structure diagnosability, denoted as$t_{s}^{r}(G;H)$, which represents the maximum number of$r$-component$H$-structure faults that system$G$can precisely detect. This parameter enables us to assess the overall diagnosability of the system. Furthermore, we strictly prove that under the PMC and MM* diagnostic models, the following results hold: for$n\geq 7$,$t_{s}^{2}(Q_{n};K_{1,1})=2n-4$; for$n\geq 6$,$t_{s}^{2}(Q_{n};K_{1,2})=n-2$. These results confirm that when the system experiences a$K_{1,1}$-structural fault and is disconnected at this time, the maximum number of detectable$K_{1,1}$-structures within the system is guaranteed to be twice the original number in previous studies.

BCube stands as a renowned server-centric data center network (DCN), boasting numerous advantages, such as low diameter, high aggregate throughput, and abundant parallel paths. As DCNs expand rapidly, followed by the daily increasing likelihood of failures, fault tolerance has become an impor tant issue in DCNs. Hamiltonian paths constitute a pivotal network topology for parallel and distributed computing, suitable for designing deadlock-free routing algorithms, fault-tolerant routing algorithms, and congestion avoidance. The partitioned edge fault (PEF) model is a recently proposed fault model that exploits the properties of networks to achieve fault tolerance with an exponential scale. In this paper, we explore the existence of Hamiltonian paths in BCube under the PEF model. Since one switch failure will result in multiple faulty links, we also extend the conclusions related to Hamiltonian paths to analyze the fault tolerance of BCube under the PEF model when switch failures occur. Moreover, we provide algorithms to embed a Hamiltonian path between arbitrary two distinct servers into BCube under the PEF model. Experimental analysis and comparisons demonstrate that our approach exhibits exponential enhancements over the other known results, and BCube DCNs possess remarkable fault tolerance in response to both link and switch failures under the PEF model. As a by-product, we obtain a deadlock-free routing based on the constructed Hamiltonian path and assess the routing performance compared to the benchmark routing algorithms.

With the surge of bandwidth demand for cloud applications and the exponential growth of data, data center networks (DCNs) are expanding rapidly, followed by the daily increasing likelihood of failures. Such failures, whether due to device or link issues, are inevitable and often lead to packet loss, transmission delays, and even system downtime. Thus, it is crucial to assess the fault-tolerant capabilities of data center networks using appropriate reliability metrics when failures occur. BCube is a well-known server-centric data center network with many advantages, such as rich low-diameter paths, high throughput, and excellent expandability. Not only do the recently proposed matroidal connectivity and conditional matroidal connectivity have reasonable fault assumptions that align well with the structural characteristics of data center networks, but they also significantly enhance the fault tolerance performance of DCNs. This paper determines the matroidal connectivity and conditional matroidal connectivity of BCube, which is the first study to apply the two reliability metrics in DCNs. Then, we extend the conclusions about (conditional) matroidal connectivity to analyze the fault tolerance of BCube in the occurrence of switch failures. In addition, we develop an efficient algorithm to identify the structural features of minimum faulty edge sets, where the cardinality of these edge sets corresponds to the conditional matroidal connectivity of BCube. Finally, we experimentally evaluate the effects of both link and switch failures on BCube’s performance under the matroidal restriction. The experimental analyses reveal that BCube DCNs exhibit high fault tolerance under matroidal constraints, with the ability to withstand both link and switch failures.

The scale of data center networks (DCNs) has grown rapidly with the increasing popularity of cloud computing, data explosion, and the dramatic drop in setup costs. Thus, inevitable component failures (including switches and servers) will become more frequent. A DCN requires maintaining regular and reliable operation and providing efficient routing algorithms for transmitting data between servers. Particularly, fault-tolerant routing is necessary. Recently, constructing completely independent spanning trees (CISTs) on DCNs has received much attention as a dual-CIST (i.e., two CISTs) suffices to configure protection routing, which is a fault-tolerant routing. Moreover, the protection routing can additionally realize a secure mechanism if it is configured by more CISTs. BCube is a server-centric DCN with many advantages, and many variations were deformed from BCube with application requirements, such as RCube and RRect. In this paper, we provide a unified framework called BCube-based DCN (BDCN) that integrates the representation of the logic graphs of DCNs mentioned above, facilitating consistent algorithms’ design. Then, we develop efficient algorithms to construct multiple CISTs on BDCN under the consideration of switch failures. Note that this is the first study that constructs multiple CISTs in DCNs with switch failures. Finally, using standard metrics, such as average path length (APL) and transmission failure rate (TFR), we evaluate the performance of the fault-tolerant routing through experiments.

The$k$-ary$n$-cube$Q_{n}^{k}$is one of the most popular interconnection networks engaged as the underlying topology of data center networks, on-chip networks, and parallel and distributed systems. Due to the increasing probability of faulty edges in large-scale networks and extensive applications of the Hamiltonian path, it becomes more and more critical to investigate the fault tolerability of interconnection networks when embedding the Hamiltonian path. However, since the existing edge fault models in the current literature only focus on the entire status of faulty edges while ignoring the important information in the edge dimensions, their fault tolerability is narrowed to a minimal scope. This article first proposes the concept of the partitioned fault model to achieve an exponential scale of fault tolerance. Based on this model, we put forward two novel indicators for the bipartite networks (including$Q^{k}_{n}$with even$k$), named partition-edge fault-tolerant Hamiltonian laceability and partition-edge fault-tolerant hyper-Hamiltonian laceability. Then, we exploit these metrics to explore the existence of Hamiltonian paths and unpaired 2-disjoint path cover in$k$-ary$n$-cubes with large-scale faulty edges. Moreover, we prove that all these results are optimal in the sense that the number of edge faults tolerated has attended to the best upper bound. Our approach is the first time that can still embed a Hamiltonian path and an unpaired 2-disjoint path cover into the$k$-ary$n$-cube even if the faulty edges grow exponentially.

The$k$-ary$n$-cube$Q_{n}^{k}$is one of the most important interconnection networks for building network-on-chips, data center networks, and parallel computing systems owing to its desirable properties. Since edge faults grow rapidly and the path structure plays a vital role in large-scale networks for parallel computing, fault-tolerant path embedding and its related problems have attracted extensive attention in the literature. However, the existing path embedding approaches usually only focus on the theoretical proofs and produce an$n$-related linear fault tolerance since they are based on the traditional fault model, which allows all faults to be adjacent to the same node. In this paper, we design an efficient fault-tolerant Hamiltonian path embedding algorithm for enhancing the fault-tolerant capacity of$k$-ary$n$-cubes. To facilitate the algorithm, we first introduce a new conditional fault model, named Partitioned Edge Fault model (PEF model). Based on this model, for the$k$-ary$n$-cube$Q_{n}^{k}$with$n\geq 2$and odd$k\geq 3$, we explore the existence of a Hamiltonian path in$Q_{n}^{k}$with large-scale edge faults. Then we give an$O(N)$algorithm, named HP-PEF, to embed the Hamiltonian path into$Q_{n}^{k}$under the PEF model, where$N$is the number of nodes in$Q_{n}^{k}$. The performance analysis of HP-PEF shows the average path length of adjacent node pairs in the Hamiltonian path constructed by HP-PEF. We also make comparisons to show that our result of edge fault tolerance has exponentially improved other known results. We further experimentally show that HP-PEF can support the dynamic degradation of average success rate of constructing Hamiltonian paths when increasing faulty edges exceed the fault tolerance.

The recently proposed RCube network is a cube-based server-centric data center network (DCN), including two types of heterogeneous servers, called core servers and edge servers. Remarkably, it takes the latter as backup servers to deal with server failures and thus achieve high availability. This paper first points out that RCube is suitable as a candidate topology of DCNs for edge computing. Three transmission types are among core and edge servers based on the demand for applications’ computation and instant response. We then employ protection routing to analyze the transmission failure of RCube DCNs. Unlike traditional protection routing, which only tolerates a single link or node failure, we use the multi-protection routing scheme to improve fault-tolerance capability. To configure a protection routing in a network, according to Tapolcai’s suggestion, we need to construct two completely independent spanning trees (CISTs), which are edge-disjoint and inner-vertex-disjoint spanning trees. It is well-known that the problem of determining whether there exists a dual-CIST (i.e., two CISTs) in a network is NP-complete. A logic graph of RCube, denoted by$L$-$RCube(n,m,k)$, is a network with a recursive structure. Each basic building element consists of$n$core servers and$m$edge servers, where the order$k$is the number of recursions applied in the structure. In this paper, we provide algorithms to construct$\min \{n,\lfloor (n+m)/2\rfloor \}$CISTs in$L$-$RCube(n,m,k)$for$n+m\geqslant 4$and$n>1$. From a combination of the multiple CISTs, we can configure the desired multi-protection routing. In our simulation, we configure up to 10 protection routings for RCube DCNs. As far as we know, in past research, there were at most three protection routings developed in other network structures. Finally, we summarize some crucial analysis viewpoints about the transmission efficiency of DCNs with heterogeneous edge-core servers from the simulation results.

A set of$k$spanning trees in a graph$G$are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices$x$and$y$in any two trees have neither vertex nor edge in common, except for$x$and$y$. The existence of multiple CISTs in the underlying graph of a network has applications in fault-tolerant broadcasting and secure message distribution. In this paper, we investigate the construction of CISTs in a server-centric data center network called BCube connected crossbars (BCCC), which can provide good network performance using inexpensive commodity off-the-shelf switches and commodity servers with only two network interface card (NIC) ports. The significant advantages of BCCC are its good expandability, lower communication latency, and higher robustness in component failure. Based on the structure of compound graphs of BCCC, we provide efficient algorithms to construct$\lceil \frac{n}{4}\rceil$CISTs in the logical graph of BCCC, denoted by$L$-$BCCC(n,k)$, for$n\geqslant 5$. As a by-product, we obtain a fault-tolerant routing that takes the constructed CISTs as its routing table. We then evaluate the performance of the fault-tolerant routing through simulation results.

Abstract A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $\min \{\textrm{deg}_G(x), \textrm{deg}_G(y)\}$ internally disjoint (edge disjoint) paths between $x$ and $y$. Motivated by parallel routing in networks with faults, Oh and Chen (resp., Qiao and Yang) proposed the (fault-tolerant) strong Menger (edge) connectivity as follows. A graph $G$ is called $m$-strongly Menger (edge) connected if $G-F$ remains strongly Menger (edge) connected for an arbitrary vertex set $F\subseteq V(G)$ (resp. edge set $F\subseteq E(G)$) with $|F|\leq m$. A graph $G$ is called $m$-conditional strongly Menger (edge) connected if $G-F$ remains strongly Menger (edge) connected for an arbitrary vertex set $F\subseteq V(G)$ (resp. edge set $F\subseteq E(G)$) with $|F|\leq m$ and $\delta (G-F)\geq 2$. In this paper, we consider strong Menger (edge) connectedness of the augmented $k$-ary $n$-cube $AQ_{n,k}$, which is a variant of $k$-ary $n$-cube $Q_n^k$. By exploring the topological proprieties of $AQ_{n,k}$, we show that $AQ_{n,3}$ (resp. $AQ_{n,k}$, $k\geq 4$) is $(4n-9)$-strongly (resp. $(4n-8)$-strongly) Menger connected for $n\geq 4$ (resp. $n\geq 2$) and $AQ_{n,k}$ is $(4n-4)$-strongly Menger edge connected for $n\geq 2$ and $k\geq 3$. Moreover, we obtain that $AQ_{n,k}$ is $(8n-10)$-conditional strongly Menger edge connected for $n\geq 2$ and $k\geq 3$. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.

Abstract Given a connected graph $G$ and a positive integer $\ell $, the $\ell $-extra (resp. $\ell $-component) edge connectivity of $G$, denoted by $\lambda ^{(\ell )}(G)$ (resp. $\lambda _{\ell }(G)$), is the minimum number of edges whose removal from $G$ results in a disconnected graph so that every component has more than $\ell $ vertices (resp. so that it contains at least $\ell $ components). This naturally generalizes the classical edge connectivity of graphs defined in term of the minimum edge cut. In this paper, we proposed a general approach to derive component (resp. extra) edge connectivity for a connected graph $G$. For a connected graph $G$, let $S$ be a vertex subset of $G$ for $G\in \{\Gamma _{n}(\Delta ),AG_n,S_n^2\}$ such that $|S|=s\leq |V(G)|/2$, $G[S]$ is connected and $|E(S,G-S)|=\min \limits _{U\subseteq V(G)}\{|E(U, G-U)|: |U|=s, G[U]\ \textrm{is connected}\ \}$, then we prove that $\lambda ^{(s-1)}(G)=|E(S,G-S)|$ and $\lambda _{s+1}(G)=|E(S,G-S)|+|E(G[S])|$ for $s=3,4,5$. By exploring the reliability analysis of $AG_n$ and $S_n^2$ based on extra (component) edge faults, we obtain the following results: (i) $\lambda _3(AG_n)-1=\lambda ^{(1)}(AG_n)=4n-10$, $\lambda _4(AG_n)-3=\lambda ^{(2)}(AG_n)=6n-18$ and $\lambda _5(AG_n)-4=\lambda ^{(3)}(AG_n)=8n-24$; (ii) $\lambda _3(S_n^2)-1=\lambda ^{(1)}(S_n^2)=4n-8$, $\lambda _4(S_n^2)-3=\lambda ^{(2)}(S_n^2)=6n-15$ and $\lambda _5(S_n^2)-4=\lambda ^{(3)}(S_n^2)=8n-20$. This general approach maybe applied to many diverse networks.

Abstract For an integer $\ell \geqslant 2$, the $\ell $-component connectivity (resp. $\ell $-component edge connectivity) of a graph $G$, denoted by $\kappa _{\ell }(G)$ (resp. $\lambda _{\ell }(G)$), is the minimum number of vertices (resp. edges) whose removal from $G$ results in a disconnected graph with at least $\ell $ components. The two parameters naturally generalize the classical connectivity and edge connectivity of graphs defined in term of the minimum vertex-cut and the minimum edge-cut, respectively. The two kinds of connectivities can help us to measure the robustness of the graph corresponding to a network. In this paper, by exploring algebraic and combinatorial properties of $n$-dimensional balanced hypercubes $BH_n$, we obtain the $\ell $-component (edge) connectivity $\kappa _{\ell }(BH_n)$ ($\lambda _{\ell }(BH_n)$). For $\ell $-component connectivity, we prove that $\kappa _2(BH_n)=\kappa _3(BH_n)=2n$ for $n\geq 2$, $\kappa _4(BH_n)=\kappa _5(BH_n)=4n-2$ for $n\geq 4$, $\kappa _6(BH_n)=\kappa _7(BH_n)=6n-6$ for $n\geq 5$. For $\ell $-component edge connectivity, we prove that $\lambda _3(BH_n)=4n-1$, $\lambda _4(BH_n)=6n-2$ for $n\geq 2$ and $\lambda _5(BH_n)=8n-4$ for $n\geq 3$. Moreover, we also prove $\lambda _\ell (BH_n)\leq 2n(\ell -1)-2\ell +6$ for $4\leq \ell \leq 2n+3$ and the upper bound of $\lambda _\ell (BH_n)$ we obtained is tight for $\ell =4,5$.

Given two regular graphs G and H such that the vertex degree of G is equal to the number of vertices in H, the compound graph G(H) is constructed by replacing each vertex of G by a copy of Hand replacing each edge of G by an additional edge connecting random vertices in two corresponding copies of H, respectively, under the constraint that each vertex in G(H) is incident with only one additional edge, exactly. L-HSDCmis a compound graph G(H), where G is a hypercube Qmand H is a complete graph Km, which is defined by focusing on the connected relation between servers in the novel data center network HSDCmproposed in [30]. A set of k spanning trees in a graph G are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and yin any two trees have neither vertex nor edge in common, except for x and y. In this paper, we give a sufficient condition for the existence of k CISTs in a kind of compound graph. Furthermore, a specific construction algorithm is provided. As corollaries of the main results, the existences of two CISTs form m ≥ 4; three CISTs form m ≥ 8 and four CISTs form m ≥ 10 in L-HSDCm(m) are gotten directly.

A set of k (≥ 2) spanning trees in the underlying graph of a network topology is called completely independent spanning trees, (CISTs for short), if they are pairwise edge-disjoint and inner-node-disjoint. Particularly, if k=2, the two CISTs are called a dual-CIST. However, it has been proved that determining if there exists a dual-CIST in a graph is an NP-hard problem. Kwong et al. [IEEE/ACM Transactions Networking 19(5) 1543-1556, 2011] defined that a routing is protected, if there is an alternate with loop-free forwarding, when a single link or node failure occurs. Shortly afterward, Tapolcai [Optim. Lett. 7(4) 723-730, 2013] showed that a network possessing a dual-CIST suffices to establish a protection routing. It is well-known that Cayley graphs have a large number of desirable properties of interconnection networks. Although many results of constructing dual-CISTs on interconnection networks have been proposed in the literature, so far, the work has not been dealt with on Cayley graphs due to that their expansions are in exponential scalability. In this paper, we try to make a breakthrough of this work on some famous subclasses of Cayley graphs, including alternating group networks, bubble-sort network, and star networks. We first propose tree searching algorithms for helping the construction of dual-CISTs on low-dimensional networks. Then, by inductive construction, we show that dual-CISTs on high-dimensional networks can also be constructed agreeably. As a result, we can configure protection routings by using the constructed dual-CISTs. In addition, we complement some analysis with a simulation study of the proposed construction to evaluate the corresponding performance.

In this paper, we determine the wide diameters of regular hyper-stars HS(2k,k) and folded hyper-stars FHS(2k,k)⁠. We first provide a connection between the wide diameter and the maximum height of a set of particular spanning trees, called independent spanning trees (ISTs for short), of a graph. According to this relation, we analyze the heights of ISTs constructed in the previous works to establish upper bounds of the wide diameters of HS(2k,k) and FHS(2k,k)⁠. By contrast, we take the known results of fault diameters of HS(2k,k) and FHS(2k,k) as lower bounds. Consequently, we obtain the following results: (i) Dw(HS(2k,k))=2k+1 for k≥2⁠, and (ii) Dw(FHS(4,2))=3 and Dw(FHS(2k,k))=k+2 for k≥3⁠, where Dw(G) stands for the wide diameter of a graph G. The latter gives the answer of a question arisen from a previous work [(2015) Pruning longer branches of ISTs on folded hyper-stars, Comput. J., 58, 2972–2981]. In addition, we ascertain that all ISTs of HS(2k,k) and FHS(2k,k) constructed in the previous works are optimal in the sense that their heights are minimized.

Hypercubes and star graphs are widespread topologies of interconnection networks. The class of hyper-stars was introduced as a new type of interconnection network to compete with both hypercubes and star graphs, and the class of folded hyper-stars is a strengthened variation of hyper-stars with additional links to connect nodes with complemented 0/1-strings. Constructing independent spanning trees (ISTs) has numerous applications in networks such as fault-tolerant broadcasting and secure message distribution. Recently, Yang and Chang [IST on folded hyper-stars, Networks 56 (2010), 272–281] proposed an algorithm to construct |$k+1$| ISTs on folded hyper-star |$FHS(2k,k)$|⁠. For |$k\geqslant 4$|⁠, their constructions include |$k$| ISTs with a height |$2k-2$| and the other one with a height |$k+1$|⁠. In this paper, we refine their constructed rules on |$FHS(2k,k)$| for |$k\geqslant 3$| and provide a set of constructions including |$k$| ISTs with a height |$k+2$| and the other one with a height |$k+1$|⁠. As a by-product, we obtain an improvement on the upper bound of the fault diameter (respectively, the wide diameter) of |$FHS(2k,k)$|⁠.

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance, bandwidth and security. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. In this paper, we give an algorithm to construct ISTs on enhanced hypercubes Qn,k, which contain folded hypercubes as a subclass. Moreover, we show that these ISTs are near optimal for heights and path lengths. Let D(Qn,k) denote the diameter of Qn,k. If n - k is odd or n - k ∈ {2; n}, we show that all the heights of ISTs are equal to D(Qn,k) + 1, and thus are optimal. Otherwise, we show that each path from a node to the root in a spanning tree has length at most D(Qn,k) + 2. In particular, no more than 2.15 percent of nodes have the maximum path length. As a by-product, we improve the upper bound of wide diameter (respectively, fault diameter) of Qn,kfrom these path lengths.

A set of k spanning trees rooted at the same vertex r in a graph G is called independent [and the trees are called independent spanning trees (ISTs)] if, for any vertex x ≠ r, the k paths from x to r, one path in each tree, are internally disjoint. The design of ISTs on graphs has applications to fault-tolerant broadcasting and secure message distribution in networks. It was conjectured that, for any k-connected graph, there exist k ISTs rooted at any vertex of the graph. The conjecture has been proved true for k-connected graphs with k ≤ 4, and remains open otherwise. In this paper, we deal with the problem of constructing ISTs on the Cartesian product of a sequence of hybrid graphs, including cycles and complete graphs. Consequently, this result generalizes a number of previous works. Moreover, the construction is shown to be optimal in the sense that the heights of ISTs are minimized.

A t-ary tree is a rooted tree such that every internal node has exactly t disjoint subtrees. Recently, a concise representation called right-distance sequences (RD-sequences) was introduced to represent t-ary trees and their generalization called non-regular trees. In particular, a loopless algorithm has been proposed by Wu et al. ((2010) Loopless generation of non-regular trees with a prescribed branching sequence. Comput. J., 53, 661–666) for generating non-regular trees (and thus of t-ary trees) encoded by RD-sequences in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of t-ary trees with n internal nodes. The time complexity and space requirement in both algorithms are O(max{n2,tn}) and O(tn), respectively. As a by-product, we have an improvement on ranking and unranking t-ary trees encoded by z-sequences in a Gray-code order.

An ordered tree is called a non-regular tree with a prescribed branching sequence (or non-regular tree for short) if its internal nodes have a prespecified degree sequence in preorder list. We define a concise representation, called right distance sequences to describe such trees. A coding tree helps us to systematically investigate the structural representation of non-regular trees. Consequently, we present a loopless algorithm to generate Gray-codes of non-regular trees using right distance sequences.

Abstract Fault‐tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple independent spanning trees (ISTs) as a broadcasting scheme or a distribution protocol for receiving high levels of fault‐tolerance and security. Recently, hyper‐stars were introduced as a competitive model of interconnection network for both hypercubes and star graphs. The class of folded hyper‐stars is a strengthened variation of hyper‐stars obtained by adding additional links to connect complemented nodes. Both hyper‐stars and folded hyper‐stars have been shown to have lower network cost (measured by the product of degree and diameter) than hypercubes, folded hypercubes, and other variants. In this article, we propose an algorithm to construct k + 1 ISTs on a regular folded hyper‐star FHS (2k,k), where the number of ISTs matches the connectivity of FHS(2k,k). In particular, for k > 4, the constructed k ISTs have height 2 k − 2, and the other one has height k + 1. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010

Two spanning trees rooted at vertex r in a graph G are called independent spanning trees (ISTs) if for each vertex v in G, vner, the paths from vertex v to vertex r in these two trees are internally distinct. If the connectivity of G is k, the IST problem is to construct k ISTs rooted at each vertex. The IST problem has found applications in fault-tolerant broadcasting, but it is still open for general graphs with connectivity greater than four. In this paper, we shall propose a very simple algorithm for solving the IST problem on multidimensional torus networks. In our algorithm, every vertex can determine its parent for a specific independent spanning tree only depending on its own label. Thus, our algorithm can also be implemented in parallel systems or distributed systems very easily.

Abstract Jwo et al. [Networks 23 (1993) 315–326] introduced the alternating group graph as an interconnection network topology for computing systems. They showed that the proposed structure has many advantages over n‐cubes and star graphs. For example, all alternating group graphs are hamiltonian‐connected (i.e., every pair of vertices in the graph are connected by a hamiltonian path) and pancyclic (i.e., the graph can embed cycles with arbitrary length with dilation 1). In this article, we give a stronger result: all alternating group graphs are panconnected, that is, every two vertices x and y in the graph are connected by a path of length k for each k satisfying d(x, y) ≤ k ≤ |V| − 1, where d(x, y) denotes the distance between x and y, and |V| is the number of vertices in the graph. Moreover, we show that the r‐dimensional alternating group graph AGr, r ≥ 4, is (r − 3)‐vertex fault‐tolerant Hamiltonian‐connected and (r − 2)‐vertex fault‐tolerant hamiltonian. The latter result can be viewed as complementary to the recent work of Lo and Chen [IEEE Trans. Parallel and Distributed Systems 12 (2001) 209–222], which studies the fault‐tolerant hamiltonicity in faulty arrangement graphs. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 302–310 2004