All Tight Descriptions of 4-Paths in 3-Polytopes with Minimum Degree 5

详细信息    查看全文

• 作者：Ts. Ch.-D. Batueva ; O. V. Borodin ; A. O. Ivanova
• 关键词：Planar graph ; Plane map ; Structure properties ; 3 ; polytope ; Weight
• 刊名：Graphs and Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：53-62
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Engineering Design;
• 出版者：Springer Japan
• ISSN：1435-5914
• 卷排序：33

文摘

Back in 1922, Franklin proved that every 3-polytope \(P_5\) with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol’ and Madaras (Discuss Math Graph Theory 16:207–217, 1996) ensured a 4-path with the degree sum at most 23. A path \(v_1\ldots v_k\) is a \((d_1,\ldots d_k)\)-path if \(d(v_i)\le d_i\) whenever \(1\le i\le k\). Recently, Borodin and Ivanova proved that every \(P_5\) has a (6, 5, 6, 6)-path or (5, 5, 5, 7)-path, and Ivanova proved the existence of a (5, 6, 6, 6)-path or (5, 5, 5, 7)-path, where both descriptions are tight. The purpose of our paper is to give all tight descriptions of 4-paths in \(P_5\)s.