2-edge-Hamiltonian-connectedness of 4-connected plane graphs

详细信息    查看全文

• 作者：Kenta Ozeki ; Petr Vr¨¢na
• 刊名：European Journal of Combinatorics
• 出版年：2014
• 出版时间：January, 2014
• 年：2014
• 卷：35
• 期：Complete
• 页码：432-448
• 全文大小：654 K

文摘

A graph is called 2-edge-Hamiltonian-connected if for any with , has a Hamiltonian cycle containing all edges in , where is the graph obtained from by adding all edges in . In this paper, we show that every 4-connected plane graph is 2-edge-Hamiltonian-connected. This result is best possible in many senses and an extension of several known results on Hamiltonicity of 4-connected plane graphs, for example, Tutte¡¯s result saying that every 4-connected plane graph is Hamiltonian, and Thomassen¡¯s result saying that every 4-connected plane graph is Hamiltonian-connected. We also show that although the problem of deciding whether a given graph is 2-edge-Hamiltonian-connected is -complete, there exists a polynomial time algorithm to solve the problem if we restrict the input to plane graphs.