×

zbMATH — the first resource for mathematics

The Hamiltonian properties of supergrid graphs. (English) Zbl 1330.05093
Summary: In this paper, we first introduce a novel class of graphs, namely supergrid. Supergrid graphs include grid graphs and triangular grid graphs as their subgraphs. The Hamiltonian cycle and path problems for grid graphs and triangular grid graphs were known to be NP-complete. However, they are unknown for supergrid graphs. The Hamiltonian cycle (path) problem on supergrid graphs can be applied to control the stitching traces of computerized sewing machines. In this paper, we will prove that the Hamiltonian cycle problem for supergrid graphs is NP-complete. It is easily derived from the Hamiltonian cycle result that the Hamiltonian path problem on supergrid graphs is also NP-complete. We then show that two subclasses of supergrid graphs, including rectangular (parallelism) and alphabet, always contain Hamiltonian cycles.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ascheuer, N., Hamiltonian path problems in the on-line optimization of flexible manufacturing systems, (1996), Konrad-Zuse-Zentrum für Informationstechnik Berlin, technique report TR 96-3
[2] Bermond, J. C., Hamiltonian graphs, (Beinke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, (1978), Academic Press New York) · Zbl 0429.05052
[3] Bertossi, A. A.; Bonuccelli, M. A., Hamiltonian circuits in interval graph generalizations, Inform. Process. Lett., 23, 195-200, (1986) · Zbl 0627.68056
[4] Bondy, J. A.; Murty, U. S.R., Graph theory, (2008), Springer New York · Zbl 1134.05001
[5] Bouchemakh, I.; Zemir, M., On the broadcast independence number of grid graph, Graphs Combin., 30, 83-100, (2014) · Zbl 1295.05173
[6] Chen, S. D.; Shen, H.; Topor, R., An efficient algorithm for constructing Hamiltonian paths in meshes, Parallel Comput., 28, 1293-1305, (2002) · Zbl 0999.68253
[7] Cheng, C. W.; Lee, C. W.; Hsieh, S. Y., Conditional edge-fault Hamiltonicity of Cartesian product graphs, IEEE Trans. Parallel Distrib. Syst., 24, 10, 1951-1960, (2013)
[8] Damaschke, P., The Hamiltonian circuit problem for circle graphs is NP-complete, Inform. Process. Lett., 32, 1-2, (1989) · Zbl 0681.68062
[9] Dettlaff, M.; Lemańskaa, M.; Yero, I. G., Bondage number of grid graphs, Discrete Appl. Math., 167, 94-99, (2014) · Zbl 1284.05195
[10] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[11] Golumbic, M. C., Algorithmic graph theory and perfect graphs, Annals of Discrete Mathematics, vol. 57, (2004), Elsevier · Zbl 1050.05002
[12] Gordon, V. S.; Orlovich, Y. L.; Werner, F., Hamiltonian properties of triangular grid graphs, Discrete Math., 308, 6166-6188, (2008) · Zbl 1158.05040
[13] Gravier, S., Total domination number of grid graphs, Discrete Appl. Math., 121, 119-128, (2002) · Zbl 0995.05109
[14] Grebinski, V.; Kucherov, G., Reconstructing a Hamiltonian cycle by querying the graph: application to DNA physical mapping, Discrete Appl. Math., 88, 147-165, (1998) · Zbl 0936.68107
[15] Hsieh, S. Y.; Cian, Y. R., Conditional edge-fault Hamiltonicity of augmented cubes, Inform. Sci., 180, 13, 2596-2617, (2010) · Zbl 1209.68375
[16] Hsieh, S. Y.; Wu, C. Y., Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults, J. Comb. Optim., 19, 1, 16-30, (2010) · Zbl 1185.90029
[17] Hu, F. T.; Lu, Y.; Xu, J. M., The total bondage number of grid graphs, Discrete Appl. Math., 160, 2408-2418, (2012) · Zbl 1252.05163
[18] Islam, K.; Meijer, H.; Núũez, Y.; Rappaport, D.; Xiao, H., Hamiltonian cycles in hexagonal grid graphs, (Proceedings of the 19th Canadian Conference on Computational Geometry, CCCG’97, (2007)), 85-88
[19] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 4, 676-686, (1982) · Zbl 0506.05043
[20] Johnson, D. S., The NP-complete column: an ongoing guide, J. Algorithms, 6, 434-451, (1985) · Zbl 0608.68032
[21] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in some classes of grid graphs, J. Appl. Math., 2012, (1982)
[22] Keshavarz-Kohjerdi, F.; Bagheri, A.; Asgharian-Sardroud, A., A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math., 160, 210-217, (2012) · Zbl 1237.05115
[23] Krishnamoorthy, M. S., An NP-hard problem in bipartite graphs, SIGACT News, 7, 26, (1976)
[24] Lee, C. W.; Lin, T. J.; Hsieh, S. Y., Hamiltonicity of product networks with faulty elements, IEEE Trans. Parallel Distrib. Syst., 25, 9, 2318-2331, (2014)
[25] Lenhart, W.; Umans, C., Hamiltonian cycles in solid grid graphs, (Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS’97, (1997)), 496-505
[26] Luccio, F.; Mugnia, C., Hamiltonian paths on a rectangular chessboard, (Proceedings of the 16th Annual Allerton Conference, (1978)), 161-173
[27] Marx, D., Eulerian disjoint paths problem in grid graphs is NP-complete, Discrete Appl. Math., 143, 336-341, (2004) · Zbl 1053.05078
[28] Menke, B.; Zamfirescu, T.; Zamfirescu, C., Intersections of longest cycles in grid graphs, J. Graph Theory, 25, 37-52, (1997) · Zbl 0874.05032
[29] Muthammai, S.; Vidhya, P., Total complementary tree domination in grid graphs, Int. J. Math. Soft Comput., 3, 107-114, (2013)
[30] O’Callaghan, J. F., Computing the perceptual boundaries of dot patterns, Comput. Graph. Image Process., 3, 141-162, (1974)
[31] Preperata, F. P.; Shamos, M. I., Computational geometry: an introduction, (1985), Springer New York
[32] Reay, J. R.; Zamfirescu, T., Hamiltonian cycles in T-graphs, Discrete Comput. Geom., 24, 497-502, (2000) · Zbl 0953.05040
[33] Salman, A. N.M., Contributions to graph theory, (2005), University of Twente, Ph.D. thesis
[34] Toussaint, G. T., Pattern recognition and geometrical complexity, (Proceedings of the 5th International Conference on Pattern Recognition, Miami Beach, (1980)), 1324-1347
[35] Zamfirescu, C.; Zamfirescu, T., Hamiltonian properties of grid graphs, SIAM J. Discrete Math., 5, 4, 564-570, (1992) · Zbl 0770.05073
[36] Zhang, W. Q.; Liu, Y. J., Approximating the longest paths in grid graphs, Theoret. Comput. Sci., 412, 5340-5350, (2011) · Zbl 1222.68089
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.