2-edge-Hamiltonian-connectedness of 4-connected plane graphs
2-edge-Hamiltonian-connectedness of 4-connected plane graphs
复制标题
4 连通平面图的 2 边哈密尔顿连通性
DOI：
10.1016/j.ejc.2013.06.033
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
and P. Vrana
中科院分区：
文献类型：
--
作者：
K. Ozeki;and P. Vrana
如果对于任何 X⊂{x 1 x 2: x 1, x 2∈ V (G)} 且 1≤|，图 G 称为 2 边哈密顿连通图。 X|≤ 2，G∪ X 具有包含 X 中所有边的哈密顿环，其中 G∪ X 是将 G 中 X 中的所有边相加得到的图。在本文中，我们证明每个 4 连通平面图都是 2 边哈密尔顿连通的。这个结果在很多意义上都是最好的，也是对 4 连通平面图哈密顿性的几个已知结果的扩展，例如 Tutte 的结果说每个 4 连通平面图都是哈密顿连通的，而 Thomassen 的结果说每个 4 连通平面图都是哈密顿连通的。我们还表明，虽然判定给定图是否是 2 边哈密尔顿连通的问题是 N P 完全的，但如果我们将输入限制为平面图，则存在多项式时间算法来解决该问题。
A graph G is called 2-edge-Hamiltonian-connected if for any X⊂{x 1 x 2: x 1, x 2∈ V (G)} with 1≤| X|≤ 2, G∪ X has a Hamiltonian cycle containing all edges in X, where G∪ X is the graph obtained from G by adding all edges in X. 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 N P-complete, there exists a polynomial time algorithm to solve the problem if we restrict the input to plane graphs.