Publication at Faculty of Mathematics and Physics |
2004
Abstract
We study noncrossing Hamiltonian paths in geometric graphs. We establish that after the removal of $\Omega(\sqrt{n})$ edges from the complete graph the Hamiltonian path still exists.
We also prove bounds for the removal of a complete graph and a star.