Search

Let = { T 1 , T 2 , ... , T k } 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 H F Q n . The network is a two-level network using folded hypercube F Q n 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 H F Q n in (2 2 n) time for n ≥ 2 , where the time required is the same scale as the number of vertices of H F Q n . Also, the diameter of each constructed CIST is 4 n + 1. [ABSTRACT FROM AUTHOR]

The Bouwer graph B (k , m , n) , proposed in 1970, is defined for every triple (k , m , n) of integers greater than 1 with 2 m ≡ 1 (mod n). It has many good properties, such as vertex-transitive and edge-transitive. Conder and Žitnik used a cycle-counting argument to prove that almost all of the Bouwer graphs are half-arc-transitive in 2016. In this paper, by exploring the structure properties of B (k , m , n) , we investigate some reliability measures, including super connectivity and super-edge connectivity, and show that the super connectivity and super-edge connectivity of the Bouwer graph are both 4 k − 2 for k ≥ 3 , m ≥ 4 and n > 7. [ABSTRACT FROM AUTHOR]

For an integer ℓ ≥ 2 , the ℓ -component connectivity 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 naturally generalizes the classical connectivity of graphs defined in term of the minimum vertex-cut. This kind of connectivity can help us to measure the robustness of the graph corresponding to a network. The hierarchical star networks H S n , proposed by Shi and Srimani, is a new level interconnection network topology, and uses the star graphs as building blocks. In this paper, by exploring the combinatorial properties and fault-tolerance of H S n , we study the ℓ -component connectivity of hierarchical star networks H S n . We obtain the results: κ 3 (H S n) = 2 n − 2 , κ 4 (H S n) = 3 n − 3 and κ 5 (H S n) = 4 n − 5 for n ≥ 5. [ABSTRACT FROM AUTHOR]

The exchanged crossed cube, denoted by E C Q (s , t) , is a novel interconnection network with fewer edges and smaller diameter compared to other variations of the corresponding hypercube. The linear array, denoted by L n , is one of the most popular topologies in optical networks. This paper addresses the routing and wavelength assignment for realizing E C Q (s , t) communication pattern on wavelength division multiplexing (WDM) optical network L n , where n = s + t + 1. We prove that the congestion for E C Q (s , t) on L n is equal to 2 s + t − 1 + ⌊ 2 t / 3 ⌋ , which is the lower bound of the minimum number of required wavelengths. In addition, an embedding scheme and an optimal wavelength assignment algorithm that achieve this bound are also proposed. [ABSTRACT FROM AUTHOR]