冒泡排序星图中边容错的两个不相交的圈覆盖问题研究

Research on Edge-Fault-Tolerant Two-Disjoint-Cycle-Cover in Bubble-Sort Star Graphs

摘要: $n$ 维冒泡排序星图$B{S}_n$ 是一个($2n-3$ )-正则二部图，具有$n!$ 个顶点。图中存在两个不相交的圈$C_1$ 和$C_2$ ，并且这些圈能够覆盖图中的所有顶点，则被称为图的两个不相交的圈覆盖。如果对于任意边集$F\subseteq E\left(G\right)$ 且$\left|F\right|\le k$ ，在$G-F$ 中存在两个顶点不相交的圈$C_1$ 和$C_2$ ，它们的顶点数加起来正好等于图的顶点数，则被称为$k$ -边容错两个不相交的圈覆盖。本文证明对于$n\ge 4$ 时，冒泡排序星图是存在($2n-5$ )-边容错两个不相交的圈覆盖。

Abstract: 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\subseteq E\left(G\right)$ , $\left|F\right|\le 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\ge 4$ , the bubble-sort star graph is a ($2n-5$ )-edge-fault-tolerant two disjoint cycle cover.