ISSN 0253-2778

CN 34-1054/N

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

Hamilton paths and cycles in fault-tolerant varietal hypercubes

  • 1.

    School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

  • 2.

    Wu Wen-Tsun Key Laboratory of Mathematics, USTC, Chinese Academy of Sciences, Hefei 230026, China

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

    HUANG Yanyun, female, born in 1984, master. Research field: graph theory. E-mail: hwaiwai@mail.ustc.edu.cn

  • Corresponding author: XU Junming
  • Received Date: 28 August 2014
  • Accepted Date: 08 April 2015
  • Rev Recd Date: 08 April 2015
  • Publish Date: 30 June 2015
    Abstract

  • Abstract

    The varietal hypercube VQn, a variant of the hypercube Qn, was studied. It was proved that VQn contains a fault-free Hamilton cycle provided faulty edges do not exceed n－2, and that for two distinct vertices, x and y, there is a fault-free xy-Hamilton path in VQn provided faulty edges do not exceed n－3 for n≥3. The proof is based on an inductive construction.

    Abstract

    The varietal hypercube VQn, a variant of the hypercube Qn, was studied. It was proved that VQn contains a fault-free Hamilton cycle provided faulty edges do not exceed n－2, and that for two distinct vertices, x and y, there is a fault-free xy-Hamilton path in VQn provided faulty edges do not exceed n－3 for n≥3. The proof is based on an inductive construction.
    • FullText(HTML)
  • loading
    • References(10)
  • [1]
    Cheng S Y, Chuang J H. Varietal hypercube: A new interconnection networks topology for large scale multicomputer[C]// Proceedings of International Conference on Parallel and Distributed Systems. IEEE, 1994: 703-708.
    [2]
    Wang J W, Xu J M. Reliability analysis of varietal hypercube networks[J]. Journal of University of Science and Technology of China, 2009, 39(12):1 248-1 252.
    [3]
    Jiang M, Hu X Y, Li Q L. Fault-tolerant diameter and width diameter of varietal hypercubes[J]. Applied Mathematics: Journal of Chinese University, Ser A, 2010, 25(3): 372-378 (in Chinese).
    [4]
    Xiao L, Cao J, Xu J M. Transitivity of varietal hypercube networks[J]. Frontiers of Mathematics in China, 2014, 9(6): 1 401-1 410.
    [5]
    Xu J M, Ma M J. A survey on cycle and path embedding in some networks[J]. Frontiers of Mathematics in China, 2009, 4(2): 217-252.
    [6]
    Cao J, Xiao L, Xu J M. Cycles and paths embedded in varietal hypercubes[J]. Journal of University of Science and Technology of China, 2014, 44(9): 732-737.
    [7]
    Xu J M. Theory and Application of Graphs[M]. Dordrecht/Boston/London: Kluwer Academic Publishers, 2003.
    [8]
    Chen Y C, Tsai C H, Hsu L H, et al. On some super fault-tolerant Hamiltonian graphs[J]. Applied Mathematics and Computation, 2004, 148(3): 729-741.
    [9]
    Huang W T, Chuang Y C, Tan J J M, et al. On the fault-tolerant Hamiltonicity of faulty crosses cubes[J]. IEICE Trans on Fundamentals, 2002, E85-A(6): 1 359-1 370.
    [10]
    Hsieh S Y, Lee C W. Conditional edge-fault Hamiltonicity of matching composition networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(4): 581-592.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    Cheng S Y, Chuang J H. Varietal hypercube: A new interconnection networks topology for large scale multicomputer[C]// Proceedings of International Conference on Parallel and Distributed Systems. IEEE, 1994: 703-708.
    [2]
    Wang J W, Xu J M. Reliability analysis of varietal hypercube networks[J]. Journal of University of Science and Technology of China, 2009, 39(12):1 248-1 252.
    [3]
    Jiang M, Hu X Y, Li Q L. Fault-tolerant diameter and width diameter of varietal hypercubes[J]. Applied Mathematics: Journal of Chinese University, Ser A, 2010, 25(3): 372-378 (in Chinese).
    [4]
    Xiao L, Cao J, Xu J M. Transitivity of varietal hypercube networks[J]. Frontiers of Mathematics in China, 2014, 9(6): 1 401-1 410.
    [5]
    Xu J M, Ma M J. A survey on cycle and path embedding in some networks[J]. Frontiers of Mathematics in China, 2009, 4(2): 217-252.
    [6]
    Cao J, Xiao L, Xu J M. Cycles and paths embedded in varietal hypercubes[J]. Journal of University of Science and Technology of China, 2014, 44(9): 732-737.
    [7]
    Xu J M. Theory and Application of Graphs[M]. Dordrecht/Boston/London: Kluwer Academic Publishers, 2003.
    [8]
    Chen Y C, Tsai C H, Hsu L H, et al. On some super fault-tolerant Hamiltonian graphs[J]. Applied Mathematics and Computation, 2004, 148(3): 729-741.
    [9]
    Huang W T, Chuang Y C, Tan J J M, et al. On the fault-tolerant Hamiltonicity of faulty crosses cubes[J]. IEICE Trans on Fundamentals, 2002, E85-A(6): 1 359-1 370.
    [10]
    Hsieh S Y, Lee C W. Conditional edge-fault Hamiltonicity of matching composition networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(4): 581-592.
    Recommended articles
    TrendMD
    Volume 45 Issue 6 page: 436-442
    Cover

    Article Metrics

    Article views (36) PDF downloads(73)
    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