首页 | 本学科首页   官方微博 | 高级检索  
     


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 GH is hamiltonian.
Keywords:Prism   Hamiltonicity   Pancyclicity   Factorization   Cartesian product
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号