Research on Edge-Fault-Tolerant Two-Disjoint-Cycle-Cover in Bubble-Sort Star Graphs
旭霖 黄 · Advances in Applied Mathematics · 2025
n 维冒泡排序星图 B S n 是一个( 2n−3 )-正则二部图，具有 n! 个顶点。图中存在两个不相交的圈 C 1 和 C 2 ，并且这些圈能够覆盖图中的所有顶点，则被称为图的两个不相交的圈覆盖。如果对于任意边集 F⊆E( G ) 且 | F |≤k ，在 G−F 中存在两个顶点不相交的圈 C 1 和 C 2 ，它们的顶点数加起来正好等于图的顶点数，则被称为 k -边容错两个不相交的圈覆盖。本文证明对于 n≥4 时，冒泡排序星图是存在( 2n−5 )-边容错两个不相交的圈覆盖。The n -dimensional bubble-sort star graph B S n is known to be a ( 2n−3 )-regular bipartite graph with n! vertices. The property where there exist two disjoint cycles C 1 and C 2 that together cover all the vertices of the graph is called the two disjoint cycle cover of the graph. Let F be an edge set in the bubble-sort star graph with F⊆E( G ) , | F |≤k , there exist two disjoint cycles C 1 and C 2 in G−F , and their combined vertex count equals the total number of vertices in the graph, this is referred to as the k -edge-fault-tolerant two disjoint cycle cover. This paper proves that for n≥4 , the bubble-sort star graph is a ( 2n−5 )-edge-fault-tolerant two disjoint cycle cover.