摘要 :
Let G = (V, E) be a k-regular graph with connectivity K and edge connectivity. G is maximum connected if kappa = k, and G is maximum edge connected if lambda = k. Moreover, G is super-connected if it is a complete graph, or it is ...
展开
Let G = (V, E) be a k-regular graph with connectivity K and edge connectivity. G is maximum connected if kappa = k, and G is maximum edge connected if lambda = k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x\(v,x) is an element of E} for some vertex v is an element of V; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)\(v,x) is an element of E} for some vertex v is an element of V. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, mobius cubes, split-stars, and recursive circulant graphs. (C) 2002 Elsevier Science Inc. All rights reserved. [References: 9]
收起
摘要 :
The super connectivity κ′ and the super edge-connectivity λ′ are more refined network reliability indices than connectivity κ and edge-connectivity λ′. This paper shows that for a connected graph G with order at least four ...
展开
The super connectivity κ′ and the super edge-connectivity λ′ are more refined network reliability indices than connectivity κ and edge-connectivity λ′. This paper shows that for a connected graph G with order at least four rather than a star and its line graph L(G), κ′(L(G)) = λ′(G) if and only if G is not super-λ′. As a consequence, we obtain the result of Hellwig et al. [Note on the connectivity of line graphs, Inform. Process. Lett. 91 (2004) 7] that κ(L(G)) = λ′(G). Furthermore, the authors show that the line graph of a super-λ′ graph is super-A if the minimum degree is at least three.
收起
摘要 :
For a graph G=(V(G), E(G)), the transformation graphs G~(+-+) is the graph with vertex set V (G)∪ E(G) in which the vertices a and β are joined by an edge if and only if α and β are adjacent or incident in G while {α, β} E(G...
展开
For a graph G=(V(G), E(G)), the transformation graphs G~(+-+) is the graph with vertex set V (G)∪ E(G) in which the vertices a and β are joined by an edge if and only if α and β are adjacent or incident in G while {α, β} E(G) , or α and β are not adjacent in G while { α, β} ∈ E(G). In this note, we show that all but for a few exceptions, G~(+-+) is super connected and super edge-connected.
收起
摘要 :
A graph G is super-connected, super-k, for short if every minimum vertex-cut isolates a vertex of G. Call G super restricted edge-connected, in short, super-λ', if every minimum restricted edge-cut isolates an edge. We view the t...
展开
A graph G is super-connected, super-k, for short if every minimum vertex-cut isolates a vertex of G. Call G super restricted edge-connected, in short, super-λ', if every minimum restricted edge-cut isolates an edge. We view the total graph T(G) of G as the disjoint of G and the line graph L(G), together with the lines of the subdivision graph S(G); for each line l = (u, v) in G there are two lines in S(G), namely (l,u) and (l,v). In this paper, we prove that T(G) is super-k if G is a super-k graph with δ(G) ≥ 4. We also show that T(G) is super-λ' if G is a k-regular graph with k(G) ≥ 3. Furthermore, we give examples which illustrate that the results are best possible.
收起
摘要 :
Let D be a strongly connected digraph with order at least two, M(D) denote the middle digraph of D, κ(D) and λ(D) denote the connectivity and arc-connectivity of D, respectively. In this paper we study super-arc-connected and su...
展开
Let D be a strongly connected digraph with order at least two, M(D) denote the middle digraph of D, κ(D) and λ(D) denote the connectivity and arc-connectivity of D, respectively. In this paper we study super-arc-connected and super-connected middle digraphs and the spectral of middle digraphs.
收起
摘要 :
Let D be a strongly connected digraph with order at least two, T(D) denote the total digraph of D, n{D) and \(D) denote the connectivity and arc-connectivity of D, respectively. In this paper we study supei-arc-connected and super...
展开
Let D be a strongly connected digraph with order at least two, T(D) denote the total digraph of D, n{D) and \(D) denote the connectivity and arc-connectivity of D, respectively. In this paper we study supei-arc-connected and super-connected total digraphs. Following results are obtained:1,T(D) is super-arc-connected if and only if D % K2,If K(D) + X(D) > S(D) + 1, then T(D) is super-connected,.
收起
摘要 :
The super-connectivity (super-edge-connectivity) of a connected graph G is the minimum number of vertices (edges) that need to be deleted from Gin order to disconnect G without creating isolated vertices. We determine when the gen...
展开
The super-connectivity (super-edge-connectivity) of a connected graph G is the minimum number of vertices (edges) that need to be deleted from Gin order to disconnect G without creating isolated vertices. We determine when the generalized Petersen graphs GP[n, k] are super-connected and super edge-connected, and show that their super-connectivity and their super-edge-connectivity are both equal to four when n is not an element of{2k, 3k}. These results partially answer a question by Harary (1983) and are of interest especially in the study of reliability and fault tolerance of interconnection networks, since the graphs in this class are good candidates for such networks. (C) 2017 Elsevier B.V. All rights reserved.
收起
摘要 :
We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained. (ⅰ) If δ~+(D_i) = δ~-(D_i) = δ(D_i) = k(D_i) for i = l,2, then D_1 × D_2 is...
展开
We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained. (ⅰ) If δ~+(D_i) = δ~-(D_i) = δ(D_i) = k(D_i) for i = l,2, then D_1 × D_2 is super-k if and only if D_1 × D_2(≌) D × K_n (D × K_n (≌)K_2 × K_2, K_2 × K_3), (ⅱ) If δ+(D_i) = δ~-(D_i) = δ(D_i) = λ.(D_i) for i = 1.2. then D_1 ×D_2 is super-λ if and only if D_1 × D_2(≌) D × k_n. where λ(D) = δ(D) = 1, K_n denotes the complete digraph of order n and n ≥ 2.
收起
摘要 :
The augmented cube AQ_n, proposed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], is a (2n - 1)-regular (2n - 1)-connected graph (n ≠ 3). This paper determines that the super conn...
展开
The augmented cube AQ_n, proposed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], is a (2n - 1)-regular (2n - 1)-connected graph (n ≠ 3). This paper determines that the super connectivity of AQ_n is An - 8
收起
摘要 :
Classical edge-connectivity is a vital metric to characterize fault tolerance and reliability of network-based multiprocessor system. As two generalizations of classical edgeconnectivity, super edge-connectivity and average degree...
展开
Classical edge-connectivity is a vital metric to characterize fault tolerance and reliability of network-based multiprocessor system. As two generalizations of classical edgeconnectivity, super edge-connectivity and average degree edge-connectivity are two important parameters to assess the fault tolerability of a multiprocessor system by imposing some constraints on the degree of survival graph. In this work, we focus on k-super edge connectivity lambda(k)(Q(3) (n)) and a-average degree edge connectivity lambda(a)(Q(3) (n)) of the 3-ary n-cube. We first show that lambda(2a)(Q(3) (n)) = 2(n - a)3(a) for 0 = 1 and lambda(2a+1)(Q(3) (n)) = 2(2n - 2a - 1)3(a) for 0 = 2. Moreover, we determine that.lambda(2a)(Q(3) (n)) =lambda(2a)(Q(3) (n)), and lambda(2a+1)(Q(3) (n)) =lambda(2a+1)(Q(3) (n)), which indicates that these two kinds of metrics possess the same robustness in a 3-ary n-cube.
收起
原文获取