Hypohamiltonian Graphs and their Crossing Number

Carol T. Zamfirescu

Abstract


We prove that for every $k \ge 0$ there is an integer $n_0(k)$ such that, for every $n \ge n_0$, there exists a hypohamiltonian graph which has order $n$ and crossing number $k$.

Keywords


Hypohamiltonian graphs; Crossing number

Full Text: PDF