| dc.description.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. | |
