ISSN 0253-2778

CN 34-1054/N

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

On 2-extra edge connectivity of folded crossed cube

Funds:  Supported by College Scientific Research Project of Xinjiang (XJEDU2018Y021), National College Students Innovation and Entrepreneurship Training Program (201810758035).
Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2020.02.002
More Information
  • Corresponding author: CAI Xuepeng (corresponding author), male, born in 1991, master/lecturer. Research field: Graph theory and its application. E-mail: cxpmaths@163.com
  • Received Date: 13 June 2019
  • Accepted Date: 30 July 2019
  • Rev Recd Date: 30 July 2019
  • Publish Date: 28 February 2020
    Abstract

  • Abstract

    The g-extra edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. Let G be a connected graph and an integer g≥0, the g-extra edge connectivity of G, denoted by λg(G), is the minimum cardinality of a set of edges of G, if it exists, whose deletion disconnects G and leaves each remaining component to have at least g+1 vertices.

    Abstract

    The g-extra edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. Let G be a connected graph and an integer g≥0, the g-extra edge connectivity of G, denoted by λg(G), is the minimum cardinality of a set of edges of G, if it exists, whose deletion disconnects G and leaves each remaining component to have at least g+1 vertices.
    • FullText(HTML)
  • loading
    • References(34)
  • [1]
    BONDY J A, MURTY U S R. Graph Theory[M]. New York: Springer, 2008.
    [2]
    XU J M. Topological Structure and Analysis of Interconnection Networks[M]. Dordrecht/ Boston/ London: Kluwer Academic Publishers, 2001.
    [3]
    KULASINGHE P D. Connectivity of the crossed cube[J]. Information Processing Letters, 1997,61(4): 221-226.
    [4]
    HARARY F. Conditional connectivity[J]. Networks, 1983,13(3): 347-357.
    [5]
    FBREGA J, FIOL M A. Extraconnectivity of graphs with large girth[J]. Discrete Math, 1994,127(1-3): 163-170.
    [6]
    FBREGA J, FIOL M A. On the extraconnectivity of graphs[J]. Discrete Math, 1996, 155: 49-57.
    [7]
    CAI X P, VUMAR E. The super connectivity of folded crossed cubes[J]. Information Processing Letters, 2019,142: 52-56.
    [8]
    CHEN Y C, TAN J J M, HSU L H. Super-connectivity and super-edge-connectivity for some interconnection networks[J]. Applied Mathematics and Computation, 2003,140(2): 245-254.
    [9]
    GUO L, QIN C, GUO X. Super connectivity of Kronecker products of graphs[J]. Information Processing Letters, 2010,110(16): 659-661.
    [10]
    LV M, CHEN G L, XU J M. On super edge-connectivity of Cartesian product graphs[J]. Networks, 2007,49(2): 135-157.
    [11]
    MA M J, ZHU L Y. The super connectivity of exchanged hypercubes[J]. Information Processing Letters, 2011,111(8): 360-364.
    [12]
    MA M J, LIU G Z, XU J M. The super connectivity of augmented cubes[J]. Information Processing Letters, 2008,106(2): 59-63.
    [13]
    NING W T. The super connectivity of exchanged crossed cube[J]. Information Processing Letters, 2016,116(2): 80-84.
    [14]
    WANG H, SHAN E, WANG W. On the super connectivity of Kronecker products of graphs[J]. Information Processing Letter, 2012, 112: 402-405.
    [15]
    XU J M, ZHU Q, HOU X M, et al. On restricted connectivity and extra connectivity of hypercubes and folded hypercubes[J]. Journal Shanghai Jiaotong University, 2005,10(2): 203-207.
    [16]
    XU J M, LV M, MA M J, et al. Super connectivity of line graphs[J]. Information Processing Letters, 2005, 94(4): 191-195.
    [17]
    XU J M, XU M, ZHU Q. The super connectivity of shuffle-cubes[J]. Information Processing Letters, 2005,96(4): 123-127.
    [18]
    ZHU Q, XU J M, HOU X M, et al. On reliability of the folded hypercubes[J]. Information Science, 2007,177(8): 1782-1788.
    [19]
    ZHOU J X. On g-extra connectivity of hypercube-like networks[J]. Journal of Computer and System Sciences, 2017, 88: 208-219.
    [20]
    ZHANG M M, ZHOU J X. On g-extra connectivity of folded hypercubes[J]. Theoretical Computer Science, 2015,593: 146-153.
    [21]
    GU M M, HAO R X. 3-extra connectivity of 3-ary n-cube networks[J]. Information Processing Letters, 2013,114(9): 146-153.
    [22]
    CHANG N W, TSAI C Y, HSIEH S Y. On 3-extra connectivity and of 3-extra edge connectivity of folded hypercubes[J]. IEEE Transactions on Computers, 2014,63(6): 1594-1600.
    [23]
    WANG S Y,WANG Z H,WANG M J S. The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks[J]. Computer Journal, 2016, 59(12): 1839-1856.
    [24]
    HONG W S, HSIEH S Y. Extra edge connectivity of hypercube-like networks[J]. International Journal of Parallel, Emergent and Distributed Systems,2013,28(2): 123-133.
    [25]
    ZHU Q, XU J M, LV M. Edge fault tolerance analysis of a class of interconnection networks[J]. Applied Mathematics and Computation, 2006, 172(1): 111-121.
    [26]
    LI X, XU J M. Edge-fault tolerance of hypercube-like network[J]. Information Processing Letters, 2013,113: 760-763.
    [27]
    MA S D, MENG J X. On the reliability of double generalized Petersen graph[J]. Journal of Xinjiang University (Natural Science Edition), 2018,35(2): 150-157.
    [28]
    KFE K, BLACKWELL P K, SLOUGH W, et al. Topological properties of the crossed cube architecture[J]. Parallel Computing, 1994, 20(12): 1763-1775.
    [29]
    KFE K. The crossed cube architecture for parallel computation[J]. IEEE Transactions on Parallel and Distributed Systems, 1992, 3(5): 513-524.
    [30]
    CHEN Y Q, TAN J J M. Restricted connectivity for three families of interconnection networks[J]. Applied Mathematics and Computation, 2007, 188: 1848-1855.
    [31]
    ELAMAWY A, LATIFI S. Properties and performance of folded hypercubes[J]. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(1): 31-42.
    [32]
    ADHIKARI N, TRIPATHY C R. The folded crossed cube:A new interconnection network for parallel systems[J]. International Journal of Computer Applications, 2010,4(3): 43-50.
    [33]
    ZHANG Y Q. Folded-crossed hypercube:A complete interconnection network[J]. Journal of Systems Architecture, 2002,47(11): 917-922.
    [34]
    PAI K J, CHANG J M, YANG J S. Vertex-transitivity on folded crossed cubes[J]. Information Processing Letters, 2016,116(11): 689-693.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    BONDY J A, MURTY U S R. Graph Theory[M]. New York: Springer, 2008.
    [2]
    XU J M. Topological Structure and Analysis of Interconnection Networks[M]. Dordrecht/ Boston/ London: Kluwer Academic Publishers, 2001.
    [3]
    KULASINGHE P D. Connectivity of the crossed cube[J]. Information Processing Letters, 1997,61(4): 221-226.
    [4]
    HARARY F. Conditional connectivity[J]. Networks, 1983,13(3): 347-357.
    [5]
    FBREGA J, FIOL M A. Extraconnectivity of graphs with large girth[J]. Discrete Math, 1994,127(1-3): 163-170.
    [6]
    FBREGA J, FIOL M A. On the extraconnectivity of graphs[J]. Discrete Math, 1996, 155: 49-57.
    [7]
    CAI X P, VUMAR E. The super connectivity of folded crossed cubes[J]. Information Processing Letters, 2019,142: 52-56.
    [8]
    CHEN Y C, TAN J J M, HSU L H. Super-connectivity and super-edge-connectivity for some interconnection networks[J]. Applied Mathematics and Computation, 2003,140(2): 245-254.
    [9]
    GUO L, QIN C, GUO X. Super connectivity of Kronecker products of graphs[J]. Information Processing Letters, 2010,110(16): 659-661.
    [10]
    LV M, CHEN G L, XU J M. On super edge-connectivity of Cartesian product graphs[J]. Networks, 2007,49(2): 135-157.
    [11]
    MA M J, ZHU L Y. The super connectivity of exchanged hypercubes[J]. Information Processing Letters, 2011,111(8): 360-364.
    [12]
    MA M J, LIU G Z, XU J M. The super connectivity of augmented cubes[J]. Information Processing Letters, 2008,106(2): 59-63.
    [13]
    NING W T. The super connectivity of exchanged crossed cube[J]. Information Processing Letters, 2016,116(2): 80-84.
    [14]
    WANG H, SHAN E, WANG W. On the super connectivity of Kronecker products of graphs[J]. Information Processing Letter, 2012, 112: 402-405.
    [15]
    XU J M, ZHU Q, HOU X M, et al. On restricted connectivity and extra connectivity of hypercubes and folded hypercubes[J]. Journal Shanghai Jiaotong University, 2005,10(2): 203-207.
    [16]
    XU J M, LV M, MA M J, et al. Super connectivity of line graphs[J]. Information Processing Letters, 2005, 94(4): 191-195.
    [17]
    XU J M, XU M, ZHU Q. The super connectivity of shuffle-cubes[J]. Information Processing Letters, 2005,96(4): 123-127.
    [18]
    ZHU Q, XU J M, HOU X M, et al. On reliability of the folded hypercubes[J]. Information Science, 2007,177(8): 1782-1788.
    [19]
    ZHOU J X. On g-extra connectivity of hypercube-like networks[J]. Journal of Computer and System Sciences, 2017, 88: 208-219.
    [20]
    ZHANG M M, ZHOU J X. On g-extra connectivity of folded hypercubes[J]. Theoretical Computer Science, 2015,593: 146-153.
    [21]
    GU M M, HAO R X. 3-extra connectivity of 3-ary n-cube networks[J]. Information Processing Letters, 2013,114(9): 146-153.
    [22]
    CHANG N W, TSAI C Y, HSIEH S Y. On 3-extra connectivity and of 3-extra edge connectivity of folded hypercubes[J]. IEEE Transactions on Computers, 2014,63(6): 1594-1600.
    [23]
    WANG S Y,WANG Z H,WANG M J S. The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks[J]. Computer Journal, 2016, 59(12): 1839-1856.
    [24]
    HONG W S, HSIEH S Y. Extra edge connectivity of hypercube-like networks[J]. International Journal of Parallel, Emergent and Distributed Systems,2013,28(2): 123-133.
    [25]
    ZHU Q, XU J M, LV M. Edge fault tolerance analysis of a class of interconnection networks[J]. Applied Mathematics and Computation, 2006, 172(1): 111-121.
    [26]
    LI X, XU J M. Edge-fault tolerance of hypercube-like network[J]. Information Processing Letters, 2013,113: 760-763.
    [27]
    MA S D, MENG J X. On the reliability of double generalized Petersen graph[J]. Journal of Xinjiang University (Natural Science Edition), 2018,35(2): 150-157.
    [28]
    KFE K, BLACKWELL P K, SLOUGH W, et al. Topological properties of the crossed cube architecture[J]. Parallel Computing, 1994, 20(12): 1763-1775.
    [29]
    KFE K. The crossed cube architecture for parallel computation[J]. IEEE Transactions on Parallel and Distributed Systems, 1992, 3(5): 513-524.
    [30]
    CHEN Y Q, TAN J J M. Restricted connectivity for three families of interconnection networks[J]. Applied Mathematics and Computation, 2007, 188: 1848-1855.
    [31]
    ELAMAWY A, LATIFI S. Properties and performance of folded hypercubes[J]. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(1): 31-42.
    [32]
    ADHIKARI N, TRIPATHY C R. The folded crossed cube:A new interconnection network for parallel systems[J]. International Journal of Computer Applications, 2010,4(3): 43-50.
    [33]
    ZHANG Y Q. Folded-crossed hypercube:A complete interconnection network[J]. Journal of Systems Architecture, 2002,47(11): 917-922.
    [34]
    PAI K J, CHANG J M, YANG J S. Vertex-transitivity on folded crossed cubes[J]. Information Processing Letters, 2016,116(11): 689-693.)
    Recommended articles
    TrendMD
    Volume 50 Issue 2 page: 94-99
    Cover

    Article Metrics

    Article views (68) PDF downloads(89)
    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