Search

The design of interconnection networks is a fundamental aspect of high-performance computing (HPC) systems. Among the available topologies, the Galaxyfly network stands out as a low-diameter and flexible-radix network for HPC applications. Given the paramount importance of collective communication in HPC performance, in this paper, we present two different all-to-all broadcast algorithms for the Galaxyfly network, which adhere to the supernode-first rule and the router-first rule, respectively. Our performance evaluation validates their effectiveness and shows that the first algorithm has a higher degree of utilization of network channels, and that the second algorithm can significantly reduce the average time for routers to collect packets from the supernode. [ABSTRACT FROM AUTHOR]

The generalized connectivity is a generalization of traditional connectivity, which is a parameter that can measure the capability of connecting vertices in G. The pancake graph has some desirable properties to design interconnection networks. In this paper, we obtain that the generalized 4-connectivity of pancake graph P n is n − 2 , that is, there are (n − 2) internally disjoint S -trees connecting any four arbitrary vertices x , y , z and w of P n , where S = { x , y , z , w }. As a corollary, the generalized 3-connectivity of the pancake graph P n can be obtained directly. [ABSTRACT FROM AUTHOR]

The generalized connectivity of a graph G , denoted as κ k (G) , is a generalization of the traditional connectivity and is a parameter to measure the capability of connecting multiple vertices in G. The divide-and-swap cube D S C n is a variant of the hypercube with a nice hierarchical structure and plentiful properties. This paper investigates the generalized connectivity on D S C n. We obtain the result κ 4 (D S C n) = d , where d = log 2 ⁡ n ≥ 1 , by the construction showing that there are d internally disjoint trees connecting any four arbitrary vertices of D S C n. As a corollary, one can directly obtain κ 3 (D S C n) = d. • The generalized k -connectivity κ k (G) is the maximum number of internally disjoint trees connecting any k vertices of G. • The divide-and-swap cube D S C n is a variant of the hypercube with a nice hierarchical structure and plentiful properties. • This paper obtains the result κ 4 (D S C n) = d , where d = log 2 ⁡ n ≥ 1. • As a corollary, we also obtain κ 3 (D S C n) = d. [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]

A connected graph |$G$| is called strongly Menger (edge) connected if for any two distinct vertices |$x,y$| of |$G$|⁠ , there are |$\min \{\textrm{deg}_G(x), \textrm{deg}_G(y)\}$| internally disjoint (edge disjoint) paths between |$x$| and |$y$|⁠. Motivated by parallel routing in networks with faults, Oh and Chen (resp. Qiao and Yang) proposed the (fault-tolerant) strong Menger (edge) connectivity as follows. A graph |$G$| is called |$m$| -strongly Menger (edge) connected if |$G-F$| remains strongly Menger (edge) connected for an arbitrary vertex set |$F\subseteq V(G)$| (resp. edge set |$F\subseteq E(G)$|⁠) with |$|F|\leq m$|⁠. A graph |$G$| is called |$m$| -conditional strongly Menger (edge) connected if |$G-F$| remains strongly Menger (edge) connected for an arbitrary vertex set |$F\subseteq V(G)$| (resp. edge set |$F\subseteq E(G)$|⁠) with |$|F|\leq m$| and |$\delta (G-F)\geq 2$|⁠. In this paper, we consider strong Menger (edge) connectedness of the augmented |$k$| -ary |$n$| -cube |$AQ_{n,k}$|⁠ , which is a variant of |$k$| -ary |$n$| -cube |$Q_n^k$|⁠. By exploring the topological proprieties of |$AQ_{n,k}$|⁠ , we show that |$AQ_{n,3}$| (resp. |$AQ_{n,k}$|⁠ , |$k\geq 4$|⁠) is |$(4n-9)$| -strongly (resp. |$(4n-8)$| -strongly) Menger connected for |$n\geq 4$| (resp. |$n\geq 2$|⁠) and |$AQ_{n,k}$| is |$(4n-4)$| -strongly Menger edge connected for |$n\geq 2$| and |$k\geq 3$|⁠. Moreover, we obtain that |$AQ_{n,k}$| is |$(8n-10)$| -conditional strongly Menger edge connected for |$n\geq 2$| and |$k\geq 3$|⁠. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults. [ABSTRACT FROM AUTHOR]

With the increasing popularity and diversity of network environments, it is crucial to assess the fault tolerance and stability of the network. Structure connectivity and substructure connectivity are two novel indicators that can better measure the network's fault tolerance compared to traditional connectivity. Additionally, analyzing a network's minimum structure cuts and minimum substructure cuts is an interesting and important subject. For a graph G, let R and M be two connected subgraphs of G. An R-structure cut (resp. R-substructure cut) of G is a set of subgraphs of G, such that each subgraph in the set is isomorphic to R (resp. is isomorphic to a connected subgraph of R), whose deletion disconnects G. If the removal of any minimum R-structure cut (resp. R-substructure cut) divides G into exactly two components, one of which is isomorphic to M, then G is referred to as hyper R | M -connected (resp. hyper sub- R | M -connected). This paper first studies the K 1 , r -structure connectivity and sub- K 1 , r -structure connectivity of hierarchical folded cubic network HFQ n . Specifically, we determine both of them are ⌈ n + 2 2 ⌉ for n ≥ 7 and 2 ≤ r ≤ n - 1 . Then, we prove that HFQ n is hyper K 1 , r | K 1 -connected and hyper sub- K 1 , r | K 1 -connected. [ABSTRACT FROM AUTHOR]

The r -component connectivity c κ r (G) of a non-complete graph G is the minimum number of vertices whose removal results in a disconnected graph with at least r components. This parameter generalizes the classical connectivity. Hence, it is an important parameter to evaluate the reliability and fault tolerance of a network. Let Γ n be the n -dimensional Cayley graph generated by transposition trees, and g (Γ n) denote the girth of Γ n (i.e., the length of a shortest cycle of Γ n). It has been shown that either g (Γ n) = 4 or g (Γ n) = 6. In this paper, we obtain that c κ 3 (Γ n) = 2 n − 4 if g (Γ n) = 4 and c κ 3 (Γ n) = 2 n − 3 if g (Γ n) = 6 for n ≥ 4. As corollaries, the 3-component connectivity of the star graph S n and the bubble-sort graph B n can be obtained directly. Also, the above consequences explicitly point out that there is a flaw in the recent result of Xu et al., (2020). • The r -component connectivity c κ r (G) is a generalization of the traditional connectivity κ (G) of a graph G. • The 3-component connectivity of the Cayley graph generated by trees is determined for n ≥ 4. • As corollaries, the 3-component connectivity of B n and S n can be obtained directly for n ≥ 4. [ABSTRACT FROM AUTHOR]

For an integer |$\ell \geqslant 2$|⁠ , the |$\ell $| -component connectivity (resp. |$\ell $| -component edge connectivity) of a graph |$G$|⁠ , denoted by |$\kappa _{\ell }(G)$| (resp. |$\lambda _{\ell }(G)$|⁠), is the minimum number of vertices (resp. edges) whose removal from |$G$| results in a disconnected graph with at least |$\ell $| components. The two parameters naturally generalize the classical connectivity and edge connectivity of graphs defined in term of the minimum vertex-cut and the minimum edge-cut, respectively. The two kinds of connectivities can help us to measure the robustness of the graph corresponding to a network. In this paper, by exploring algebraic and combinatorial properties of |$n$| -dimensional balanced hypercubes |$BH_n$|⁠ , we obtain the |$\ell $| -component (edge) connectivity |$\kappa _{\ell }(BH_n)$| (⁠|$\lambda _{\ell }(BH_n)$|⁠). For |$\ell $| -component connectivity, we prove that |$\kappa _2(BH_n)=\kappa _3(BH_n)=2n$| for |$n\geq 2$|⁠ , |$\kappa _4(BH_n)=\kappa _5(BH_n)=4n-2$| for |$n\geq 4$|⁠ , |$\kappa _6(BH_n)=\kappa _7(BH_n)=6n-6$| for |$n\geq 5$|⁠. For |$\ell $| -component edge connectivity, we prove that |$\lambda _3(BH_n)=4n-1$|⁠ , |$\lambda _4(BH_n)=6n-2$| for |$n\geq 2$| and |$\lambda _5(BH_n)=8n-4$| for |$n\geq 3$|⁠. Moreover, we also prove |$\lambda _\ell (BH_n)\leq 2n(\ell -1)-2\ell +6$| for |$4\leq \ell \leq 2n+3$| and the upper bound of |$\lambda _\ell (BH_n)$| we obtained is tight for |$\ell =4,5$|⁠. [ABSTRACT FROM AUTHOR]

Let G be a connected graph and S ⊆ V (G) with | S | ≥ 2. A tree T in G is called an S -tree if S ⊆ V (T). Two S -trees T 1 and T 2 are internally disjoint if E (T 1) ∩ E (T 2) = 0̸ and V (T 1) ∩ V (T 2) = S. For an integer k ≥ 2 , the generalized k -connectivity of a graph G , denoted by κ k (G) , is defined as κ k (G) = min { κ G (S) : S ⊆ V (G) and | S | = k } , where κ G (S) denotes the maximum number of pairwise internally disjoint S -trees in G. The generalized connectivity is a generalization of traditional connectivity. Let G n be the class of connected graphs of order n and let f (n , k , t) = min G ∈ G n { | E (G) | : κ k (G) = t }. In this paper, we prove f (n , k , t) ≥ ⌈ t (t + 2) 2 t + 2 n ⌉ for 4 ≤ k ≤ n and 1 ≤ t ≤ n − ⌈ k 2 ⌉. In particular, the lower bound is sharp when k = 4 and t = 2 (i.e., we explicitly provide a family of graphs fulfilling the bound in this case), improving the known results of Sun et al. (2021). [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]

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]

Fault detection and localization are vital for ensuring the stability of data center networks (DCNs). Specifically, adaptive fault diagnosis is deemed a fundamental technology in achieving the fault tolerance of systems. The highly scalable data center network (HSDC) is a promising structure of server-centric DCNs, as it exhibits the capacity for incremental scalability, coupled with the assurance of low cost and energy consumption, low diameter, and high bisection width. In this paper, we first determine that both the connectivity and diagnosability of the m-dimensional complete HSDC, denoted by H S D C m (m) , are m. Further, we propose an efficient adaptive fault diagnosis algorithm to diagnose an H S D C m (m) within three test rounds, and at most N + 4 m (m − 2) tests with m ≥ 3 (resp. at most nine tests with m = 2 ), where N = m · 2 m is the total number of nodes in H S D C m (m) . Our experimental outcomes demonstrate that this diagnosis scheme of HSDC can achieve complete diagnosis and significantly reduce the number of required tests. [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]

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]

"Linearly many faults" is a phenomenon observed by Cheng and Lipták in which a specific structure emerges when a graph is disconnected and often occurs in various interconnection networks. This phenomenon means that if a certain number of vertices or edges are deleted from a graph, the remaining part either stays connected or breaks into one large component along with smaller components with just a few vertices. This phenomenon can be observed in many types of graphs and has important implications for network analysis and optimization. In this paper, we first validate the phenomenon of linearly many faults for surviving graph of a burnt pancake graph B P n when removing any edge subset with a size of approximately six times λ (B P n) . For graph G, the ℓ-component edge connectivity denoted as λ ℓ (G) (resp., the ℓ-extra edge connectivity denoted as λ (ℓ) (G) ) is the cardinality of a minimum edge subset S such that G − S is disconnected and has at least ℓ components (resp., each component of G − S has at least ℓ + 1 vertices). Both λ ℓ (G) and e λ (ℓ) (G) are essential metrics for network reliability assessment. Specifically, from the property of "linearly many faults", we may further prove that λ 5 (B P n) = λ (3) (B P n) + 3 = 4 n − 3 for n ⩾ 5 ; λ 6 (B P n) = λ (4) (B P n) + 4 = 5 n − 4 and λ 7 (B P n) = λ (5) (B P n) + 5 = 6 n − 5 for n ⩾ 6 . [ABSTRACT FROM AUTHOR]

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]

A long-standing conjecture mentions that a k -connected graph G admits k independent spanning trees (ISTs for short) rooted at an arbitrary node of G . An n -dimensional twisted cube, denoted by T Q n , is a variation of hypercube with connectivity n and has many features superior to those of hypercube. Yang (2010) first proposed an algorithm to construct n edge-disjoint spanning trees in T Q n for any odd integer n ⩾ 3 and showed that half of them are ISTs. At a later stage, Wang et al. (2012) inferred that the above conjecture in affirmative for T Q n by providing an O ( N log N ) time algorithm to construct n ISTs, where N = 2 n is the number of nodes in T Q n . However, this algorithm is executed in a recursive fashion and thus is hard to be parallelized. In this paper, we revisit the problem of constructing ISTs in twisted cubes and present a non-recursive algorithm. Our approach can be fully parallelized to make the use of all nodes of T Q n as processors for computation in such a way that each node can determine its parent in all spanning trees directly by referring its address and tree indices in O ( log N ) time. [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]

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]

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]

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]

A set of k spanning trees rooted at the same vertex r in a graph G is called independent [and the trees are called independent spanning trees (ISTs)] if, for any vertex x ≠ r, the k paths from x to r, one path in each tree, are internally disjoint. The design of ISTs on graphs has applications to fault-tolerant broadcasting and secure message distribution in networks. It was conjectured that, for any k-connected graph, there exist k ISTs rooted at any vertex of the graph. The conjecture has been proved true for k-connected graphs with k ≤ 4, and remains open otherwise. In this paper, we deal with the problem of constructing ISTs on the Cartesian product of a sequence of hybrid graphs, including cycles and complete graphs. Consequently, this result generalizes a number of previous works. Moreover, the construction is shown to be optimal in the sense that the heights of ISTs are minimized. [ABSTRACT FROM AUTHOR]

A t-ary tree is a rooted tree such that every internal node has exactly t disjoint subtrees. Recently, a concise representation called right-distance sequences (RD-sequences) was introduced to represent t-ary trees and their generalization called non-regular trees. In particular, a loopless algorithm has been proposed by Wu et al. ((2010) Loopless generation of non-regular trees with a prescribed branching sequence. Comput. J., 53, 661–666) for generating non-regular trees (and thus of t-ary trees) encoded by RD-sequences in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of t-ary trees with n internal nodes. The time complexity and space requirement in both algorithms are O(max{n2,tn}) and O(tn), respectively. As a by-product, we have an improvement on ranking and unranking t-ary trees encoded by z-sequences in a Gray-code order. [ABSTRACT FROM PUBLISHER]

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]

Given an edge-weighted undirected graph G and two prescribed vertices u and v, a next-to-shortest ( u, v)-path is a shortest ( u, v)-path amongst all ( u, v)-paths having length strictly greater than the length of a shortest ( u, v)-path. In this paper, we deal with the problem of computing a next-to-shortest ( u, v)-path. We propose an ${\mathcal{O}}(n^{2})$ time algorithm for solving this problem, which significantly improves the bound of a previous one in ${\mathcal{O}}(n^{3})$ time where n is the number of vertices in G. [ABSTRACT FROM AUTHOR]

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]

Abstract: Ordered trees are called non-regular trees with a prescribed branching sequence (or non-regular trees for short) if their internal nodes have a pre-specified degree sequence in preorder list. This article presents two main results. First, we develop a simple algorithm to generate all non-regular trees in lexicographic order using RD-sequences defined by [R.-Y. Wu, J.-M. Chang, Y.-L. Wang, Loopless generation of non-regular trees with a prescribed branching sequence, The Computer Journal 53 (2010) 661–666]. Then, by analyzing the structure of a coding tree, this algorithm is proved to run in constant amortized time. Next, we propose efficient ranking algorithm (i.e., determining the rank of a given non-regular tree in such an order) and unranking algorithm (i.e., converting a positive integer to its corresponding RD-sequence). [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]

Abstract: Two spanning trees of a graph are said to be independent if they are rooted at the same vertex , and for each vertex in , the two different paths from to , one path in each tree, are internally disjoint. A set of spanning trees of is independent if they are pairwise independent. The construction of multiple independent spanning trees has many applications in network communication. For instance, it is useful for fault-tolerant broadcasting and secure message distribution. A recursive circulant graph has vertices labeled from 0 to , where , , and , and two vertices are adjacent if and only if there is an integer with such that  (mod ). In this paper, we propose an algorithm to construct multiple independent spanning trees on a recursive circulant graph with , where the number of independent spanning trees matches the connectivity of . [Copyright &y& Elsevier]

Abstract: Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2002) 71–84] proposed the class of augmented cubes as a variation of hypercubes and showed that augmented cubes possess several embedding properties that the hypercubes and other variations do not possess. Recently, Hsu et al. [H.-C. Hsu, P.-L. Lai, C.-H. Tsai, Geodesic-pancyclicity and balanced pancyclicity of augmented cubes, Information Processing Letters 101 (2007) 227–232] showed that the n-dimensional augmented cube , n ⩾2, is weakly geodesic-pancyclic, i.e., for each pair of vertices and for each integer ℓ satisfying where d(u, v) denotes the distance between u and v in , there is a cycle of length ℓ that contains a u-v geodesic. In this paper, we obtain a stronger result by proving that , n ⩾2, is indeed geodesic-pancyclic, i.e., for each pair of vertices and for each integer ℓ satisfying , every u-v geodesic lies on a cycle of length ℓ. To achieve the result, we first show that , n ⩾3, remains panconnected (and thus is also edge-pancyclic) if is any faulty vertex. The result of fault-tolerant panconnectivity is the best possible in the sense that the number of faulty vertices in , n ⩾3, cannot be increased. [Copyright &y& Elsevier]

Abstract: A king x in a tournament T is a player who beats any other player y directly (i.e., ) or indirectly through a third player z (i.e., ). For , let denote the number of third players through which x beats y indirectly. Then, a king x is strong if the following condition is fulfilled: whenever . In this paper, a result shows that for a tournament on n players there exist exactly k strong kings, , with the following exceptions: when n is odd and when n is even. Moreover, we completely determine the uniqueness of tournaments. [Copyright &y& Elsevier]

Abstract: Cycle-embedding is an important issue in evaluating the efficiency of interconnection networks and is also an extension of the theoretical research on Hamiltonicity. In this paper, we study the fault-tolerant Hamiltonicity of alternating group graphs which were recently proposed as interconnection topologies for parallel and distributed systems. A cycle of length ℓ is said to be an ℓ-cycle. Let F be a set of faulty vertices in an n-dimensional alternating group graph AG n and let m be the number of vertices in AG n − F. A previous result in [J.-M. Chang, J.-S. Yang, Y.-L. Wang, Y. Cheng, Panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs, Networks 44 (2004) 302–310] showed that, for n ⩾4, AG n − F is Hamiltonian (i.e., AG n − F possesses a Hamiltonian cycle) if ∣F∣⩽ n −2, and AG n − F is Hamiltonian-connected (i.e., every two vertices of AG n − F are connected by a Hamiltonian path) if ∣F∣⩽ n −3. In this paper, we show the following results: (i) AG n − F is pancyclic (i.e., AG n − F contains an ℓ-cycle for each ℓ with 3⩽ℓ⩽ m) if ∣F∣⩽ n −2; (ii) AG n − F is vertex-pancyclic (i.e., every vertex of AG n − F is contained in an ℓ-cycle for each ℓ with 3⩽ℓ⩽ m) if ∣F∣⩽ n −3; and (iii) AG n − F is edge 4-pancyclic (i.e., every edge of AG n − F is contained in an ℓ-cycle for each ℓ with 4⩽ℓ⩽ m) if ∣F∣⩽ n −4. The first result is an improvement over the previous one and the last two results are new characterization of fault-tolerant pancyclicity on AG n . All the results we achieved are the best possible in the sense that the number of faulty vertices cannot be increased. [Copyright &y& Elsevier]

Abstract: A shortest path connecting two vertices and is called a - geodesic. The distance between and in a graph G, denoted by , is the number of edges in a - geodesic. A graph G with n vertices is panconnected if, for each pair of vertices and for each integer k with , there is a path of length k in G that connects and . A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices , every - geodesic lies on every cycle of length k satisfying . In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a transformation on binary trees using new types of rotations. Each of the newly proposed rotations is permitted only at nodes on the left-arm or the right-arm of a tree. Consequently, we develop a linear time algorithm with at most rotations for converting weight sequences between any two binary trees. In particular, from an analysis of aggregate method for a sequence of rotations, each rotation of the proposed algorithm can be performed in a constant amortized time. Next, we show that a specific directed rooted tree called rotation tree can be constructed using one of the new type rotations. As a by-product, a naive algorithm for enumerating weight sequences of binary trees in lexicographic order can be implemented by traversing the rotation tree. [Copyright &y& Elsevier]

There are a number of ways of measuring the difference in shape between two rooted binary trees with the same number of leaves. Pallo ( Computer Journal , 9, 171–175, 1986) introduced a left weight sequence, which is a sequence of positive integers, to characterize the structure of a binary tree. By applying the AVL tree transformation on binary trees, we develop an algorithm for the efficient transformation of the left weight sequences between two binary trees. [ABSTRACT FROM AUTHOR]

Let G =( V , E ) be a graph with vertex set V of size n and edge set E of size m . A vertex v ? V is called a hinge vertex if there exist two vertices in V \{ v } such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O ( n 2 ) time complexity and O ( m ) message complexity. In particular, the total messages exchanged during the algorithm are at most 2 m (log n + n log n +1) bits. [ABSTRACT FROM AUTHOR]

An induced matching M of a graph G is a set of pairwise nonadjacent edges such that no two edges of M are joined by an edge in G. The problem of finding a maximum induced matching is known to be NP-hard even for bipartite graphs of maximum degree four. In this paper, we study the maximum induced matching problem on classes of graphs related to AT-free graphs. We first define a wider class of graphs called the line-asteroidal triple-free (LAT-free) graphs which contains AT-free graphs as a subclass. By examining the square of line graph of LAT-free graphs, we give a characterization of them and apply this for showing that the maximum induced matching problem and a generalization, called the maximum δ-separated matching problem, on LAT-free graphs can be solved in polynomial time. In fact, our result can be extended to the classes of graphs with bounded asteroidal index. Next, we propose a linear-time algorithm for finding a maximum induced matching in a bipartite permutation (bipartite AT-free) graph using the greedy approach. Moreover, we show that using the same technique the minimum chain subgraph cover problem on bipartite permutation graphs can be solved with the same time complexity. [Copyright &y& Elsevier]

A distance-k dominating set D of a directed graph G is a set of vertices such that for every vertex v of G, there is a vertex u∈D and the distance between u and v is at most k. Minimum distance-k dominating set is especially important in communication networks for distributed data structures and for server placement. In this paper, we show that there is a unique minimum distance-k dominating set for k=1,2 in a directed split-star, which has recently been developed as a new model of the interconnection network for parallel and distributed computing systems. Moreover, we shall present simple distributed algorithms for finding such sets. [Copyright &y& Elsevier]

The k -ary n -cube Q n k serves as an indispensable interconnection network in the design of data center networks, network-on-chips, and parallel computing systems since it possesses numerous attractive properties. In these parallel architectures, the paired (or unpaired) many-to-many m -disjoint path cover (m -DPC) plays a significant role in message transmission. Nevertheless, the construction of m -DPC is severely obstructed by large-scale edge faults due to the rapid growth of the system scale. In this paper, we investigate the existence of paired 2-DPC in Q n k under the partitioned edge fault (PEF) model, which is a novel fault model for enhancing the networks' fault-tolerance related to path embedding problem. We exploit this model to evaluate the edge fault-tolerance of Q n k when a paired 2-DPC is embedded into Q n k. Compared to the other known works, our results can help Q n k to achieve large-scale edge fault-tolerance. • This research studies the existence of paired 2-disjoint path cover in k -ary n -cubes in the presence of large-scale faulty edges. • Our findings generalize the result in [50] from the theoretical perspective. • Our results provide the exponential edge fault-tolerance compared to previous similar works. [ABSTRACT FROM AUTHOR]

The k -dimensional data center network with n port switches, denoted by D k,n , has been proposed as a structure of the server-centric network and it was required to have a high reliability on data transmission. A set of t spanning trees in a graph G are called completely independent spanning trees (CISTs for short) if for every pair of nodes x, y ∈ V (G), the paths joining x and y in any two trees have neither node nor edge in common, except for x and y. In particular, if t = 2 , the two CISTs are called a dual-CIST. Although it has been proved that determining if a graph G admits t CISTs is an NP-complete problem even for t = 2 , the construction of multiple CISTs on the underlying graph of a network has applications in the fault-tolerance of data transmission. In this paper, we provide a recursive construction for building a dual-CIST on D k,n for k ≥ 0 and n ≥ 6. [ABSTRACT FROM AUTHOR]

Given a connected graph |$G$| and a positive integer |$\ell $|⁠ , the |$\ell $| -extra (resp. |$\ell $| -component) edge connectivity of |$G$|⁠ , denoted by |$\lambda ^{(\ell)}(G)$| (resp. |$\lambda _{\ell }(G)$|⁠), is the minimum number of edges whose removal from |$G$| results in a disconnected graph so that every component has more than |$\ell $| vertices (resp. so that it contains at least |$\ell $| components). This naturally generalizes the classical edge connectivity of graphs defined in term of the minimum edge cut. In this paper, we proposed a general approach to derive component (resp. extra) edge connectivity for a connected graph |$G$|⁠. For a connected graph |$G$|⁠ , let |$S$| be a vertex subset of |$G$| for |$G\in \{\Gamma _{n}(\Delta),AG_n,S_n^2\}$| such that |$|S|=s\leq |V(G)|/2$|⁠ , |$G[S]$| is connected and |$|E(S,G-S)|=\min \limits _{U\subseteq V(G)}\{|E(U, G-U)|: |U|=s, G[U]\ \textrm{is connected}\ \}$|⁠ , then we prove that |$\lambda ^{(s-1)}(G)=|E(S,G-S)|$| and |$\lambda _{s+1}(G)=|E(S,G-S)|+|E(G[S])|$| for |$s=3,4,5$|⁠. By exploring the reliability analysis of |$AG_n$| and |$S_n^2$| based on extra (component) edge faults, we obtain the following results: (i) |$\lambda _3(AG_n)-1=\lambda ^{(1)}(AG_n)=4n-10$|⁠ , |$\lambda _4(AG_n)-3=\lambda ^{(2)}(AG_n)=6n-18$| and |$\lambda _5(AG_n)-4=\lambda ^{(3)}(AG_n)=8n-24$|⁠ ; (ii) |$\lambda _3(S_n^2)-1=\lambda ^{(1)}(S_n^2)=4n-8$|⁠ , |$\lambda _4(S_n^2)-3=\lambda ^{(2)}(S_n^2)=6n-15$| and |$\lambda _5(S_n^2)-4=\lambda ^{(3)}(S_n^2)=8n-20$|⁠. This general approach maybe applied to many diverse networks. [ABSTRACT FROM AUTHOR]

• The generalized k -connectivity κ k (G) is the maximum number of internally disjoint trees connecting any k vertices of G. • The substructure properties of the n -dimensional augmented cube A Q n are given. • The results of κ 3 (A Q n) = 2 n − 2 for n = 3 or n ≥ 5 are derived. • κ 3 (A Q 4) = 5 is derived. Given a connected graph G and S ⊆ V (G) with | S | ≥ 2 , a tree T in G is called an S -Steiner tree (or S -tree for short) if S ⊆ V (T). Two S -trees T 1 and T 2 are internally disjoint if E (T 1) ∩ E (T 2) = ∅ and V (T 1) ∩ V (T 2) = S. The packing number of internally disjoint S -trees, denoted as κ G (S) , is the maximum size of a set of internally disjoint S -trees in G. For an integer k ≥ 2 , the generalized k -connectivity (abbr. κ k -connectivity) of a graph G is defined as κ k (G) = min { κ G (S) | S ⊆ V (G) and | S | = k }. The n -dimensional augmented cube, denoted as A Q n , is an important variant of the hypercube that possesses several desired topology properties such as diverse embedding schemes in applications of parallel computing. In this paper, we focus on the study of constructing internally disjoint S -trees with | S | = 3 in A Q n. As a result, we completely determine the κ 3 -connectivity of A Q n as follows: κ 3 (A Q 4) = 5 and κ 3 (A Q n) = 2 n − 2 for n = 3 or n ≥ 5. [ABSTRACT FROM AUTHOR]

Recently, network connectivity analysis in terms of reliability has received attention from the network research community. Although traditional connectivity can be used to assess the strength of the connection between two nodes, however, such measures are inadequate for evaluating the connectivity among a set of multiple nodes in a network. Given a set S of vertices in a graph G with | S | ⩾ 2 , we say that a tree in G is an S -tree if it connects all vertices of S. Two S -trees T and T ′ in G are internally disjoint if E (T) ∩ E (T ′) = 0̸ and V (T) ∩ V (T ′) = S. Let κ G (S) denote the maximum number of S -trees in G such that every pair of them are internally disjoint. For an integer k ⩾ 2 , the generalized k -connectivity of graph G is defined as κ k (G) = m i n { κ G (S) ∣ S ⊆ V (G) and | S | = k }. In this paper, we investigate the problem of finding the generalized 3-connectivity of the n -dimensional balanced hypercube B H n , which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, we prove that κ 3 (B H n) = 2 n − 1 for n ⩾ 1. [ABSTRACT FROM AUTHOR]

Traditional model compression techniques are dependent on handcrafted features and require domain experts, with a tradeoff between model size, speed, and accuracy. This study proposes a new approach toward resolving model compression problems. Our approach combines reinforcement-learning-based automated pruning and knowledge distillation to improve the pruning of unimportant network layers and the efficiency of the compression process. We introduce a new state quantity that controls the size of the reward and an attention mechanism that reinforces useful features and attenuates useless features to enhance the effects of other features. The experimental results show that the proposed model is superior to other advanced pruning methods in terms of the computation time and accuracy on CIFAR-100 and ImageNet dataset, where the accuracy is approximately 3% higher than that of similar methods with shorter computation times. [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 ℓ -extra (resp. ℓ -component) edge connectivity λ (ℓ) (G) (resp. λ ℓ (G)) is a good measure of robustness for networks. • The relationship between ℓ -extra edge connectivity and (ℓ + 2)-component edge connectivity for regular graphs is given. • As applications, the extra edge connectivity and component edge connectivity are explored for some well-known networks. A conditional connectivity is the generalization of the traditional connectivity and can provide more accurate measures regarding the reliability of a large-scale multiprocessor system. The extra edge connectivity and component edge connectivity are two parameters for the reliability evaluation. Although these two measures have attracted considerable attention and been determined for many classes of graphs in recent years, they are established independently. In this paper, we determine the relationship between extra edge connectivities and component edge connectivities of regular networks. Using this relationship, the extra edge connectivity and component edge connectivity are explored for some well-known graphs, including BC graphs, data center networks, augmented k -ary n -cubes, hierarchical star networks, burnt pancake graphs, (n , k) -star graphs, etc. [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]