.png){kind=icon}
.png){kind=icon}
Return
Fault Hamiltonicity and fault Hamiltonian connectivity of (n, k)-bubble sort graphs
.png){kind=icon}
PRE
AI
H
Y
DOI：10.1016/j.amc.2026.130218.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Hamiltonian properties are vital metrics for the structural robustness and communication efficiency of interconnection networks. Formally, a Hamiltonian path in a graph G is defined as a path that includes every vertex from the vertex set of G exactly one time. When this property holds for all possible pairs of distinct vertices in G, the graph is classified as Hamiltonian-connected. Similarly, a cycle which passes through each vertex of a graph precisely one time is called Hamiltonian. Consequently, any graph that contains at least one Hamiltonian cycle earns the designation of being a Hamiltonian graph. The graph Bn,k, known as the (n, k)-bubble sort graph, refers to a significant interconnection structure, formed by generalizing the classical bubble-sort graph Bn. In this paper, we present a comprehensive analysis of fault Hamiltonian properties for Bn,k. We prove that, for T ⊂ V(Bn,k) ∪ E(Bn,k) and under conditions n ≥ 6, k ≥ 2, n−k≥2 , the graph Bn,k−T admits a Hamiltonian cycle when |T|≤n−3 , and is Hamiltonian connected when |T|≤n−4 .
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W
Organization
No organization information available
Cited Papers