Prism-Hamiltonicity and Hamiltonicity of Graph Products

Abstract

The prism over a graph G is the cartesian product of G with K2, i.e., the graph obtained by taking two copies of G and adding a perfect matching joining the two copies of each vertex by an edge. The graph G is called prism-Hamiltonian if it has a Hamiltonian prism. It is known that the property of having a Hamiltonian prism (prism-Hamiltonicity) is stronger than that of having a spanning 2-walk (closed walk using every vertex at most twice) and weaker than that of having a Hamilton path. In this dissertation we study different problems related to prism-Hamiltonicity of graphs and the Hamiltonicity of other graph products. We answer D. West’s question of finding a Chv´atal-Erd}os condition for prism-Hamiltonicity, i.e., a bound on independence number in terms of connectivity, guaranteeing prism-Hamiltonicity. We also find the Chv´atal-Erd}os condition for Hamiltonicity of the cartesian product of G with K3. Moreover, we show that for the class of P4-free graphs, the three properties of being prism-Hamiltonian, having a spanning 2-walk, and being 1/2-tough are all equivalent. Finally, we characterize the forbidden subgraphs and forbidden pairs that imply prism-Hamiltonicity.