Hits:
Indexed by:期刊论文
Date of Publication:2009-01-15
Journal:APPLIED MATHEMATICS AND COMPUTATION
Included Journals:SCIE、EI、Scopus
Volume:207
Issue:2
Page Number:900-306
ISSN No.:0096-3003
Key Words:Super edge-connectivity; Super edge-connected; lambda '-graph; lambda '-optimal; Product graph
Abstract:For a connected graph G, the super edge-connectivity lambda'(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 G(1)*G(2), which is one important model in the design of large reliable networks. Let G(i) be a connected graph with order nu(i) and edge-connectivity lambda(i) for i = 1, 2. We show that lambda '(G(1)G(2)) >= min{nu(1)lambda(2), nu(2)lambda(1),lambda(1) + 2 lambda(2),2 lambda(1) + lambda(2)} for nu(1), nu(2) >= 2 and deduce the super edge-connectedness of G(1)*G(2) when G(1) and G(2) are maximally edge-connected with delta(G(1)) >= 2, delta(G(2)) >= 2. Furthermore we state sufficient conditions for G(1)*G(2) to be lambda'-optimal, that is, lambda'(G(1)*G(2)) = xi(G(1)*G(2)). As a consequence, we obtain the lambda'-optimality of some important interconnection networks. Crown Copyright (C) 2008 Published by Elsevier Inc. All rights reserved.