On the hamiltonicity of the Cartesian product. (English) Zbl 1191.68464
Summary: We examine the Hamiltonicity of the Ccartesian product \(P=G_{1}\times G_{2}\) of two graphs \(G_{1}, G_{2}\). We provide necessary and/or sufficient conditions for \(P\) to be Hamiltonian, depending on the Hamiltonian properties of \(G_{1}\) and \(G_{2}\), with corresponding constructions. We also prove a conjecture by Batagelj and Pisanski related to the ‘cyclic Hamiltonicity’ of a graph.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68M10 | Network design and communication in computer systems |
References:
| [1] | Batagelj, V.; Pisanski, T., Hamiltonian cycles in the cartesian product of a tree and a cycle, Discrete Math., 38, 311-312 (1982) · Zbl 0472.05042 |
| [2] | Behzad, M.; Mahmoodian, S. E., On topological invariants of the product of graphs, Canad. Math. Bull., 12, 2, 157-166 (1969) · Zbl 0177.52402 |
| [3] | Bermond, J.-C., Hamiltonian graphs, (Selected Topics in Graph Theory (1978), Academic Press: Academic Press London), 127-167 · Zbl 0429.05052 |
| [4] | Bermond, J.-C.; Gargano, L.; Rescigno, A. A.; Vaccaro, U., Fast gossiping by short messages, SIAM J. Comput., 27, 4, 917-941 (1998) · Zbl 0960.94044 |
| [5] | V.V. Dimakopoulos, On single-port multinode broadcasting, in: IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, vol. I, Victoria, B.C., Canada, 2001, pp. 75-78; V.V. Dimakopoulos, On single-port multinode broadcasting, in: IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, vol. I, Victoria, B.C., Canada, 2001, pp. 75-78 |
| [6] | Gould, R. J., Updating the hamiltonian problem—A survey, J. Graph Theory, 15, 2, 121-157 (1991) · Zbl 0746.05039 |
| [7] | Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064 |
| [8] | Rosenfeld, M.; Barnette, D., Hamiltonian circuits in certain prisms, Discrete Math., 5, 389-394 (1973) · Zbl 0269.05114 |
| [9] | Sabidussi, G., Graphs with given group and given graph-theoretical properties, Canad. J. Math., 9, 515-525 (1957) · Zbl 0079.39202 |
| [10] | Teichert, H.-M., On the cartesian sum of undirected graphs, Elektronische Informationsverabeitung und Kybernetik, 18, 12, 639-646 (1982) · Zbl 0521.05044 |
| [11] | Zaks, J., Hamiltonian cycles in products of graphs, Canad. Math. Bull., 17, 5, 763-765 (1975) · Zbl 0306.05123 |
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.
