×

Hamiltonian laceability in hypercubes with faulty edges. (English) Zbl 1377.05132

Summary: It is useful to consider faulty networks because node faults or link faults may occur in networks. In this paper, we investigate hamiltonian properties of conditional faulty hypercubes. Let \(F\) be a set of faulty edges in hypercube \(Q_n\) with \(n \geq 4\) and \(| F | \leq 3 n - 11\). We prove that there still exists a hamiltonian path in \(Q_n - F\) joining any two vertices of different partite sets if the following two constraints are satisfied: \((1)\) the degree of every vertex in \(Q_n - F\) is at least 2, and \((2)\) there is at most one vertex with degree 2 in \(Q_n - F\).

MSC:

05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andre, F.; Verjus, J., Hypercubes and Distributed Computers (1989), North-Halland: North-Halland Amsterdam, New York, Oxford
[3] Castaneda, N.; Gotchev, I., Embedded paths and cycles in faulty hypercubes, J. Combin. Optim., 20, 3, 224-248 (2010) · Zbl 1242.90189
[4] 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
[5] Chen, X. B., Paired many-to-many disjoint path covers of hypercubes with faulty edges, Inform. Process. Lett., 112, 61-66 (2012) · Zbl 1233.68028
[6] Dimitrov, D.; Dvořák, T.; Gregor, P.; Skrekovski, R., Gray codes avoiding matchings, Discrete Math. Theor. Comput. Sci., 11, 123-148 (2009) · Zbl 1192.94070
[7] Dvořák, T., Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math., 19, 135-144 (2005) · Zbl 1082.05056
[8] Dvořák, T.; Gregor, P., Hamiltonian fault-tolerance of hypercubes, Electron. Notes Discrete Math., 29, 471-477 (2007) · Zbl 1341.05142
[9] Dvořák, T.; Koubek, V., Computational complexity of long paths and cycles in faulty hypercubes, Theoret. Comput. Sci., 411, 40-42, 3774-3786 (2010) · Zbl 1207.68038
[10] Fink, J.; Gregor, P., Long paths and cycles in hypercubes with faulty vertices, Inform. Sci., 179, 3634-3644 (2009) · Zbl 1193.68052
[11] Gregor, P.; Dvořák, T., Path partitions of hypercubes, Inform. Process. Lett., 108, 402-406 (2008) · Zbl 1191.68037
[12] Gros, L., Theorie Du Baguenodier (1872), Aime Vingtrinier: Aime Vingtrinier Lyon
[13] Havel, I., On Hamiltonian circuits and spanning trees of hypercube, Cas. Pest. Mat., 109, 135-152 (1984) · Zbl 0544.05057
[14] Kueng, T. L.; Liang, T.; Tan, J. M.; Hsu, L. H., Long paths in hypercubes with conditional node-faults, Inform. Sci., 179, 667-681 (2009) · Zbl 1170.68001
[15] Lewinter, M.; Widulski, W., Hyper-Hamilton laceable and caterpillar-spannable product graphs, Comput. Math. Appl., 34, 99-104 (1997) · Zbl 0907.05033
[16] Liu, J. J.; Wang, Y. L., Hamiltonian cycles in hypercubes with faulty edges, Inform. Sci., 256, 225-233 (2014) · Zbl 1320.68130
[17] Simmons, G., Almost all \(n\)-dimensional rectangular lattices are Hamilton laceable, Congr. Numer., 21, 103-108 (1978) · Zbl 0413.05029
[18] Szepietowski, A., Hamiltonian cycles in hypercubes with \(2 n - 4\) faulty edges, Inform. Sci., 215, 75-82 (2012) · Zbl 1251.68171
[19] Tsai, C. H., Linear array and ring embeddings in conditional faulty hypercubes, Theoret. Comput. Sci., 314, 431-443 (2004) · Zbl 1072.68082
[20] Tsai, C. H.; Tan, J. M.; Liang, T.; Hsu, L. H., Fault tolerant hamiltonian laceability of hypercubes, Inform. Process. Lett., 83, 301-306 (2002) · Zbl 1043.68081
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.