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]

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]

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]

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

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]

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]