Open Access Article
Advances in International Applied Mathematics. 2026; 8: (2) ; 9-14 ; DOI: 10.12208/j.aam.20260011.
A construction of a graph whose every triangulation has degeneracy 5
任意三角剖分的退化度都是5的平面图的构造
作者：
张旺凯 *,
刘文忠
南京航空航天大学数学学院 江苏南京
*通讯作者：
张旺凯,单位：南京航空航天大学数学学院 江苏南京 ；
发布时间: 2026-08-31 总浏览量: 43
PDF 全文下载
引用本文
摘要
Bickle在研究平面图三角剖分的退化度时，提出如下问题：给定整数𝑘,𝑙，是否存在退化度为𝑘的平面图𝐺，使得𝐺的任意三角剖分都有退化度𝑙，其中0≤𝑘≤5，3≤𝑙≤5。对于上述问题，除了(𝑘,𝑙)=(2,5)和(𝑘,𝑙)=(3,5)两种情形外，Bickle确定了其它所有情形。在本文中，我们肯定地回答(3,5)这种情形：证明存在一个3-退化平面图𝐺，使得𝐺的每一个三角剖分的退化度都是5。
关键词： 平面图；三角剖分；退化度
Abstract
When studying the degeneracy of triangulations of plane graphs, Bickle asked whether there exists a plane graph 𝐺 of degeneracy 𝑘 such that every triangulation of 𝐺 has degeneracy 𝑙, where 0≤𝑘≤5 and 3≤𝑙≤5. Except for the cases (𝑘,𝑙)=(2,5) and (𝑘,𝑙)=(3,5), the problem has been completely resolved. In this paper, we answer the case (3, 5) affirmatively. More precisely, we construct a 3-degenerate plane graph 𝐺 and prove that every triangulation of 𝐺 contains a 5-core. Consequently, every triangulation of 𝐺 has degeneracy 5.
Key words： Plane graph; Triangulation; Degeneracy
参考文献 References
[1] Bickle A. Degeneracies of triangulated graphs[J]. Theory and Applications of Graphs, 2025, 12(2): Article 1.
[2] Bickle A. Fundamentals of Graph Theory[M]. Providence, RI: American Mathematical Society, 2020.
[3] Bickle A. Plane triangulations without spanning 2-trees[J]. Australasian Journal of Combinatorics, 2023, 85(1): 82-91.
[4] Bickle A. A survey of maximal k-degenerate graphs and k-trees[J]. Theory and Applications of Graphs, 2024, 0(1): Article 5.
[5] Krisam N D. Maximal k-degenerate spanning subgraphs[D]. Karlsruhe: Karlsruhe Institute of Technology, 2021.
[6] Diestel R. 图论：原书第5版[M]. 于青林, 译. 北京: 科学出版社, 2020.
[7] Lick D R, White A T. k-Degenerate graphs[J]. Canadian Journal of Mathematics, 1970, 22(5): 1082-1096.
[8] Bickle A. The k-Cores of a Graph[D]. Kalamazoo: Western Michigan University, 2010.
引用本文
张旺凯, 刘文忠, 任意三角剖分的退化度都是5的平面图的构造[J]. 国际应用数学进展, 2026; 8: (2) : 9-14.