×

Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees. (English) Zbl 1251.05077

Summary: A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every pair of vertices that are in different parts of the graph. It is well known that \(Cay(S_{n},B)\) is Hamiltonian laceable, where \(S_{n}\) is the symmetric group on \({1,2,\ldots ,n}\) and \(B\) is a generating set consisting of transpositions of \(S_{n}\).
In this paper, we show that for any \(F\subseteq E(Cay(S_{n},B))\), if \(|F|\leq n - 3\) and \(n\geq 4\), then there exists a Hamiltonian path in \(Cay(S_{n},B) - F\) joining every pair of vertices that are in different parts of the graph. The result is optimal with respect to the number of edge faults.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C05 Trees
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
20B30 Symmetric groups
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Araki, T., Hyper Hamiltonian laceability of Cayley graphs generated by transpositions, Networks, 48, 121-124 (2006) · Zbl 1117.05068
[2] Araki, T.; Kikuchi, Y., Hamiltonian laceability of bubble-sort graphs with edge faults, Inf. Sci., 177, 2679-2691 (2007) · Zbl 1115.68106
[3] Ashir, Y. A.; Stewart, I. A., Fault-tolerant embedding of Hamiltonian circuits in \(k\)-ary \(n\)-cube, SIAM J. Discrete Math., 15, 317-328 (2002) · Zbl 1018.68058
[4] Cheng, E.; Lipták, L., Linearly many faults in Cayley graphs generated by transposition trees, Inf. Sci., 177, 4877-4882 (2007) · Zbl 1129.68050
[5] Day, K.; Tripathi, A., Embedding of cycles in arrangement graphs, IEEE Trans. Comput., 42, 1001-1006 (1993) · Zbl 1395.05090
[6] Fu, J. S., Conditional fault-tolerant Hamiltonicity of star graphs, Parallel Comput., 33, 488-496 (2007)
[7] Godsil, C.; Royle, G., Algebraic Graph Theory (2004), Springer-Verlag: Springer-Verlag Berlin, pp. 9, 33, 66-67
[8] Hsieh, S. Y.; Chen, G.; Ho, C., Hamiltonian-laceability of star graphs, Networks, 36, 225-232 (2000) · Zbl 0968.05051
[9] Hsieh, S. Y.; Chen, G. H.; Ho, C. W., Fault-Free Hamiltonian cycles in faulty arrangement graphs, IEEE Trans. Parallel Distrib. Syst., 10, 223-237 (1999)
[10] Hsieh, S. Y.; Guo, Z. N., Hamilton-connectivity and strongly Hamiltonian-laceability of folded hypercube, Comput. Math. Appl., 53, 1040-1044 (2007) · Zbl 1149.68409
[11] Hsieh, S. Y.; Guo, Z. N., 1-vertex-Hamiltonian-laceability of hypercubes with maximal edge faults, J. Interconnection Networks, 6, 407-415 (2005)
[12] Hsieh, S. Y.; Lee, C. W., Conditional edge-fault Hamiltonicity of matching composition networks, IEEE Trans. Parallel Distrib. Syst., 20, 581-592 (2009)
[13] Hsieh, S. Y.; Weng, Y. F., Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults, Theory Comput. Syst., 25, 407-427 (2009) · Zbl 1187.68344
[14] Hsu, H. C.; Li, T. K.; Tan, J. M.; Hsu, L. H., Fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graphs, IEEE Trans. Comput., 53, 39-53 (2004)
[15] Hung, H. S.; Fu, J. S.; Chen, G. H., Fault-free Hamiltonian cycles in crossed cubes with conditional link faults, Inf. Sci., 177, 5664-5674 (2007) · Zbl 1132.68018
[16] Kikuchi, Y.; Araki, T., Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs, Inf. Process. Lett., 100, 52-59 (2006) · Zbl 1185.05090
[17] Kompel’makher, V. L.; Liskovets, V. A., Sequential generation of arrangements by means of a basis of transpositions, Kibernetica, 3, 17-21 (1975)
[18] Li, Y.; Peng, S.; Chu, W., Hamiltonian connectedness of recursive dual-net, Proceedings of the 9th IEEE International Conference on Computer and Information Technology, 1, 203-208 (2009)
[19] Li, T.; Tan, J. J.; Hsu, L., Hyper Hamiltonian laceability on edge fault star graph, Inf. Sci., 165, 59-71 (2004) · Zbl 1057.05054
[20] Liu, W.; Hildebrandt, T. H.; Cavin, R., Hamiltonian cycles in the shuffle-exchange network, IEEE Trans. Comput., 38, 745-750 (1989) · Zbl 1395.68017
[21] Lo, R. S.; Chen, G. H., Embedding Hamiltonian paths in faulty arrangement graphs with the backtracking method, IEEE Trans. Parallel Distrib. Syst., 12, 209-222 (2001)
[22] Tchuente, M., Generation of permutations by graphical exchanges, ARS Combinatria, 14, 115-122 (1982) · Zbl 0508.05041
[23] Tsai, C. H., Linear array and ring embeddings in conditional faulty hypercubes, Theor. Comput. Sci., 314, 431-443 (2004) · Zbl 1072.68082
[24] Tsai, P. Y.; Fu, J. S.; Chen, G. H., Fault-free longest paths in star networks with conditional link faults, Theor. Comput. Sci., 410, 766-775 (2009) · Zbl 1162.68004
[25] Tsai, P. Y.; Fu, J. S.; Chen, G. H., Embedding Hamiltonian cycles in alternating group graphs under conditional fault model, Inf. Sci., 179, 851-857 (2009) · Zbl 1163.68330
[26] Tsai, C. H.; Tan, J.; Liang, T.; Hsu, L., Fault-tolerant Hamiltonian laceability of hyper- cubes, Inf. Process. Lett., 83, 301-306 (2002) · Zbl 1043.68081
[27] Wang, D., On embedding Hamiltonian cycles in crossed cubes, IEEE Trans. Parallel Distrib. Syst., 19, 334-346 (2008)
[28] Wong, S., Hamiltonian cycles and paths in butterfly graphs, Networks, 26, 145-150 (1995) · Zbl 0855.05080
[29] Yang, W.; Li, H.; Meng, J., Conditional connectivity of Cayley graphs by transposition trees, Inf. Process. Lett., 110, 1027-1030 (2010) · Zbl 1379.05069
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.