Edge-bipancyclicity of bubble-sort star graphs

Abstract

The interconnection network considered in this paper is the bubble-sort star graph. The $n$-dimensional bubble-sort star graph $BS_n$ is a bipartite and $(2n-3)$-regular graph of order $n!$. A bipartite graph $G$ is edge-bipancyclic if each edge of $G$ lies on a cycle of all even length $l$ with $4\leq l\leq |V(G)|$. In this paper, we show that the $n$-dimensional bubble-sort star graph $BS_n$ is edge-bipancyclic for $n\ge 3$ and for each even length $l$ with $4\leq l\leq n!$, every edge of $BS_n$ lies on at least four different cycles of length $l$.

13 pages, 5 figures, 6 tables