Article
Mathematics, Applied
Huifeng Zhang, Xirong Xu, Ziming Wang, Qiang Zhang, Yuansheng Yang
Summary: This paper focuses on the fault-tolerant Hamiltonian connectivity of the augmented cube AQ(n) and proves properties related to weak vertex-pairs and fault-free Hamiltonian paths in AQ(n). The paper provides an optimal and sharp result without restrictions on each vertex.
Article
Computer Science, Theory & Methods
Guo Chen, Baolei Cheng, Dajin Wang
Summary: This article discusses the importance and applications of constructing Completely Independent Spanning Trees (CISTs) in a network, especially in data center networks. It also introduces the augmented cube AQn as the underlying structure of a data center network and studies how to construct n-1 optimal CISTs in its logic graph L-AQDNn. Additionally, the relationship between the dimension of a hypercube-family network and the number of CISTs it can host is established for the first time.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2021)
Article
Mathematics
James Carraher, Michael Ferrara, Timothy Morris, Michael Santana
Summary: This paper investigates the pancyclicity property of 4-connected graphs and proves that certain types of 4-connected graphs are pancyclic. It also describes the situation of specific forbidden subgraphs for pancyclicity in 4-connected graphs.
DISCRETE MATHEMATICS
(2021)
Article
Mathematics, Applied
Meijie Ma, Jiguo Yu
Summary: This article investigates edge-disjoint paths in augmented cubes with faulty edges, proving some important results and introducing the concept of extra edge-connectivity.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Engineering, Multidisciplinary
Burhan Selcuk, Ayse Nur Altintas Tankuel
Summary: This paper reconsiders the study of Connected Square Network Graphs (CSNG) as presented by Selcuk (2022) and Selcuk and Tankul (2022). While CSNG is a 2-dimensional mesh structure, its most important feature is that it is a hypercube variant. Therefore, this study focuses on developing algorithms that utilize hypercube to solve various problems in CSNG. Firstly, an efficient algorithm for finding the Hamiltonian path is proposed. Additionally, two different algorithms for label mapping in the graph and unicast routing are presented. The parallel process for mapping and unicast routing is also discussed, along with guidelines for broadcasting algorithms. © 2023 Karabuk University. Publishing services by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
ENGINEERING SCIENCE AND TECHNOLOGY-AN INTERNATIONAL JOURNAL-JESTECH
(2023)
Article
Multidisciplinary Sciences
Mohammad Awadh, Zaid Hussain, Hesham Almansouri
Summary: This paper proposes an algorithm to prove the panconnectivity of Eisenstein-Jacobi networks by constructing cycles of specific lengths between any two nodes. The algorithm adopts and modifies the idea of Dynamic Source Routing and provides the time complexity and results of test cases.
KUWAIT JOURNAL OF SCIENCE
(2023)
Article
Computer Science, Hardware & Architecture
Lina Ba, Yaxian Zhang, Heping Zhang
Summary: This paper investigates the P-t-structure connectivity and P-t-substructure connectivity of augmented k-ary n-cubes AQ(n,k). The minimum connectivity for these graphs is obtained under certain conditions.
Article
Computer Science, Hardware & Architecture
Jin Huo, Weihua Yang
Summary: This paper mainly studies the pancyclic and Hamiltonian properties of the dragonfly network D(n, h), and finds that it is Hamiltonian-connected when n >= 1, h >= 2, and pancyclic and vertex-pancyclic when n >= 4, h >= 2.
Article
Computer Science, Hardware & Architecture
Yujie Zhang, Weibei Fan, Zhijie Han, Yunfei Song, Ruchuan Wang
Summary: The study proposes a fault-tolerant routing algorithm based on virtual network partition technology for 3-ary n-cube networks, proving its deadlock free property. It also explores constructing disjoint paths under the fault model and proposes a fault-tolerant routing algorithm based on structure faults with disjoint paths. Simulation results show significant improvements compared to previous algorithms.
JOURNAL OF SUPERCOMPUTING
(2021)
Article
Mathematics
Xia Li, Weihua Yang
Summary: A graph is l-path Hamiltonian if every path of length not exceeding l is contained in a Hamiltonian cycle. It is known that a 2-connected, k-regular graph G on at most 3k - 1 vertices is edge-Hamiltonian if {u, v} is not a cut-set for every edge uv of G. Thus, G is 1-path Hamiltonian if G - {u, v} is connected for every edge uv of G. In this paper, we prove that if G - V (P) is connected, where P = uv z is a 2-path of a 2-connected, k-regular graph G on at most 2k vertices, then there exists a Hamiltonian cycle containing the 2-path P. This work presents a condition for a 2-connected, k-regular graph to be 2-path Hamiltonian, with an example showing that the maximum number is at most 2k + 1.
DISCRETE MATHEMATICS
(2023)
Article
Computer Science, Hardware & Architecture
Hongwei Qiao, Jixiang Meng, Eminjan Sabir
Summary: Reliability is a fundamental consideration in network design. This paper investigates the embedding of spanning disjoint paths in enhanced hypercube networks with edge fault tolerance. Theoretical and experimental results are provided to support the findings.
JOURNAL OF SUPERCOMPUTING
(2023)
Article
Computer Science, Information Systems
Weibei Fan, Jianxi Fan, Zhijie Han, Peng Li, Yujie Zhang, Ruchuan Wang
Summary: This paper mainly studies the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQ(s, t) - (f(v) + f(e)), proving that for s > 2, t > 3, and s <= t, an LeTQ(s, t) can tolerate up to s - 1 faulty vertices and edges when embedding a Hamiltonian cycle. Furthermore, it is also proven that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQ(s, t) with up to (s - 2) faulty vertices and edges. The results demonstrate that LeTQ(s, t) is (s - 1)-Hamiltonian and (s - 2)-Hamiltonian-connected, achieving optimal (s - 1)-fault-tolerant Hamiltonicity and (s - 2) fault-tolerant Hamiltonian connectivity.
FRONTIERS OF COMPUTER SCIENCE
(2021)
Article
Computer Science, Hardware & Architecture
Ying-Ze Zhao, Xiang-Jun Li, Meijie Ma
Summary: Many interconnection networks in large-scale parallel computing have hierarchical and recursive structures. This paper focuses on the structures of the Crossed cube and the Mobius cube in the bijective connection networks, and determines their embedded connectivity using these structural properties.
JOURNAL OF SUPERCOMPUTING
(2022)
Article
Mathematics, Applied
Lan Xiao, Yubao Guo
Summary: This study proves that a semicomplete digraph has a certain type of path if it satisfies certain conditions. Additionally, specific conditions for tournaments are also investigated.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Information Systems
Hao Xu, Yixuan Fan, Wenyu Li, Lei Zhang
Summary: This article explores a trustworthy and fault-tolerant framework for connected critical autonomous systems (C-CAS) to achieve hyperreliable global decision making in a trustless environment. The proposed framework is based on distributed consensus mechanisms, such as practical Byzantine fault tolerance (PBFT) and Raft, under the perception-initiative-consensus-action (PICA) protocol with wireless connections among the nodes. The results show that wireless distributed consensus (WDC) significantly improves overall system reliability.
IEEE INTERNET OF THINGS JOURNAL
(2023)