Hamilton-connected properties in cartesian product

Document Type : Research Paper


College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, China


In this paper‎, ‎we investigate a problem of finding natural condition‎ ‎to assure the product of two graphs to be hamilton-connected‎. ‎We present some‎ ‎sufficient and necessary conditions for $G\Box H$ being hamilton-connected when $G$ is a‎ ‎hamilton-connected graph and $H$ is a tree or $G$ is a hamiltonian‎ ‎graph and $H$ is $K_2$‎.


Main Subjects

J. A. Bondy and U. S. R. Murty (1976). Graph Theory with Applications. Macmillan, New York. W. S. Chiue and B. S. Shieh (1999). On connectivity of the Cartesian product of two graphs. Appl. Math. Comput.. 102, 129-137 E. Flandrin, H. Li and R. Cada (2006). Hamiltonicity and pancyclicity of generalaized prisms. Discrete Math.. 24, 61-67 R. Gould (2003). Advances on the Hamiltonian Problem -A Survey. Graphs and Combinatorics. 19, 7-52 W. Goddard and M. A. Henning (2001). Pancyclicity of the prism. Discrete Math.. 234, 139-142 P. R. Goodey and M. Rosenfeld (1978). Hamiltonian circuits in prisms over certain simple 3-polytopes. Discrete Math.. 21, 229-235 L.-H. Hsu and C.-K. Lin (2008). Graph Theory and Interconnection Networks. CRC press. T. Kaiser, Z. Ryj\'{a}\v{c}ek, D. Kral, M. Rosenfeld and H. J. Voss (2007). Hamilton Cycle in Prisms. J. Graph Theory. 56, 249-269 M. Lu, H-J. Lai and H. Li (2009). Hamiltonian properties in Cartesian product. Manuscript. K. Ozeki (2009). A degree sum condition for graphs to be prisim Hamiltonian. Discrete Math.. 309, 4266-4299 P. Paulraja (1993). A characterization of hamiltonian prisms. J. Graph Theory. 17, 161-171 M. Rosenfeld and D. Barnette (1973). Hamiltonian circuits in certain prisms. Discrete Math.. 5, 389-394
Volume 1, Issue 3 - Serial Number 3
September 2012
Pages 11-19
  • Receive Date: 01 June 2012
  • Revise Date: 04 October 2012
  • Accept Date: 04 October 2012
  • Published Online: 01 September 2012