location: Current position: Home >> Scientific Research >> Paper Publications
149

On super edge-connectivity of product graphs

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.

Pre One:朴素贝叶斯的二次建模及在卷烟GC-TOFMS指纹分类上的应用

Next One:The Graphs C(13)(t) are Graceful for t equivalent to 0, 3 (mod 4)