ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Edge fault-tolerance of super restricted edge-connected Cartesian product graphs

  • School of Mathematical Sciences, University of Science and Technology of China；Wu Wentsun Key Laboratory of Mathematics, USTC, Chinese Academy of Sciences, Hefei 230026, China

Funds:  Supported by NSFC (61272008).
Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2014.12.001
More Information
  • Author Bio:

    HONG Zhenmu, male, born in 1987, PhD candidate. Research field: combinatorics and graph theory.

  • Corresponding author: XU Junming
  • Received Date: 12 December 2013
  • Accepted Date: 19 March 2014
  • Rev Recd Date: 19 March 2014
  • Publish Date: 30 December 2014
    Abstract

  • Abstract

    A subset F of edges in a connected graph G is a restricted edge-cut if G-F is disconnected and every component has at least two vertices. A graph G is super restricted edge-connected (super-λ′ for short) if every minimum restricted edge-cut of G isolates at least one edge. The edge fault-tolerance ρ′(G) of a super-λ′ graph G is the maximum integer m for which G-F is still super-λ′ for any subset FE(G) with |F|≤m. It was shown that

    Abstract

    A subset F of edges in a connected graph G is a restricted edge-cut if G-F is disconnected and every component has at least two vertices. A graph G is super restricted edge-connected (super-λ′ for short) if every minimum restricted edge-cut of G isolates at least one edge. The edge fault-tolerance ρ′(G) of a super-λ′ graph G is the maximum integer m for which G-F is still super-λ′ for any subset FE(G) with |F|≤m. It was shown that
    • FullText(HTML)
  • loading
    • References(12)
  • [1]
    Xu J M. Theory and Application of Graphs[M]. Dordrecht/Boston/London: Kluwer Academic Publishers, 2003.
    [2]
    Fbrega J, Fiol M A. Extraconnectivity of graphs with large girth[J]. Discrete Mathematics, 1994, 127: 163-170.
    [3]
    Fbrega J, Fiol M A. On the extraconnectivity of graphs[J]. Discrete Mathematics, 1996, 155: 49-57.
    [4]
    Esfahanian A H, Hakimi S L. On computing a conditional edge-connectivity of a graph[J]. Information Processing Letters, 1988, 27: 195-199.
    [5]
    Bonsma P, Ueffing N, Volkmann L. Edge-cuts leaving components of order at least three[J]. Discrete Mathematics, 2002, 256(1-2): 431-439.
    [6]
    Zhang Z, Yuan J. A proof of an inequality concerning k-restricted edge-connectivity[J]. Discrete Mathematics, 2005, 304: 128-134.
    [7]
    Hong Y M, Meng J X, Zhang Z. Edge fault tolerance of graphs with respect to super edge-connectivity[J]. Discrete Applied Mathematics, 2012, 160: 579-587.
    [8]
    Wang D, Lu M. Edge fault tolerance of super edge connectivity for three families of interconnection networks[J]. Information Sciences, 2012, 188: 260-268.
    [9]
    Xu J M. Topological Structure and Analysis of Interconnection Networks[M]. Dordrecht/Boston/London: Kluwer Academic Publishers, 2001.
    [10]
    Chiue W S, Shieh B S. On connectivity of the Cartesian product of two graphs[J]. Applied Mathematics and Computation, 1999, 102: 129-137.
    [11]
    Balbuena C, Gonzlez-Moreno D, Marcote X. On the 3-restricted edge connectivity of permutation graphs[J]. Discrete Applied Mathematics, 2009, 157: 1 586-1 591.
    [12]
    Ou J P. On optimizing edge-connectivity of product graphs[J]. Discrete Mathematics, 2011, 311: 478-492.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    Get Citation
    PDF
    XML
    [1]
    Xu J M. Theory and Application of Graphs[M]. Dordrecht/Boston/London: Kluwer Academic Publishers, 2003.
    [2]
    Fbrega J, Fiol M A. Extraconnectivity of graphs with large girth[J]. Discrete Mathematics, 1994, 127: 163-170.
    [3]
    Fbrega J, Fiol M A. On the extraconnectivity of graphs[J]. Discrete Mathematics, 1996, 155: 49-57.
    [4]
    Esfahanian A H, Hakimi S L. On computing a conditional edge-connectivity of a graph[J]. Information Processing Letters, 1988, 27: 195-199.
    [5]
    Bonsma P, Ueffing N, Volkmann L. Edge-cuts leaving components of order at least three[J]. Discrete Mathematics, 2002, 256(1-2): 431-439.
    [6]
    Zhang Z, Yuan J. A proof of an inequality concerning k-restricted edge-connectivity[J]. Discrete Mathematics, 2005, 304: 128-134.
    [7]
    Hong Y M, Meng J X, Zhang Z. Edge fault tolerance of graphs with respect to super edge-connectivity[J]. Discrete Applied Mathematics, 2012, 160: 579-587.
    [8]
    Wang D, Lu M. Edge fault tolerance of super edge connectivity for three families of interconnection networks[J]. Information Sciences, 2012, 188: 260-268.
    [9]
    Xu J M. Topological Structure and Analysis of Interconnection Networks[M]. Dordrecht/Boston/London: Kluwer Academic Publishers, 2001.
    [10]
    Chiue W S, Shieh B S. On connectivity of the Cartesian product of two graphs[J]. Applied Mathematics and Computation, 1999, 102: 129-137.
    [11]
    Balbuena C, Gonzlez-Moreno D, Marcote X. On the 3-restricted edge connectivity of permutation graphs[J]. Discrete Applied Mathematics, 2009, 157: 1 586-1 591.
    [12]
    Ou J P. On optimizing edge-connectivity of product graphs[J]. Discrete Mathematics, 2011, 311: 478-492.
    Recommended articles
    TrendMD
    Volume 44 Issue 12 page: 967-974
    Cover

    Article Metrics

    Article views (27) PDF downloads(108)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return