Hamiltonicity and pancyclicity of cartesian products of graphs |
| |
Authors: | Roman ?ada Evelyne Flandrin |
| |
Affiliation: | a Department of Mathematics, University of West Bohemia, Pilsen, Czech Republic b Institute for Theoretical Computer Science, Charles University, Pilsen, Czech Republic c L.R.I., Université Paris-Sud, Orsay, France d School of Mathematics and Statistics, Lanzhou University, LanZhou, GanSu, China |
| |
Abstract: | The cartesian product of a graph G with K2 is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g′(H) and Δ(H)≤g′(G) (we denote by g′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian. |
| |
Keywords: | Prism Hamiltonicity Pancyclicity Factorization Cartesian product |
本文献已被 ScienceDirect 等数据库收录! |
|