4-connected projective-planar graphs are Hamiltonian-connected
4-connected projective-planar graphs are Hamiltonian-connected
复制标题
DOI：
10.1016/j.jctb.2014.11.006
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
K. Kawarabayashi;K. Ozeki
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi;K. Ozeki
We generalize the following two seminal results.(1) Thomassen's result [15] in 1983, which says that every 4-connected planar graph is Hamiltonian-connected (which generalizes the old result of Tutte [16] in 1956, which says that every 4-connected planar graph is Hamiltonian).(2) Thomas and Yu's result [12] in 1994, which says that every 4-connected projective-planar graph is Hamiltonian. Here, Hamiltonian-connected means that for any two vertices u, v, there is a Hamiltonian path between u and v (and hence this generalizes the existence of Hamiltonian cycles). Specifically, we prove the following; Every 4-connected projective-planar graph is Hamiltonian-connected. This proves a conjecture of Dean [3] in 1990. Our result is best possible in many senses. First, we cannot lower the connectivity 4. Secondly, we cannot generalize our result to a surface with higher genus (that is, there is a 4-connected graph on the torus or on the Klein bottle which is not Hamiltonian-connected). Our proof is constructive in a sense that there is a polynomial time algorithm to find, given two vertices in a 4-connected projective-planar graph, a Hamiltonian path between these two vertices.
