Search

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]

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]