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]

A set of $k~(\geqslant 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. [ABSTRACT FROM AUTHOR]