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]

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]

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]

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]