Hamilton-connected properties in cartesian product

Hoshur, Rushengul; Vumar, Elkin

Home Article Information

Hamilton-connected properties in cartesian product

Article 3, Volume 1, Issue 3, September 2012, Page 11-19 PDF (445 K)

Document Type: Research Paper

Authors

Rushengul Hoshur; Elkin Vumar

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

Cartesian product; Hamilton-connectedness; Hamilton cycle; Hamilton path

Main Subjects

05C38 Paths and cycles; 05C45 Eulerian and Hamiltonian graphs

References

1	J. A. Bondy and U. S. R. Murty (1976). Graph Theory with Applications. Macmillan, New York.
2	W. S. Chiue and B. S. Shieh (1999). On connectivity of the Cartesian product of two graphs. Appl. Math. Comput.. 102, 129-137
3	E. Flandrin, H. Li and R. Cada (2006). Hamiltonicity and pancyclicity of generalaized prisms. Discrete Math.. 24, 61-67
4	R. Gould (2003). Advances on the Hamiltonian Problem -A Survey. Graphs and Combinatorics. 19, 7-52
5	W. Goddard and M. A. Henning (2001). Pancyclicity of the prism. Discrete Math.. 234, 139-142
6	P. R. Goodey and M. Rosenfeld (1978). Hamiltonian circuits in prisms over certain simple 3-polytopes. Discrete Math.. 21, 229-235
7	L.-H. Hsu and C.-K. Lin (2008). Graph Theory and Interconnection Networks. CRC press.
8	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
9	M. Lu, H-J. Lai and H. Li (2009). Hamiltonian properties in Cartesian product. Manuscript.
10	K. Ozeki (2009). A degree sum condition for graphs to be prisim Hamiltonian. Discrete Math.. 309, 4266-4299
11	P. Paulraja (1993). A characterization of hamiltonian prisms. J. Graph Theory. 17, 161-171
12	M. Rosenfeld and D. Barnette (1973). Hamiltonian circuits in certain prisms. Discrete Math.. 5, 389-394

Statistics

Article View: 3,304

PDF Download: 2,937