×

Edge-fault-tolerant edge-bipancyclicity of bubble-sort graphs. (English) Zbl 1334.05074

Summary: The bubble-sort graph \(B_n\) is a bipartite graph. Y. Kikuchi and T. Araki [Inf. Process. Lett. 100, No. 2, 52–59 (2006; Zbl 1185.05090)] have proved that \(B_n\) is edge-bipancyclic for \(n\geq 5\) and \(B_n- F\) is bipancyclic when \(n\geq 4\) and \(|F|\leq n - 3\). In this paper, we improve this result by showing that for any edge set \(F\) of \(B_n\) with \(|F|\leq n - 3\), every edge of \(B_n- F\) lies on a cycle of every even length from 6 to \(n\)! for \(n\geq 5\) and every edge of \(B_n- F\) lies on a cycle of every even length from 8 to \(n\)! for \(n = 4\).

MSC:

05C38 Paths and cycles
90B10 Deterministic network models in operations research

Citations:

Zbl 1185.05090
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B., Hare, D.: Edge-pancyclic block-intersection graphs. Discrete Math., 97, 17–24 (1991) · Zbl 0758.05010 · doi:10.1016/0012-365X(91)90417-Z
[2] Fan, J.: Hamilton-connectivity and cycle-embedding of Möbius cubes. Information Processing Letters, 82, 113–117 (2002) · Zbl 1013.68008 · doi:10.1016/S0020-0190(01)00256-3
[3] Xu, J. M., Ma, M. J.: Cycles in folded hypercubes. Applied Mathematics Letters, 19, 140–145 (2006) · Zbl 1106.05054 · doi:10.1016/j.aml.2005.04.002
[4] Xu, M., Xu, J. M.: Edge-pancyclicity of Möbius cubes. Information Processing Letters, 96, 136–140 (2005) · Zbl 1181.68179 · doi:10.1016/j.ipl.2005.07.003
[5] Xu, M.: Edge-pancyclicity and Hamiltonian connectivity of twisted cubes. Acta Mathematica Sinica, English Series, 26(7), 1315–1322 (2010) · Zbl 1231.05152 · doi:10.1007/s10114-010-8581-x
[6] Bondy, J. A.: Pancyclic graphs I. J. Combin. Theory, 11, 80–84 (1971) · Zbl 0183.52301 · doi:10.1016/0095-8956(71)90016-5
[7] Hobbs, A.: The square of a block is vertex pancyclic. J. Combin. Theory B, 20, 1–4 (1976) · Zbl 0321.05135 · doi:10.1016/0095-8956(76)90061-7
[8] Hsieh, S. Y., Chen, G. H., Ho, C. W.: Fault-free hamiltonian cycles in faulty arrangement graphs. IEEE Transactions on Parallel and Distributed Systems, 10, 223–237 (1999) · Zbl 05106902 · doi:10.1109/71.755822
[9] Hsieh, S. Y., Chen, C. H.: Pancyclicity on Möbius cubes with maximal edge faults. Parallel Computing, 30, 407–421 (2004) · doi:10.1016/j.parco.2003.12.003
[10] Hsu, H. C., Chiang, L. C., Tan, J. J. M., et al.: Fault hamiltonicity of augmented cubes. Parallel Computing, 31, 130–145 (2005) · doi:10.1016/j.parco.2004.10.002
[11] Kikuchi, Y., Araki, T.: Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. In: Proc. 2005 International Symposium on Parallel Architectures, Algorithms and Networks, 2005, 46–71 · Zbl 1185.05090
[12] Kikuchi, Y., Araki, T.: Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52–59 (2006) · Zbl 1185.05090 · doi:10.1016/j.ipl.2006.05.012
[13] Ma, M. J., Liu, G. Z., Xu, J. M.: Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes. Parallel Computing, 33, 36–42 (2007) · doi:10.1016/j.parco.2006.11.008
[14] Xu, J. M., Du, Z. Z., Xu, M.: Edge-fault-tolerant edge-bipancyclicity of hypercubes. Information Processing Letters, 96, 146–150 (2005) · Zbl 1184.68117 · doi:10.1016/j.ipl.2005.06.006
[15] Xu, J. M., Ma, M. J., Du, Z. Z.: Edge-fault-tolerant properties of hypercubes and folded hypercubes. Australasian Journal of Combinatorics, 35, 7–16 (2006) · Zbl 1106.68088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.