Embedded edge connectivity of k-ary n-cubes

被引：8
|
作者：
Yang, Yuxing [1 ,2 ]
机构：
[1] Henan Normal Univ, Sch Math & Informat Sci, Xinxiang 453007, Henan, Peoples R China
[2] Henan Normal Univ, Henan Engn Lab Big Data & Stat Anal & Optimal Cont, Xinxiang 453007, Henan, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2023年 / 180卷
关键词：
Interconnection network; k-ary n-cubes; Fault tolerance; Embedded edge connectivity; CONDITIONAL CONNECTIVITY; TOPOLOGICAL PROPERTIES; NETWORKS;
D O I：
10.1016/j.ipl.2022.106328
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The t-embedded edge connectivity eta t(Gn) of an n-dimensional recursive network Gn is the minimum number of edges, if any, whose removal disconnects Gn and each vertex of the resultant network lies in a t-dimensional subnetwork of Gn. The k-ary n-cube is one of the most attractive interconnection networks for parallel computer systems. One of the main results in [15] showed that eta t(Qn3) = 2(n - t)3t for 0 < t < n -1. In this short paper, we generalize the above result and prove that eta t(Qnk) = 2(n - t)kt for 0 < t < n - 1 and odd k > 3.(c) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页数：4
相关论文
共 50 条
  • [31] Embedding long paths in k-ary n-cubes with faulty nodes and links
    Stewart, Iain A.
    Xiang, Yonghong
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2008, 19 (08) : 1071 - 1085
  • [32] Hamiltonian cycles passing through linear forests in k-ary n-cubes
    Wang, Shiying
    Yang, Yuxing
    Li, Jing
    Lin, Shangwei
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (14) : 1425 - 1435
  • [33] Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes
    Ashir, YA
    Stewart, IA
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (03) : 317 - 328
  • [34] Hamiltonian Cycles through Prescribed Edges in k-Ary n-Cubes
    Stewart, Iain A.
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, 2011, 6831 : 82 - 97
  • [35] Balanced Dimension-Order Routing for k-ary n-cubes
    Miguel Montanana, Jose
    Koibuchi, Michihiro
    Matsutani, Hiroki
    Amano, Hideharu
    2009 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING WORKSHOPS (ICPPW 2009), 2009, : 499 - +
  • [36] ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES
    Stewart, Iain A.
    PARALLEL PROCESSING LETTERS, 2012, 22 (01)
  • [37] Routing in bidirectional k-ary n-cubes with the Red Rover algorithm
    Draper, J
    Petrini, F
    INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-III, PROCEEDINGS, 1997, : 1184 - 1193
  • [38] Fault-tolerant embedding of cycles of various lengths in k-ary n-cubes
    Wang, Shiying
    Li, Jing
    Lin, Shangwei
    Wang, Ruixia
    INFORMATION AND COMPUTATION, 2013, 230 : 55 - 66
  • [39] Hamiltonian Cycle and Path Embeddings in k-Ary n-Cubes Based on Structure Faults
    Lv, Yali
    Lin, Cheng-Kuan
    Fan, Jianxi
    COMPUTER JOURNAL, 2017, 60 (02) : 159 - 179
  • [40] Paired 2-disjoint path covers of faulty k-ary n-cubes
    Chen, Xie-Bin
    THEORETICAL COMPUTER SCIENCE, 2016, 609 : 494 - 499
12345