Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4633733 | Applied Mathematics and Computation | 2009 | 7 Pages |
Abstract
For a connected graph G, the super edge-connectivity λâ²(G) is the minimum cardinality of an edge-cut F in G such that G-F contains no isolated vertices. It is a more refined index than the edge-connectivity for the fault-tolerance of the network modeled by G. This paper deals with the super edge-connectivity of product graphs G1âG2, which is one important model in the design of large reliable networks. Let Gi be a connected graph with order νi and edge-connectivity λi for i=1,2. We show that λâ²(G1âG2)⩾min{ν1λ2,ν2λ1,λ1+2λ2,2λ1+λ2} for ν1,ν2⩾2 and deduce the super edge-connectedness of G1âG2 when G1 and G2 are maximally edge-connected with δ(G1)⩾2,δ(G2)⩾2. Furthermore we state sufficient conditions for G1âG2 to be λâ²-optimal, that is, λâ²(G1âG2)=ξ(G1âG2). As a consequence, we obtain the λâ²-optimality of some important interconnection networks.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Min Lü, Guo-Liang Chen, Xi-Rong Xu,