Search

All-to-all broadcasting means to distribute the exclusive message of each node in the network to all other nodes. It can be handled by rings, and a Hamiltonian cycle is a ring that visits each vertex exactly once. Multiple edge-disjoint Hamiltonian cycles, abbreviated as EDHCs, have two application advantages: (1) parallel data broadcast and (2) edge fault-tolerance in network communications. There are three edge-disjoint Hamiltonian cycles on n-dimensional locally twisted cubes and n-dimensional crossed cubes while n ≥ 6, respectively. Locally twisted cubes, crossed cubes, folded locally twisted cubes (denoted as FLTQn), and folded crossed cubes (denoted as FCQn) are among the hypercube-variant network. The topology of hypercube-variant network has more wealth than normal hypercubes in network properties. Then, the following results are presented in this paper: (1) Using the technique of edge exchange, three EDHCs are constructed in FLTQ5 and FCQ5, respectively. (2) According to the recursive structure of FLTQn and FCQn, there are three EDHCs in FLTQn and FCQn while n ≥ 6. (3) Considering that multiple faulty edges will occur randomly, the data broadcast performance of three EDHCs in FLTQn and FCQn is evaluated by simulation when 5 ≤ n ≤ 9. [ABSTRACT FROM AUTHOR]

In IP networks, packet forwarding is destination-based and hop-by-hop, and routes are built as needed. Kwong et al. introduced a protection routing in which packet delivery to the destination node can proceed uninterrupted in the event of any single node or link failure. He then showed that "whether there is a protection routing to the destination" is NP-complete. Tapolcai found that two completely independent spanning trees, abbreviated as CISTs, can be used to configure the protection routing. In this paper, we proposed dual protection routing trees, denoted as dual-PRTs to replace CISTs, which are less restrictive than CISTs. Next, we proposed a transformation algorithm that uses dual-PRTs to configure the protection routing. Taking complete graphs Kn, complete bipartite graphs Km,n, hypercubes Qn, and locally twisted cubes LTQn as examples, we provided a recursive method to construct dual-PRTs on them. This article showed that there are no two CISTs on K3,3, Q3, and LTQ3, but there exist dual-PRTs that can be used to configure the protection routing. As shown in the performance evaluation of simulation results, for both Qn and LTQn, we get the average path length of protection routing configured by dual-PRTs is shorter than that by two CISTs. [ABSTRACT FROM AUTHOR]

Multiple edge-disjoint Hamiltonian cycles (EDHCs) provide the advantages of data broadcast in parallel and edge fault-tolerance in network communications. This paper investigates how to construct more EDHCs in a hypercube-variant network called crossed cube, denoted as C Q n . The topology of C Q n has more wealth than normal hypercubes in network properties, e.g., it has about half of the diameter of a hypercube with the same dimension. Then, we obtain the following results in this paper: (1) We first provide the construction of three EDHCs in C Q 6 . (2) According to the recursive structure of C Q n , we prove by induction that there exist also three EDHCs in C Q n for n ⩾ 7 . (3) Finally, we evaluate the performance of data broadcasting by simulation through three EDHCs and compare it against the best previous result in [18] using two EDHCs. In particular, our findings significantly improved the average success rate in edge fault-tolerant data broadcasting and two specific metrics concerning the broadcasting delivery time (latency). [ABSTRACT FROM AUTHOR]

The notion of neighbor connectivity was derived from the assessment of subversion in spy networks caused by the underground resistance movement. For a network G , the neighbor connectivity κ N B (G) (resp. edge neighbor connectivity λ N B (G)) is defined as the least number of vertices (resp. edges) such that if we remove the closed neighborhoods of them, the network will become disconnected, empty, or complete (resp. trivial). The two connectivities can also provide more accurate measures regarding the reliability and fault-tolerance of networks. Star graphs S n and hypercubes Q n are the two most famous structures in the family of Cayley graphs. They are widely studied in the research of developing multiprocessor systems. In this paper, we investigate the neighbor connectivity and edge neighbor connectivity of two kinds of hierarchical networks, called hierarchical star network H S n and complete cubic network C C n , which take S n and Q n as building blocks, respectively. Specifically, we obtain the following results: κ N B (H S n) = n − 1 and λ N B (H S n) = n for n ≥ 3 , and κ N B (C C n) = ⌈ n 2 ⌉ + 1 and λ N B (C C n) = n + 1 for n ≥ 2. In addition, to further determine the distribution of the number of subverted vertices and their occurrence status, we also carry out experiments to simulate the subversion at the vertices on these networks. • This research studies the subversion analyses of hierarchical networks based on (edge) neighbor connectivity. • The neighbor connectivity of hierarchical star network H S n is κ N B (H S n) = n − 1 for n ≥ 3. • The edge neighbor connectivity of hierarchical star network H S n i s λ N B (H S n) = n for n ≥ 3. • The neighbor connectivity of complete cubic network C C n is κ N B (C C n) = [ n 2 ] + 1 for n ≥ 2. • The edge neighbor connectivity of complete cubic network C C n is λ N B (C C n) = n + 1 for n ≥ 2. [ABSTRACT FROM AUTHOR]

• We point out that FDSC(n) is suitable as a candidate topology for DCNs. • We propose a recursive construction of a dual-CIST of FDSC(n). • The diameter of constructed CISTs is no more than 47 8 n. • As a by-product, we can use the dual-CIST to configure a protection routing. Spanning trees T 1 , T 2 , ... , T k (k ⩾ 2) in a network are 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. Hasunuma (2002) [8] proved that the problem of determining whether there exists a dual-CIST in a network is NP-complete. Tapolcai (2013) [20] showed that a dual-CIST has an application on configuring a protection routing in intra-domain IP networks. The adoption of protection routing guarantees that there is a loop-free alternate path for packet forwarding when a single link or node failure occurs. Pai et al. (2020) [17] demonstrated that protection routing is also suitable for relatively large (static) network topologies with scalability, such as interconnection networks with recursive structure and data center networks (DCNs). Recently, Kim et al. (2019) [10] newly proposed a hypercube-variant network called folded divide-and-swap cube, denoted as FDSC(n), which is obtained from the divide-and-swap cube DSC(n) by adding an extra edge to each node. They also showed that DSC(n) and FDSC(n) have a better network performance than that of hypercubes, where the performance is measured by the product of degree and diameter. In this paper, we first point out that FDSC(n) is suitable as a candidate topology for DCNs. Then, we investigate the construction of a dual-CIST { T 1 , T 2 } in FDSC(n). In particular, the diameters of T i for i = 1 , 2 we constructed are diam (T i) = { 9 if n = 4 ; 47 8 n − 15 − 2 3 (4 ⌊ d − 4 2 ⌋ − 1) (d mod 2 + 1) if n = 2 d for d ⩾ 3. [ABSTRACT FROM AUTHOR]

For a connected graph G = (V , E) , two spanning trees T 1 and T 2 of G are said to be a pair of completely independent spanning trees (or a dual-CIST for short) if for any two vertices u , v ∈ V , the paths joining u and v in the two trees have no common vertex except for u and v. Although the existence of a dual-CIST in the underlying graph of a network has the practical application of protection routing on fault-tolerance, it has been proved that determining whether a graph G admits a dual-CIST is NP-complete. As we know that Cayley graphs are a large family of graphs, some of its subclasses have been attracted and thus graphs in these subclasses have been adopted as the topologies of interconnection networks, such as the n-dimensional star graphs S n , bubble sort graphs B S n , pancake graph P n , alternating group networks A G N n and so on. Pai and Chang (IEEE/ACM Trans Netw 27(3): 1112–1123, 2019) recently showed that there exist dual-CISTs in S n , B S n , A G N n for n ⩾ 5 and provided their corresponding protection routings. So far, the problem of constructing dual-CISTs on P n has not been dealt with yet. In this sequel, we continue the investigation of the construction of dual-CISTs in pancake graphs as a complementary result. Since P n , S n , and B S n are with the same scale, we experimentally assess the performance of protection routing through simulation results for comparing them when n = 5 , 6 , 7 . [ABSTRACT FROM AUTHOR]

The protection routing uses the multi-paths technique for integrating route discovery and route maintenance mechanisms in a network, and thus it can tolerate the failure of one component (including a node or a link). Tapolcai (2013) proposed a method showing that a network possessing two completely independent spanning trees (CISTs for short) suffices to configure a protection routing. However, it is well-known that the problem of determining whether there exist two CISTs in a graph (or network) is NP-complete. In this paper, we extend Tapolcai's method such that the protection routing is configured by a combination of multiple CISTs. The first application of such an extension is that it can be used to deal with the problem of security in transmission, which we call the secure-protection routing scheme (SPR-scheme for short). Thus, a network transmission using the SPR-scheme ensures that no node other than the destination can receive the complete message. Moreover, we show that if a message M is transmitted in a network G using the SPR-scheme configured by a combination of n CISTs, then each intermediate node of G can receive a maximum of 2 ∕ n ratio of M. From a similar idea of the extension, another application is the so-called multiple-protection routing scheme (MPR-scheme for short) which can be used to increase the capability of fault-tolerance. For assessing the performance of routing using MPR-scheme, we first propose a construction of three CISTs in the two types of Möbius cubes, which are hypercube-variant networks and are superior to hypercubes due to having a smaller diameter. For the n -dimensional Möbius cube, the diameters of CISTs we constructed are at most 14 when n = 6 and at most 2 n + 1 when n ⩾ 7. So, we configure the desired protection routing in the Möbius cubes via the three CISTs. Then, we provide simulation results to experimentally evaluate the performance of the newly proposed MPR-scheme in the n -dimensional Möbius cubes for 6 ⩽ n ⩽ 10. As an important point, our results show that the adoption of routing using MPR-scheme will result in a significant slowdown in the transmission failure rate. • We propose a construction of three CISTs in a Möbius cube M Q n . • For n ⩾ 7 , the diameters of three CISTs of M Q n we constructed are at most 2n+1. • Protection routing employing MPR-scheme can increase the capability of fault-tolerance. • Protection routing using SPR-scheme ensures that no node other than the destination can receive the complete message. [ABSTRACT FROM AUTHOR]

A new type of sequences called left-child sequences (LC-sequences for short) was recently introduced by Wu et al. (2014) for representing binary trees. They pointed out that such sequences have a natural interpretation from the view point of data structure and gave a characterization of them. Based on this characterization, there is an easily implementing algorithm that uses generate-and-test approach to filter all LC-sequences of binary trees with n internal nodes in lexicographic order, while in general it is not efficient at all. In this paper, we first design two novel rotations that allow us to drastically alter the shape of binary trees (and thus their corresponding LC-sequences). As an application, these operations can be employed to generate all LC-sequences in lexicographic order. Accordingly, we present a more efficient algorithm associated with the new types of rotations for generating all LC-sequences and show that it takes only constant amortized running cost. Moreover, we extend our study to the ranking and unranking problems. By integrating a measure called "left distances" introduced by Mäkinen (1987) to represent binary trees, we develop efficient ranking and unranking algorithms for LC-sequences in lexicographic order. With the help of aggregate analysis, we show that both ranking and unranking algorithms can be run in amortized cost of O (n) time and space. [ABSTRACT FROM AUTHOR]

For the underlying graph G of a network, k (⩾ 2) spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. It is well-known that determining the existence of k CISTs in a graph is an NP-hard problem, even for k = 2. Also, there exists a k -connected graph which does not possess two CISTs for any k ⩾ 2. Accordingly, researches focused on the problem of constructing multiple CISTs in some particular famous networks. Pai and Chang (2016) proposed a unified approach to recursively construct two CISTs with diameter 2 n − 1 in several n -dimensional hypercube-variant networks for n ⩾ 4 , including locally twisted cubes L T Q n and crossed cubes C Q n. Later on, new constructions showed that the diameter of two CISTs can be reduced to 2 n − 2 if n = 4 and 2 n − 3 if n ⩾ 5 for L T Q n , and to 2 n − 2 if n = 4 , 5 and 2 n − 3 if n ⩾ 6 for C Q n. In this paper, we intend to construct more CISTs for those networks that are paid attention. We develop a novel tree searching algorithm, called two-stages tree-searching algorithm (abbreviated as TS 2), which can be used to construct three CISTs of a 6-regular graph if the scale of the graph is not too large and there exist three CISTs for certain. In particular, we demonstrate that three CISTs of L T Q 6 and C Q 6 can be acquired by using TS 2. Moreover, for high-dimensional L T Q n and C Q n with n ⩾ 7 , we show that their three CISTs can be constructed by recursion. Consequently, we obtain the following results: (i) For L T Q n , the diameters of three CISTs we constructed are 11, 12 and 12 when n = 6 , and all are 2 n − 1 when n ⩾ 7 ; (ii) For C Q n , all diameters of three CISTs we constructed are 12 when n = 6 , and 2 n + 1 when n ⩾ 7. [ABSTRACT FROM AUTHOR]

Abstract The ℓ -component connectivity (or ℓ -connectivity for short) of a graph G , denoted by κ ℓ (G) , is the minimum number of vertices whose removal from G results in a disconnected graph with at least ℓ components or a graph with fewer than ℓ vertices. This generalization is a natural extension of the classical connectivity defined in term of minimum vertex-cut. As an application, the ℓ -connectivity can be used to assess the vulnerability of a graph corresponding to the underlying topology of an interconnection network, and thus is an important issue for reliability and fault tolerance of the network. So far, only a little knowledge of results have been known on ℓ -connectivity for particular classes of graphs and small ℓ 's. In a previous work, we studied the ℓ -connectivity on n -dimensional alternating group networks A N n and obtained the result κ 3 (A N n) = 2 n − 3 for n ⩾ 4. In this sequel, we continue the work and show that κ 4 (A N n) = 3 n − 6 for n ⩾ 4. [ABSTRACT FROM AUTHOR]

Let 풯 = {T1,T2,…,Tk} be a set of k ≥ 2 spanning trees in a graph G. The k spanning trees 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. Particularly, 풯 is called a dual-CIST provided k = 2. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. This paper investigates the problem of constructing a dual-CIST in the n-dimensional hierarchical folded cubic network HFQn. The network is a two-level network using folded hypercube FQn as clusters to reduce the diameter, hardware overhead and improve the fault tolerance ability. We propose a recursive algorithm to construct a dual-CIST of HFQn in 풪(22n) time for n ≥ 2, where the time required is the same scale as the number of vertices of HFQn. Also, the diameter of each constructed CIST is 4n + 1. [ABSTRACT FROM AUTHOR]

Given a graph G , a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any two vertices x , y ∈ V ( G ) , the paths joining x and y on these trees have neither vertex nor edge in common, except x and y . Hasunuma [9,10] first introduced the concept of CISTs and conjectured that there are k CISTs in any 2 k -connected graph. Unfortunately, Péterfalvi [16] disproved this conjecture by constructing a k -connected graph, for each k ⩾ 2 , which does not have two CISTs. In this paper, we provide a unified approach for constructing two CISTs in several hypercube-variant networks, including hypercubes, locally twisted cubes, crossed cubes, parity cubes, and Möbius cubes. In particular, for an n -dimensional hypercube-variant network, the diameters of the constructed CISTs are 2 n − 1 . [ABSTRACT FROM AUTHOR]

Let χ i ( G ) and Δ ( G ) denote the incidence coloring number and the maximum degree of a graph G , respectively. An easy observation shows that χ i ( G ) ⩾ Δ ( G ) + 1 . In this paper, we consider incidence coloring number on hypercubes Q n . Based on the technique of Hamming codes, we present algorithms to obtain upper bounds of χ i ( Q n ) for n in certain forms of integers. Let p , q be positive integers. We show that (1) χ i ( Q n ) = n + 1 if n = 2 p − 1 for p ⩾ 1 ; (2) χ i ( Q n ) = n + 2 if the following conditions hold: (i) n = 2 p − 2 for p ⩾ 2 ; (ii) n = 2 p + 2 q − 2 for p , q ⩾ 1 ; (iii) n = 2 p + 2 q − 3 for p , q ⩾ 2 ; and (3) χ i ( Q n ) ⩾ n + 2 otherwise. [ABSTRACT FROM AUTHOR]

The power domination problem is to find a minimum placement of phase measurement units (PMUs) for observing the whole electric power system, which is closely related to the classical domination problem in graphs. For a graph , the power domination number of is the minimum cardinality of a set such that PMUs placed on every vertex of results in all of being observed. A vertex with a PMU observes itself and all its neighbors, and if an observed vertex with degree has only one unobserved neighbor, then the unobserved neighbor becomes observed. Although the power domination problem has been proved to be NP-complete even when restricted to some special classes of graphs, Dorfling and Henning in [M. Dorfling, M.A. Henning, A note on power domination in grid graphs, Discrete Applied Mathematics 154 (2006) 1023–1027] showed that it is easy to determine the power domination number of an grid. Their proof provides an algorithm for giving a minimum placement of PMUs. In this paper, we consider the situation in which PMUs may only be placed within a restricted subset of . Then, we present algorithms to solve this restricted type of power domination on grids under the conditions that consecutive rows or columns form a forbidden zone. Moreover, we also deal with the fault-tolerant measurement placement in the designed scheme and provide approximation algorithms when the number of faulty PMUs does not exceed 3. [Copyright &y& Elsevier]

Abstract: A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. In this paper, we show that the -dimensional hypercube can be laid out using queues for . Our result improves the previously known result for the case . [Copyright &y& Elsevier]

Diagnosability is an important indicator to measure the reliability of multiprocessor systems. If we focus on the status of a particular node, instead of doing global diagnosis, Hsu and Tan introduced the concept of local diagnosis and proposed an extended star structure to diagnose a node under the comparison model. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the extended star structure mentioned above. In this paper, we propose a new testing structure and a corresponding diagnosis algorithm to diagnose a node under the comparison model and better evaluate the local diagnosability. The local diagnosability of a node is upper bounded by its degree in the system. If the local diagnosability of each node equals to its degree in the system, then we say this system has the strong local diagnosability property. Based on the new structure, we provide two sufficient conditions for a multiprocessor system to have the strong local diagnosability property. As applications, we show that the n -dimensional star graph S n and pancake graph P n with faulty links have the strong local diagnosability property no matter how many edges are faulty, provided that each node connects to at least three fault-free links. Moreover, we show that S n and P n keep the strong local diagnosability property even if they have up to 3 n − 12 faulty links, assuming that each node connects to at least two fault-free links. Simulations are presented to show the performance of our tree structure. [ABSTRACT FROM AUTHOR]

• We investigate the problem of constructing a dual-CIST on bicubes B Q n. • A newly generic adjustment scheme can reduce the diameter of dual-CIST. • The diameter of the constructed dual-CIST of B Q n is 2 n − 2 for n ⩾ 5 odd. • The diameter of the constructed dual-CIST of B Q n is 2 n − 3 for n ⩾ 6 even. • As a by-product, a folded hypercube F Q n admits a dual-CIST with diameter 2 n − 2. Recently, an innovative hypercube-variant network called bicube, denoted as B Q n , has been proposed to possess both short diameter and symmetry advantages. Unlike other existing hypercube-variant networks, they lose their symmetry in pursuit of short diameters. For solving the problems of fault-tolerant transmission and secure message distribution in a reliable network, one solution suggested a dual-CIST (two completely independent spanning trees) to design a multi-path routing (e.g., a recently proposed secure-protection routing). We can make the construction using the standard arrangement guideline (SAG) like the hypercubes to obtain a dual-CIST with a diameter of 2 n − 1 on B Q n. This paper proposes a newly generic adjustment scheme (GAS) for reducing the diameter of the dual-CIST under this construction. As a result, the diameter of T i for i = 1 , 2 we constructed for B Q n are as follows: diam (T i) = { 7 if n = 4 ; 2 n − 2 if n ⩾ 5 and n is odd ; 2 n − 3 if n ⩾ 6 and n is even. [ABSTRACT FROM AUTHOR]

Spanning trees T 1 , T 2 , ... , T k (k ≥ 2) in a graph G are called completely independent spanning trees (CISTs for short) if for any two vertices x , y of G , the paths joining x and y in these k trees are pairwise openly disjoint. Hong and Zhang (2018) recently showed that a sufficient condition for Hamiltonian graphs still suffices for the existence of two CISTs. That is, if G is a graph with n vertices and | N (x) ∪ N (y) | ≥ n 2 , | N (x) ∩ N (y) | ≥ 3 for every two nonadjacent vertices x , y of G and n ≥ 5 , then G admits two CISTs. In this note, we first attend that the restriction on the number of vertices in the statement should be revised. Moreover, we point out that there is a flaw in their proof. Accordingly, we give an amendment to correct the proof. [ABSTRACT FROM AUTHOR]

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\in \lbrace 2,n\rbrace , 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,k from these path lengths. [ABSTRACT FROM PUBLISHER]

Abstract: Let be a set of points arranged in convex position in the plane and suppose that all points of are labeled from 1 to in clockwise direction. A planar path on is a path whose edges connect all points of with straight line segments such that no two edges of cross. Flipping an edge on means that a new path is obtained from by a single edge replacement. In this paper, we provide efficient algorithms to generate all planar paths. With the help of a loopless algorithm to produce a set of 2-way binary-reflected Gray codes, the proposed algorithms generate the next planar path by means of a flip and such that the number of position changes for points in the path has a constant amortized upper bound. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

Pallo and Wu et al. respectively introduced the left-weight sequences (LW-sequences) and right-weight sequences (RW-sequences) for representing binary trees. In this paper, we introduce two new types of binary tree sequences called the left-child sequences (LC-sequences) and right-child sequences (RC-sequences). Next, we propose a loopless algorithm associated with rotations of binary trees for generating LW-, RW-, LC-, and RC-sequences simultaneously. Moreover, we show that LW- and RW-sequences are generated in Gray-code order, and LC- and RC-sequences are generated so that each sequence can be obtained from its predecessor by changing at most two digits. Our algorithm is shown to be more efficient in both space and time than the existing known algorithms. [ABSTRACT FROM AUTHOR]