Hyper star structure connectivity of hierarchical folded cubic networks

被引:1
|
作者
Guo, Huimei [1 ]
Hao, Rong-Xia [1 ]
Chang, Jou-Ming [2 ]
Kwon, Young Soo [3 ]
机构
[1] Beijing Jiaotong Univ, Sch Math & Stat, Beijing 100044, Peoples R China
[2] Natl Taipei Univ Business, Inst Informat & Decis Sci, Taipei 10051, Taiwan
[3] Yeungnam Univ, Dept Math, Gyongsan 38541, South Korea
基金
中国国家自然科学基金; 新加坡国家研究基金会;
关键词
Hierarchical folded cube; Structure connectivity; Hyper structure connected; Interconnection network; FAULT-TOLERANCE; COMPONENT;
D O I
10.1007/s11227-024-05992-3
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
With the increasing popularity and diversity of network environments, it is crucial to assess the fault tolerance and stability of the network. Structure connectivity and substructure connectivity are two novel indicators that can better measure the network's fault tolerance compared to traditional connectivity. Additionally, analyzing a network's minimum structure cuts and minimum substructure cuts is an interesting and important subject. For a graph G, let R and M be two connected subgraphs of G. An R-structure cut (resp. R-substructure cut) of G is a set of subgraphs of G, such that each subgraph in the set is isomorphic to R (resp. is isomorphic to a connected subgraph of R), whose deletion disconnects G. If the removal of any minimum R-structure cut (resp. R-substructure cut) divides G into exactly two components, one of which is isomorphic to M, then G is referred to as hyper R|M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R|_{M}$$\end{document}-connected (resp. hyper sub-R|M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R|_{M}$$\end{document}-connected). This paper first studies the K1,r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{1,r}$$\end{document}-structure connectivity and sub-K1,r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{1,r}$$\end{document}-structure connectivity of hierarchical folded cubic network HFQn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\text {HFQ}}_n$$\end{document}. Specifically, we determine both of them are left ceiling n+22 right ceiling \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lceil \frac{n+2}{2}\rceil$$\end{document} for n >= 7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 7$$\end{document} and 2 <= r <= n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\le r\le n-1$$\end{document}. Then, we prove that HFQn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\text {HFQ}}_n$$\end{document} is hyper K1,r|K1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{1,r}|_{K_1}$$\end{document}-connected and hyper sub-K1,r|K1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{1,r}|_{K_1}$$\end{document}-connected.
引用
收藏
页码:14224 / 14241
页数:18
相关论文
共 50 条
  • [41] Set-to-Set Disjoint Paths Routing in Hierarchical Cubic Networks
    Bossard, Antoine
    Kaneko, Keiichi
    COMPUTER JOURNAL, 2014, 57 (02) : 332 - 337
  • [42] The Extra, Restricted Connectivity and Conditional Diagnosability of Split-Star Networks
    Lin, Limei
    Xu, Li
    Zhou, Shuming
    Hsieh, Sun-Yuan
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2016, 27 (02) : 533 - 545
  • [43] The 4-set tree connectivity of (n, k)-star networks
    Li, Chunfang
    Lin, Shangwei
    Li, Shengjia
    THEORETICAL COMPUTER SCIENCE, 2020, 844 : 81 - 86
  • [44] Star structure connectivity of cayley graphs generated by transposition trees
    Pan, Kaige
    Cheng, Dongqin
    JOURNAL OF SUPERCOMPUTING, 2023, 79 (04) : 4398 - 4411
  • [45] The 1-good neighbor connectivity of unidirectional star graph networks
    Li, Chunfang
    Lin, Shangwei
    DISCRETE APPLIED MATHEMATICS, 2021, 304 : 1 - 11
  • [46] K1,1-structure connectivity and K1,1-substructure connectivity of torus networks
    Lv, Yali
    Xu, Yulong
    2017 29TH CHINESE CONTROL AND DECISION CONFERENCE (CCDC), 2017, : 5998 - 6003
  • [47] The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks
    Wang, Shiying
    Wang, Zhenhua
    Wang, Mujiangshan
    COMPUTER JOURNAL, 2016, 59 (12) : 1839 - 1856
  • [48] One-to-many node-disjoint paths of hyper-star networks
    Liptak, Laszlo
    Cheng, Eddie
    Kim, Jong-Seok
    Kim, Sung Won
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (13-14) : 2006 - 2014
  • [49] An exchanged folded hypercube-based topology structure for interconnection networks
    Qi, Heng
    Li, Yang
    Li, Keqiu
    Stojmenovic, Milos
    CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2015, 27 (16) : 4194 - 4210
  • [50] Node-to-Set Disjoint-Path Routing in Hierarchical Cubic Networks
    Bossard, Antoine
    Kaneko, Keiichi
    COMPUTER JOURNAL, 2012, 55 (12) : 1440 - 1446