×

Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges. (English) Zbl 1281.05100

Summary: F. Ruskey and C. D. Savage [SIAM J. Discrete Math. 6, No. 1, 152–166 (1993; Zbl 0771.05050)] asked the following question: for \(n\geq 2\), does every matching in \(Q_n\) extend to a Hamiltonian cycle in \(Q_n\)? Fink showed that the answer is yes for every perfect matching, thereby proving Kreweras’ conjecture. In this paper we consider the question in hypercubes with faulty edges. We show for \(n\geq 2\) that every matching \(M\) of at most \(2n-1\) edges extends to a Hamiltonian cycle in \(Q_n\). Moreover, we prove that when \(n\geq 4\) and \(M\) is nonempty this conclusion still holds even if \(Q_n\) has at most \(n-1-\lceil\frac{| M|}{2}\rceil\) faulty edges, with one exception.

MSC:

05C65 Hypergraphs
05C45 Eulerian and Hamiltonian graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0771.05050
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan Press: Macmillan Press London · Zbl 1226.05083
[2] Chan, M. Y.; Lee, S. J., On the existence of Hamiltonian circuits in faulty hypercubes, SIAM J. Discrete Math., 4, 511-527 (1991) · Zbl 0747.05035
[3] Dimitrov, D.; Dvořák, T.; Gregor, P.; Škrekovski, R., Gray codes avoiding matchings, Discrete Math. Theor. Comput. Sci., 11, 123-148 (2009) · Zbl 1192.94070
[4] Dvořák, T., Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math., 19, 135-144 (2005) · Zbl 1082.05056
[5] Dvořák, T.; Gregor, P., Hamiltonian fault-tolerance of hypercubes, Electron. Notes Discrete Math., 29, 471-477 (2007) · Zbl 1341.05142
[6] Fink, J., Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B, 97, 1074-1076 (2007) · Zbl 1126.05080
[7] Fink, J., Matching graphs of hypercubes and complete bipartite graphs, European J. Combin., 30, 7, 1624-1629 (2009) · Zbl 1218.05128
[8] Gros, L., Théorie du Baguenodier (1872), Aimé Vingtrinier: Aimé Vingtrinier Lyon
[9] Harary, F.; Hayes, J. P.; Wu, H. J., A survey of the theory of hypercube graphs, Comput. Math. Appl., 15, 277-286 (1988)
[10] Havel, I., On Hamiltonian circuits and spanning trees of hypercube, Čas. Pěst. Mat., 109, 135-152 (1984) · Zbl 0544.05057
[11] Kreweras, G., Matchings and Hamiltonian cycle on hypercubes, Bull. Inst. Combin. Appl., 16, 87-91 (1996) · Zbl 0855.05089
[12] Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA · Zbl 0743.68007
[13] Li, T. K.; Tsai, C. H.; Tan, J. J.M.; Hsu, L. H., Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes, Inform. Process. Lett., 87, 107-110 (2003) · Zbl 1161.68684
[14] Ruskey, F.; Savage, C. D., Hamilton cycles that extend transposition matchings in Cayley graphs of \(S_n\), SIAM J. Discrete Math., 6, 1, 152-166 (1993) · Zbl 0771.05050
[15] Savage, C., A survey of combinatorial gray codes, SIAM Rev., 39, 605-629 (1997) · Zbl 1049.94513
[16] Sengupta, A., On ring embedding in hypercubes with faulty nodes and links, Inform. Process. Lett., 68, 207-214 (1998) · Zbl 1339.68213
[17] Tsai, C. H.; Lai, Y. C., Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Inform. Sci., 177, 5590-5597 (2007) · Zbl 1132.68019
[18] Vandenbussche, J.; West, D. B., Matching extendibility in hypercubes, SIAM J. Discrete Math., 23, 3, 1539-1547 (2009) · Zbl 1207.05161
[19] Wang, W. Q.; Chen, X. B., A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges, Inform. Process. Lett., 107, 205-210 (2008) · Zbl 1186.68035
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.