Hamilton-connected properties in cartesian product

Document Type: Research Paper

Authors

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

Abstract

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$‎.

Keywords

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