The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 （2006）] have proved tha...The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 （2006）] have proved that Bn is edge-bipancyclic for n ≤ 5 and Bn - F is bipancyclic when n ≥ 4 and IFI≤ n - 3. In this paper, we improve this result by showing that for any edge set F of Bn with IFI ≤ n - 3, every edge of Bn - F lies on a cycle of every even length from 6 to n! for n≤ 5 and every edge of Bn - F lies on a cycle of every even length from 8 to n! for n = 4.展开更多
基金Supported by National Natural Science Foundation of China(Grant Nos.10626053,10701074 and 11171160)Sciences Foundation for Young Scholars of Beijing Normal UniversityPriority Discipline of Beijing Normal University,Fundamental Research Funds for the Central Universities
文摘The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 （2006）] have proved that Bn is edge-bipancyclic for n ≤ 5 and Bn - F is bipancyclic when n ≥ 4 and IFI≤ n - 3. In this paper, we improve this result by showing that for any edge set F of Bn with IFI ≤ n - 3, every edge of Bn - F lies on a cycle of every even length from 6 to n! for n≤ 5 and every edge of Bn - F lies on a cycle of every even length from 8 to n! for n = 4.
