摘要 :
Given a connected graph G and S⊆V(G) with |S|≥2, an S-tree is a such subgraph T=(V′,E′) of G that is a tree with S⊆V′. Two S-trees T and T′ are edge-disjoint if E(T)∩E(T′)=∅. Let λG(S) be the maximum size of a set of ed...
展开
Given a connected graph G and S⊆V(G) with |S|≥2, an S-tree is a such subgraph T=(V′,E′) of G that is a tree with S⊆V′. Two S-trees T and T′ are edge-disjoint if E(T)∩E(T′)=∅. Let λG(S) be the maximum size of a set of edge-disjoint S-trees in G. The λk-connectivity of G is defined as λk(G)=min{λG(S):S⊆V(G),|S|=k}. In this paper, we first show some structural properties of edge-disjoint S-trees by Fan Lemma and König-ore Formula. Then, the λ4-connectivity of the Cartesian product of trees is determined. That is, let Tn1,Tn2,…,Tnk be trees, then λ4(Tn1□Tn1⋯□Tnk)=k if |V(Tni)|≥4 for each i∈{1,2,…,k}, otherwise λ4(Tn1□Tn2□⋯□Tnk)=k−1. As corollaries, λ4-connectivity for some graph classes such as hypercubes and meshes can be obtained directly.
收起
摘要 :
The distance Laplacian matrix of a connected graph G is defined as L(G) = Tr(G)-D(G), where Tr(G) is the diagonal matrix of the vertex transmissions in G and D(G) is the distance matrix of G. The largest eigenvalue of L(G) is call...
展开
The distance Laplacian matrix of a connected graph G is defined as L(G) = Tr(G)-D(G), where Tr(G) is the diagonal matrix of the vertex transmissions in G and D(G) is the distance matrix of G. The largest eigenvalue of L(G) is called the distance Laplacian spectral radius ofG. In this paper,wedetermine the graphs with themaximum distance Laplacian spectral radius and the minimum distance Laplacian spectral radius among all the bicyclic graphs with given order, respectively.
收起
摘要 :
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...
展开
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.
收起
摘要 :
The balanced hypercube BH_n, proposed by Wu and Huang, is a new variation of hyper-cube. A Hamiltonian bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path between two arbitrary vertices from different partit...
展开
The balanced hypercube BH_n, proposed by Wu and Huang, is a new variation of hyper-cube. A Hamiltonian bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path between two arbitrary vertices from different partite sets. A Hamiltonian laceable graph G is strongly Hamiltonian laceable if there is a path of length |V(G)| - 2 between any two distinct vertices of the same partite set. A graph G is called k-edge-fault strong Hamiltonian laceable, if G - F is strong Hamiltonian laceable for any edge-fault set F with |F| ≤ k. It has been proved that the balanced hypercube BH_n is strong Hamiltonian laceable. In this paper, we improve the above result and prove that BH_n is (n - 1)-edge-fault strong Hamiltonian laceable.
收起
摘要 :
The hierarchical star networks HS_n, proposed by Shi and Srimani, is a new level network topology and uses the star graphs as building blocks. Given a graph 6, the h-extra connectivity of 6 is the minimum cardinality of a set of v...
展开
The hierarchical star networks HS_n, proposed by Shi and Srimani, is a new level network topology and uses the star graphs as building blocks. Given a graph 6, the h-extra connectivity of 6 is the minimum cardinality of a set of vertices in G, if exists, whose deletion disconnects G and leaves every remaining component with more than h vertices. There is no known polynomial-time algorithm for finding κ_h,(G) for a given graph G. In this paper, by exploring the combinatorial properties and fault-tolerance of HS_n, we show that the largest component of a survival graph contains almost all of the remaining vertices after removing at most 4n-8 vertices and obtain the h-extra connectivity for 1 ≤ h ≤ 3 of HS_n, where n ≥ 5. As applications, the conditional diagnosability and the h-extra conditional diagnosability for 1 ≤ h ≤ 3 of HS_n under the PMC model and the MM* model, respectively, are obtained.
收起
摘要 :
Let F_v (resp. F_e) be the set of faulty vertices (resp. faulty edges) in the n-dimensional balanced hypercube BH_n. The edge-bipancyclicity of BH_n - F_v for |F_v| ≤ n - 1 had been proved in [Inform. Sci. 288 (2014) 449-461]. Th...
展开
Let F_v (resp. F_e) be the set of faulty vertices (resp. faulty edges) in the n-dimensional balanced hypercube BH_n. The edge-bipancyclicity of BH_n - F_v for |F_v| ≤ n - 1 had been proved in [Inform. Sci. 288 (2014) 449-461]. The existence of edge-Hamiltonian cycles in BH_n - F_e for |F_e| ≤ 2n - 2 were obtained in [Appl. Math. Comput. 244 (2014) 447-456]. In this paper, we consider fault-tolerant cycle embedding of BH_n with both faulty vertices and faulty edges, and prove that there exists a fault-free cycle of length 2~(2n) - 2|F_v| in BH_n with |F_v| + |F_e| ≤ 2n - 3 and |F_v| ≤ n - 1 for n ≥ 2.
收起
摘要 :
The balanced hypercube BH_n proposed by Wu and Huang is a variation of the hypercube. It has been proved that the balanced hypercube is a node-transitive and bipartite graph. Assume that the nodes are divided into two bipartite no...
展开
The balanced hypercube BH_n proposed by Wu and Huang is a variation of the hypercube. It has been proved that the balanced hypercube is a node-transitive and bipartite graph. Assume that the nodes are divided into two bipartite node sets X and Y; u and x are two different nodes in X, and v and y are two different nodes in Y. In this paper, we prove that there exist two node-disjoint paths P(x, y) and R(u, v) in BH_n, and V(P[x, y]) [V(R[u, v]) = V(BH_n), where n P 1. The Hamiltonian laceability of BH_n which was proved by Xu et al. is also obtained from the corollary of our result.
收起
摘要 :
Thek-dimensional data center network withnport switches, denoted byDk,n, has been proposed for data centers as a server centric network structure. Wang et?al. (2015) had shown thatDk,nis(n+k?3)-fault-tolerant Hamiltonian. In this ...
展开
Thek-dimensional data center network withnport switches, denoted byDk,n, has been proposed for data centers as a server centric network structure. Wang et?al. (2015) had shown thatDk,nis(n+k?3)-fault-tolerant Hamiltonian. In this paper, we consider more faulty edges and prove thatDk,nis conditional(2n+2k?9)-edge-fault-tolerant Hamiltonian for anyk≥0andn≥2exceptk=1andn≥6. Moreover, the upper bound2n+2k?9of|F|is optimal.
收起
摘要 :
Thek-dimensional data center network withnport switches, denoted byDk,n, has been proposed for data centers as a server centric network structure. Wang et?al. (2015) had shown thatDk,nis(n+k?3)-fault-tolerant Hamiltonian. In this ...
展开
Thek-dimensional data center network withnport switches, denoted byDk,n, has been proposed for data centers as a server centric network structure. Wang et?al. (2015) had shown thatDk,nis(n+k?3)-fault-tolerant Hamiltonian. In this paper, we consider more faulty edges and prove thatDk,nis conditional(2n+2k?9)-edge-fault-tolerant Hamiltonian for anyk≥0andn≥2exceptk=1andn≥6. Moreover, the upper bound2n+2k?9of|F|is optimal.
收起
摘要 :
A system is t/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free processor mistaken as a faulty one. The pes...
展开
A system is t/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free processor mistaken as a faulty one. The pessimistic diagnosability of a system G, denoted by f_p(G), is the maximal number of faulty processors so that the system G is t/t-diagnosable. The known results about t_p(G) for alternating group graphs [Inform. Process. Lett. (2015), pp. 151-154]; BC networks [IEEE Trans. Comput. (2005), pp. 176-184]; the k-ary n-cube networks [IEEE Trans. Comput. (1991), pp. 232-237], [Int. J. Comput. Math. (2012), pp. 1-10] etc. have property that cn(G) < 2. In this paper, we study the pessimistic diagnosability of two kinds of graphs with cn(G) ≥ 3, those are: bubble-sort star graphs BS_n and augmented k-ary n-cubes AQ_(n,k), and prove that f_p(BS_n) = 4n - 9forn ≥ 4, t_P(AQ_n,3) = 8n - 11 forn ≥ 4,and t_p(AQ_(n,k)) = 8n - 10forn ≥ 3and k ≥ 4.
收起
原文获取