Search

"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]

At present, the reliability of interconnection networks of multiprocessing systems has become a hot topic of research concern for parallel computer systems. Conditional connectivity is an important parameter to measure the reliability of an interconnected network. In reality, the failure of one node will inevitably have a negative impact on the surrounding nodes. Often it is the specific structures that fail in an interconnected network. Therefore, we propose two novel kinds of connectivity, called $ g $-extra $ H $-structure connectivity and $ g $-extra $ H $-substructure connectivity, to go for a more accurate measure of the reliability of the network. Hypercube network is the most dominant interconnection network topology used by computer systems today, for example, the famous parallel computing systems Cray $ T3D $, Cray $ T3E $, $ IBM $ Blue Gene, etc. are built with it as the interconnection network topology. In this paper, we obtain the results of the $ g $-extra $ H $-structure connectivity and the $ g $-extra $ H $-substructure connectivity of the hypercubes when the specific structure is $ P_k $ and $ g = 1 $.

At present, the reliability of interconnection networks of multiprocessing systems has become a hot topic of research concern for parallel computer systems. Conditional connectivity is an important parameter to measure the reliability of an interconnected network. In reality, the failure of one node will inevitably have a negative impact on the surrounding nodes. Often it is the specific structures that fail in an interconnected network. Therefore, we propose two novel kinds of connectivity, called g-extra H-structure connectivity and g-extra H-substructure connectivity, to go for a more accurate measure of the reliability of the network. Hypercube network is the most dominant interconnection network topology used by computer systems today, for example, the famous parallel computing systems Cray T3D, Cray T3E, IBM Blue Gene, etc. are built with it as the interconnection network topology. In this paper, we obtain the results of the g-extra H-structure connectivity and the g-extra H-substructure connectivity of the hypercubes when the specific structure is Pk and g = 1. [ABSTRACT FROM AUTHOR]

The conditional h-vertex (h-edge) connectivity of a connected graph H of minimum degree k > h is the size of a smallest vertex (edge) set F of H such that H − F is a disconnected graph of minimum degree at least h. Let G be the Cartesian product of r ≥ 1 cycles, each of length at least four and let h be an integer such that 0 ≤ h ≤ 2r − 2. In this paper, we determine the conditional h-vertex-connectivity and the conditional h-edge-connectivity of the graph G. We prove that both these connectivities are equal to (2r−h)arh, where arh is the number of vertices of a smallest h-regular subgraph of G.

“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 BPn when removing any edge subset with a size of approximately six times λ(BPn). 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(BPn)=λ(3)(BPn)+3=4n−3 for n⩾5; λ6(BPn)=λ(4)(BPn)+4=5n−4 and λ7(BPn)=λ(5)(BPn)+5=6n−5 for n⩾6.

Quantitative structure property research works, which are the essential part in chemical information and modelling, give basic underlying topological properties for chemical substances. This information enables conducting more feasible studies between theory and practice. Connectivity concept in chemical graph theory gives information about underlying topology of chemical structures, fault tolerance of molecules, and vulnerability of chemical networks. In this study we first defined two novel types of conditional connectivity measures based on regularity notion: k-regular edge connectivity and almost k-regular edge connectivity in chemical graph theory literature. We computed these new graph invariants for cycles, complete graphs, and Cartesian product of cycles. Our results will be applied to calculate k-regular edge connectivity of some nanotubes which are stated as Cartesian product of cycles. These calculations give information about fault tolerance capacity and vulnerability of these chemical structures.

Let G be a connected graph and g be a non-negative integer. A vertex set S of graph G is called a g-extra cut if G − S is disconnected and each component of G − S has at least g + 1 vertices. The g-extra connectivity of G is the minimum cardinality of a g-extra cut of G if G has at least one g-extra cut. For two graphs G 1 = (V 1 , E 1) and G 2 = (V 2 , E 2) , the strong product G 1 ⊠ G 2 is defined as follows: its vertex set is V 1 × V 2 and its edge set is { (x 1 , x 2) (y 1 , y 2) | x 1 = x 2 and y 1 y 2 ∈ E 2 ; or y 1 = y 2 and x 1 x 2 ∈ E 1 ; or x 1 x 2 ∈ E 1 and y 1 y 2 ∈ E 2 } , where (x 1 , x 2) , (y 1 , y 2) ∈ V 1 × V 2 . In this paper, we obtain the g-extra connectivity of the strong product of two paths, the strong product of a path and a cycle, and the strong product of two cycles. [ABSTRACT FROM AUTHOR]

The n -dimensional augmented cube A Q n , proposed by Choudum and Sunitha in 2002, is one of the most famous interconnection networks of the distributed parallel system. Reliability evaluation of underlying topological structures is vital for fault tolerance analysis of this system. As one of the most extensively studied parameters, the k -conditional edge-connectivity of a connected graph G , λ k (G) , is defined as the minimum number of the cardinality of the edge-cut of G , if exists, whose removal disconnects this graph and keeps each component of G − F having minimum degree at least k. Let n , t and δ be three integers, where δ = 1 , if t = 0 and δ = 0 , if t > 0. In this paper, we determine the exact value of the (2 t − 1) -conditional edge-connectivity of A Q n , λ 2 t − 1 (A Q n) = 2 t (2 n − 2 t) − δ for each positive integer 0 ≤ t ≤ n − 1 and n ≥ 1 , and give an affirmative answer to Shinde and Borse's corresponding conjecture on this topic in [On edge-fault tolerance in augmented cubes, J. Interconnection Netw. 20(4) (2020), DOI:10.1142/S0219265920500139 ]. [ABSTRACT FROM AUTHOR]

In large-scale multiprocessor systems, it is significant to estimate the reliability of the interconnection networks. The κ k and λ k are two generalized measurements of reliability for networks. The κ k (λ k) of G is the minimum cardinality of a set of vertices (edges) of G , if any, whose deletion disconnects G , and every remaining component has minimum degree at least k. For the modified bubble-sort networks M B n , this paper proves κ k (M B n) = λ k (M B n) = 2 k (n − k) for k ≤ n / 2. The conclusions extend some known results in the literature, imply that to make a modified bubble-sort network M B n disconnected with all remaining vertices have at least k neighbors, at least 2 k (n − k) vertices or edges have to be faulty. [ABSTRACT FROM AUTHOR]

Let G be a connected graph and g be a non-negative integer. A vertex set S of graph G is called a g-extra cut if G−S is disconnected and each component of G−S has at least g+1 vertices. The g-extra connectivity of G is the minimum cardinality of a g-extra cut of G if G has at least one g-extra cut. For two graphs G1=(V1,E1) and G2=(V2,E2), the strong product G1⊠G2 is defined as follows: its vertex set is V1×V2 and its edge set is {(x1,x2)(y1,y2)|x1=x2 and y1y2∈E2; or y1=y2 and x1x2∈E1; or x1x2∈E1 and y1y2∈E2}, where (x1,x2),(y1,y2)∈V1×V2. In this paper, we obtain the g-extra connectivity of the strong product of two paths, the strong product of a path and a cycle, and the strong product of two cycles.

Let G be a connected graph with minimum degree at least n and let h be an integer such that 0 ≤ h < n. The conditional h -edge (h -vertex) cut of G is defined as a set F of edges (vertices) of G whose removal disconnects G leaving behind components of minimum degree at least h. The characterization of a minimum h -vertex cut of the n -dimensional hypercube Q n is known. In this paper, we characterize a minimum h -edge cut of Q n. Also, we obtain a sharp lower bound on the number of vertices of an h -edge cut of Q n and obtain some consequences. [ABSTRACT FROM AUTHOR]

In this paper, we study the connectivity and diagonosability of n -dimensional hierarchical star network H S n based on the concept of forbidden faulty sets. In a forbidden faulty set, certain nodes cannot be faulty at the same time and this model can better reflect fault patterns in a real system than the existing ones. Under the condition every fault-free node in a network contains at least g fault-free neighbors, the g -good neighbor conditional connectivity is defined as the minimum number of faulty processors whose deletion makes the network disconnected, the g -good neighbor conditional diagnosability t g (G) is defined as the maximum number of faulty processors that the network can guarantee to identify solely by performing mutual tests among the processors. We investigate the g -good neighbor conditional connectivity and the g -good-neighbor conditional diagnosability of n -dimensional hierarchical star network H S n . Our results show that the g -good-neighbor conditional connectivity of H S n is (n − g) (g + 1) ! − 1 and the g -good-neighbor conditional diagnosability of H S n under the PMC and MM* models is (n − g + 1) (g + 1) ! − 1 when 0 ≤ g ≤ n − 3 , g ≠ 2 and n ≥ 4. In addition, we show the 2-good-neighbor conditional connectivity of H S n is 4 n − 8 and the 2-good-neighbor conditional diagnosability of H S n under the PMC and MM* models is 4 n − 5 when n ≥ 4. [ABSTRACT FROM AUTHOR]

The augmented cube AQn is one of the important variations of the hypercube Qn. In this paper, we prove that the conditional h-edge connectivity of AQn with n ≥ 3 is 8n − 16 for h = 3 and 2n for h = 2n − 3. We also obtain an upper bound on the conditional h-edge connectivity for odd integer h satisfying 5   ≤   h   ≤   2 n   -   5. [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]

We propose two new measures of conditional connectivity to be the extension of Rg-connectivity and Rg-edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) degG–F(p) + degG–F(q) ≥ 2g + k for every two distinct vertices p and q in G – F with d(p, q) ≤ d. The (g, d, k)-conditional(-edge)-connectivity, denoted by κg,d,k(λg,d,k), is the minimum cardinality of a conditional (g, d, k)(-edge)-cut. Based on these requirements, we obtain κ1,1,k, κ1,d,2, λ1,1,1 and λ1,d,2 for the hypercubes. [ABSTRACT FROM AUTHOR]

We propose two new measures of conditional connectivity to be the extension of Rg-connectivity and Rg-edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) degG–F(p) + degG–F(q) ≥ 2g + k for every two distinct vertices p and q in G – F with d(p, q) ≤ d. The (g, d, k)-conditional(-edge)-connectivity, denoted by κg,d,k(λg,d,k), is the minimum cardinality of a conditional (g, d, k)(-edge)-cut. Based on these requirements, we obtain κ1,1,k, κ1,d,2, λ1,1,1 and λ1,d,2 for the hypercubes. [ABSTRACT FROM AUTHOR]

Abstract The component connectivity is a kind of conditional connectivity. It is a generalization of the traditional connectivity, which is also a parameter for the reliability evaluation of interconnection networks. The g -component connectivity c κ g (G) of a non-complete connected graph G is the minimum number of vertices whose deletion results in a graph with at least g components. The results in Hsu et al. (2012) by Hsu et al. determine the component connectivity of the hypercube. As an invariant of the hypercube, in this paper, we first determine the minimum neighbourhood of g vertices in the folded hypercube for 1 ≤ g ≤ n + 2 , then we give the (g + 1) -component connectivity of the folded hypercube c κ g + 1 (F Q n) = g (n + 1) − 1 2 g (g + 1) + 1 for 1 ≤ g ≤ n − 1 and n ≥ 8. [ABSTRACT FROM AUTHOR]

Highlights • We study a refined measure for the fault-tolerance of a network, called h -super connectivity. • We determine h -super connectivity of the generalized star network. • We generalize some known results. Abstract This paper considers the conditional fault tolerance, h -super connectivity κ h and h -super edge-connectivity λ h of the hierarchical cubic network H C N n , an attractive alternative network to the hypercube, and shows κ h (H C N n) = λ h (H C N n) = 2 h (n + 1 − h) for any h with 0 ≤ h ≤ n − 1. The results imply that at least 2 h (n + 1 − h) vertices or edges have to be removed from H C N n to make it disconnected with no vertices of degree less than h , and generalize some known results. [ABSTRACT FROM AUTHOR]

Abstract For a graph G = (V , E) , a subset F ⊆ V (G) is called an Rk -vertex-cut of G if G − F is disconnected and each vertex u ∈ V (G) − F has at least k neighbours in G − F. The Rk -vertex-connectivity of G , denoted by κk (G), is the cardinality of a minimum Rk -vertex-cut of G. In this paper, we further study the Rk -vertex-connectivity by introducing the concept, called super Rk -vertex-connectedness. The graph G is called super Rk -vertex-connectedness if, for every minimum Rk -vertex-cut S , G − S contains a component which is isomorphic to a certain graph H , where H is related to the graph G and integer k. For the Cayley graphs generated by wheel graphs, H is isomorphic to K 2 when k = 1 and H is isomorphic to C 4 when k = 2. In this paper, we show that the Cayley graphs generated by wheel graphs are super R 1-vertex-connectedness and super R 2-vertex-connectedness. Our studies generalize the main result in [8]. [ABSTRACT FROM AUTHOR]

In this paper, first we estimate the star conditional connectivity of Hypercube, where the star conditional connectivity is the minimum number of stars in a graph, such that the deletion of those stars disconnects the graph and the left graph has property P. Second, a graph is called strongly Menger connected if for any two vertices u , v in the graph, there are m i n (d (u) , d (v)) internally disjoint paths between them, where d (u) , d (v) are the degree of u , v in the graph. In this paper, we propose k -star-fault-tolerance strong Menger connectivity. A graph is called k -star-fault-tolerance strong Menger connected if after the removal of no more that k stars, the left graph remains strongly Menger connected. We show that Hypercube Q n is ⌊ n − 2 2 ⌋ -star-fault-tolerance strongly Menger connected. Moreover, the bound is sharp. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a connected graph and P be graph-theoretic property. A network is often modeled by a graph G = ( V , E ) . One fundamental consideration in the design of networks is reliability. The connectivity is an important parameter to measure the fault tolerance and reliability of network. The conditional connectivity λ ( G, P ) or κ ( G, P ) is the minimum cardinality of a set of edges or vertices, if it exists, whose deletion disconnects G and each remaining component has property P . Let F be a vertex set or edge set of G and P be the property of with at least k components. Then we have the k -component connectivity cκ k ( G ) and the k -component edge connectivity cλ k ( G ). In this paper, we determine the k -component (edge) connectivity of locally twisted cubes LTQ n for small k , and we also prove other properties of LTQ n . [ABSTRACT FROM AUTHOR]

Abstract: Many ocean species exist within what are called marine metapopulations: networks of otherwise isolated local populations connected by the exchange of larval offspring. In order to manage these species as effectively as possible (e.g., by designing and implementing effective networks of marine protected areas), we must know how many offspring are produced within each local population (i.e., local demography), and where those offspring disperse (i.e., larval connectivity). Although there is much interest in estimating connectivity in the relatively simple sense of identifying the locations of spawning parents and their settling offspring, true measures of demographic connectivity that account for among‐site variation in offspring production have been lacking. We combined detailed studies of local reproductive output and larval dispersal of a coral reef fish to quantify demographic connectivity within a regional metapopulation that included four widely spaced islands in the Bahamas. We present a new method for estimating demographic connectivity when the levels of dispersal among populations are inferred by the collection of genetically “tagged” offspring. We estimated that 13.3% of recruits returned to natal islands, on average (95% CI = 1.1–50.3%), that local retention was high on one of the islands (41%, 95% CI = 6.0–97.0%), and that larval connectivity was appreciable, even between islands 129 km apart (mean = 1.6%, 95% CI = 0.20–8.8%). Our results emphasize the importance of properly integrating measurements of production with measurements of connectivity. Had we not accounted for among‐site variation in offspring production, our estimates of connectivity would have been inaccurate by a factor as much as 6.5. At a generational timescale, lifetime offspring production varied substantially (a fivefold difference among islands) and the importance of each island to long‐term metapopulation growth was dictated by both larval production and connectivity. At the scale of our study (local populations inhabiting 5‐ha reefs), the regional metapopulation could not grow without external input. However, an exploratory analysis simulating a network of four marine protected areas suggested that reserves of >65 ha each would ensure persistence of this network. Thus, integrating studies of larval connectivity and local demography hold promise for both managing and conserving marine metapopulations effectively. [ABSTRACT FROM AUTHOR]

For a connected graph G = (V (G), E(G)), a subset F ⊂ V (G) is called an Rk-vertex-cut if G- F is disconnected and each vertex u ∊ V (G) - F has at least k neighbors in G - F. The cardinality of a minimum Rk-vertex-cut of G is the Rk-vertex-connectivity and is denoted by kk (G). The conditional connectivity is a new measure to study the fault tolerance of network structures beyond connectivity. In this paper, we study R1-vertex-connectivity and R2-vertex-connectivity of Cayley graphs generated by 2-trees T2,n which are denoted by KTn and show that K1(KTn) 4n-8 k1( ) = - for n ⩾ 4; K 2 (KTn) = 8n -22 for n ⩾ 6. [ABSTRACT FROM AUTHOR]

For a connected graph G = ( V , E ) , a subset F ⊆ V is called an R k -vertex-cut of G if G − F is disconnected and each vertex in V − F has at least k neighbors in G − F . The cardinality of the minimum R k -vertex-cut is the R k -vertex-connectivity of G and is denoted by κ k ( G ). The conditional connectivity is a measure to explore the structure of networks beyond the vertex-connectivity. Let Sym ( n ) be the symmetric group on { 1 , 2 , … , n } and T be a set of transpositions of Sym ( n ). Denote by G ( T ) the graph with vertex set { 1 , 2 , … , n } and edge set { i j : ( i j ) ∈ T } . If G ( T ) is a wheel graph, then simply denote the Cayley graph C a y ( S y m ( n ) , T ) by WG n . In this paper, we determine the values of κ 1 and κ 2 for Cayley graphs generated by wheel graphs and prove that κ 1 ( W G n ) = 4 n − 6 and κ 2 ( W G n ) = 8 n − 18 . [ABSTRACT FROM AUTHOR]

Multiprocessor systems commonly take interconnection network (simply graph) as the underlying topological structure. The performance of multiprocessor systems is greatly influenced by their network topologies. The connectivity is a classical metric to evaluate the fault tolerance of multiprocessor systems. In this work, we propose a composite graph based on disc-ring and folded hypercube, D F Q (m , d , n) (simply, D F Q n). Compared with the compound graph DQcube (D Q n), D F Q n shows better performance in terms of many metrics such as diameter, connectivity and layout cost. In detail, we first show that the connectivity, edge-connectivity and tightly super connectivity are n + 2 uniformly. Furthermore, we show that h -extra connectivity of D F Q n is κ h (D F Q n) = (h + 1) (n + 2) − 2 h − ( h 2 ). [ABSTRACT FROM AUTHOR]

The r -component connectivity c κ r ( G ) of a non-complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. In this paper, we determine the component connectivity of the hypercube c κ r + 1 ( Q n ) = − r 2 2 + ( 2 n − 5 2 ) r − n 2 + 2 n + 1 for n + 1 ≤ r ≤ 2 n − 5 , n ≥ 6 . This paper extends the results in Hsu et al. (2012) [3] . [ABSTRACT FROM AUTHOR]

The diagnosability of a parallel system is defined as the maximum number of faulty processors or nodes that the system can guarantee to identify. In this study, we investigate the g -good-neighbor conditional diagnosability, which indicates that every fault-free node in a system contains at least g fault-free neighbors. Compared with the conventional diagnosability, g -good-neighbor conditional diagnosability improves accuracy in measuring the reliability of interconnection networks in heterogeneous environments. We apply the PMC and MM* models to study the g -good-neighbor conditional diagnosability of 3-ary n -cube networks, which represent a family of popular parallel systems such as IBM's Blue Gene and Cray T3D. The findings made in this study facilitate accurate reliability measurements in modern parallel systems powered by 3-ary n -cube networks. Specifically, our results show that the g -good-neighbor conditional diagnosability of 3-ary n -cube is g 2 ( 2 n − g + 1 ) − 1 and g − 1 2 ( 4 n − 2 g + 1 ) − 1 when the g value is even and odd, respectively. [ABSTRACT FROM AUTHOR]

Fault tolerance is especially important for interconnection networks, since the growing size of networks increases their vulnerability to component failures. A classical measure for the fault tolerance of a network in the case of vertex failures is its connectivity. Given a network based on a graph G and a positive integer h , the R h -connectivity of G is the minimum cardinality of a set of vertices in G , if any, whose deletion disconnects G , and the minimum degree of every connected component is at least h . This paper investigates the R h -connectivity ( h = 1 , 2 ) of the hierarchical cubic network HCN n ( n ≥ 2 ), and shows that κ 1 ( HCN n ) = 2 n , κ 2 ( HCN n ) = 4 n − 4 , respectively. Furthermore, the paper establishes the conditional diagnosability of HCN n under the PMC diagnostic model. [ABSTRACT FROM AUTHOR]

Fault tolerance is especially important for interconnection networks, vastly influencing the performance of the parallel processing systems underlying the corresponding networks. This paper studies the fault tolerance of radix- k n-dimensional hypermesh optical interconnection networks, determines the connectivity of partial hypermesh, and derives the conditional connectivity of hypermesh provided that each adjacent set cannot be faulty simultaneously. Under this condition, the hypermesh networks can tolerate up to 2 n( k-1)- k-1 fault processors without being disrupted, implying that when the number of dimension n (respectively, radix- k) is a fixed value in the hypermesh network, the larger the value of radix- k (respectively, dimension n) is, the higher the reliability and availability of the network becomes. [ABSTRACT FROM AUTHOR]

Fault tolerance is especially important for interconnection networks, since the growing size of the networks increases its vulnerability to component failures. A classic measure for the fault tolerance of a network in the case of vertex failures is its connectivity. Given a network based on a graphGand a positive integerh, the-connectivity ofGis the minimum cardinality of a set of vertices inG, if any, whose deletion disconnectsG, and the minimum degree of every connected component is at leasth. This study investigates the-connectivity of the dual-cubes forh = 1 andh = 2, respectively. Furthermore, the study establishes the conditional diagnosability ofunder the Preparata Metze Chien (PMC) model. [ABSTRACT FROM PUBLISHER]

Abstract: This work deals with a generalization of the Cartesian product of graphs, the product graph introduced by Bermond et al. [J.C. Bermond, C. Delorme, G. Farhi, Large graphs with given degree and diameter II, J. Combin. Theory, Series B 36 (1984), 32–48]. The connectivity of these product graphs is approached by studying the -restricted edge-connectivity, which is defined as the minimum number of edges of a graph whose deletion yields a disconnected graph with all its components having at least vertices. To be more precise, we present lower and upper bounds for the -restricted edge-connectivity of , and provide sufficient conditions that ensure an optimal value for this parameter. When both and are regular graphs, conditions for guaranteeing that is super- are also presented, and the particular case where both and are complete graphs is considered. [Copyright &y& Elsevier]

Abstract: A vertex subset is an -cut of a connected graph if is disconnected and every vertex in has at least fault-free neighbors in . The cardinality of the minimum -cut of is the -connectivity of , denoted by . This parameter measures a kind of conditional fault tolerance of networks. In this work, we characterize the smallest components after deleting a minimum -cut of hypercubes. Our work strengthens the results of [A.H. Esfahanian, Generalized measure of fault tolerance with application to -cube networks, IEEE Trans. Comput. 38 (1989) 1586–1591] and [S. Latifi, M. Hegde, M. Naraghi-Pour, Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput. 43 (1994) 218–222] and also corrects bugs in them. [Copyright &y& Elsevier]

Abstract: In this paper, we study fault-tolerant routing in bijective connection networks with restricted faulty edges. First, we prove that the probability that all the incident edges of an arbitrary node become faulty in an -dimensional bijective connection network, denoted by , is extremely low when becomes sufficient large. Then, we give an algorithm to find a fault-free path of length at most between any two different nodes in if each node of has at least one fault-free incident edge and the number of faulty edges is not more than . In fact, we also for the first time provide an upper bound of the fault diameter of all the bijective connection networks with the restricted faulty edges. Since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., all the results are appropriate for these cubes. [Copyright &y& Elsevier]

Abstract: The conditional connectivity and the conditional fault diameter of a crossed cube are studied in this work. The conditional connectivity is the connectivity of an interconnection network with conditional faults, where each node has at least one fault-free neighbor. Based on this requirement, the conditional connectivity of a crossed cube is shown to be . Extending this result, the conditional fault diameter of a crossed cube is also shown to be as a set of node failures. This indicates that the conditional fault diameter of a crossed cube is increased by three compared to the fault-free diameter of a crossed cube. The conditional fault diameter of a crossed cube is approximately half that of the hypercube. In this respect, the crossed cube is superior to the hypercube. [Copyright &y& Elsevier]

Abstract: Let D be a graph or a digraph. If is the minimum degree, the edge-connectivity and the vertex-connectivity, then is a well-known basic relationship between these parameters. The graph or digraph D is called maximally edge-connected if and maximally vertex-connected if . In this survey we mainly present sufficient conditions for graphs and digraphs to be maximally edge-connected as well as maximally vertex-connected. We also discuss the concept of conditional or restricted edge-connectivity and vertex-connectivity, respectively. [Copyright &y& Elsevier]

Abstract: A matched sum graph G of two graphs and of the same order is obtained from the union of and and from joining each vertex of with one vertex of according to one bijection between the vertices in and . When then f is just a permutation of and the corresponding matched sum graph is a permutation graph . In this paper, we derive lower bounds for the connectivity, edge-connectivity, and different conditional connectivities in matched sum graphs, and present sufficient conditions which guarantee maximum values for these conditional connectivities. [Copyright &y& Elsevier]

Let k and h be two integers, 0≤ h< k. Let G be a connected graph with minimum degree at least k. The conditional h-edge-connectivity of G, denoted by λ( h )( G), is defined as the minimum cardinality ⋎ S⋎ of a set S of edges in G such that G-S is disconnected and is of minimum degree at least h. This type of edge-connectivity is a generalization of the traditional edge-connectivity and can more accurately measure the fault-tolerance of networks. In this paper, we will first show that λ2( G)≤ g( k-2) for a k(≥3)-regular graph G provided G is neither K 4 and K 5 nor K 3,3 , where g is the length of a shortest cycle of G, then show that λ( h )( Q k )=( k-h) 2 h for a k-dimensional cube Q k . [ABSTRACT FROM AUTHOR]

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an R 2-edge-cut if G-S is disconnected and contains neither an isolated vertex nor a one-degree vertex. The R 2-edge-connectivity of G, denoted by λ n( G), is the minimum cardinality over all R 2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ n( G)= g(2 k−2) for any 2 k-regular connected graph G(≠ K 5) that is either edge-transitive or vertex-transitive and g≥5 is given. [ABSTRACT FROM AUTHOR]

The hypercubes are a famous class of networks for multiprocessor systems and the unidirectional hypercubes are hypercube interconnection topologies with simplex unidirectional links. Under the classic PMC model, each processor in a multiprocessor system tests a subset of its neighbors. The collection of tests in this system can be modeled by a directed graph. The diagnosability of a system is the maximum number of faulty processors that the system may identify according to the outcomes of the tests, and the g -good-neighbor diagnosability is a more accurate indicator than the diagnosability. In this paper, we first determine the 1-good-neighbor connectivity of unidirectional hypercubes and then determine the diagnosability and 1-good-neighbor diagnosability of hypercube networks when unidirectional hypercubes are used as the collection of tests under the PMC model. [ABSTRACT FROM AUTHOR]