Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.amc.2008.10.035 | Applied Mathematics and Computation |
Keywords | Field | DocType |
Super edge-connectivity,Super edge-connected,λ′-graph,λ′-optimal,Product graph | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Cardinality,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
207 | 2 | 0096-3003 |
Citations | PageRank | References |
4 | 0.41 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Lü | 1 | 4 | 0.41 |
| Guoliang Chen | 2 | 305 | 46.48 |
| Xirong Xu | 3 | 44 | 13.81 |