Every Triangulated 3-Polytope of Minimum Degree 4 has a 4-Path of Weight at Most 27

[摘要] By $\delta$ and $w_k$ denote the minimum degree and minimum degree-sum (weight) of a $k$-vertex path in a given graph, respectively. For every 3-polytope, $w_2\le13$ (Kotzig, 1955) and $w_3\le21$ (Ando, Iwasaki, Kaneko, 1993), where both bounds are sharp.

[学科分类] 离散数学和组合数学

[关键词] Plane graph;Structural property;Normal plane map;4-Path