arXiv:2203.10239 Abstract | arXiv Analytics

arXiv:2203.10239 [math.CO]Abstract References Reviews Resources

Plane Triangulations Without Spanning 2-Trees

Published 2022-03-19Version 1

A 2-tree is a graph that can be formed by starting with a triangle and iterating the operation of making a new vertex adjacent to two adjacent vertices of the existing graph. Leizhen Cai asked in 1995 whether every maximal planar graph contains a spanning 2-tree. We answer this question in the negative by constructing an infinite class of maximal planar graphs that have no spanning 2-tree.

Comments: 9 pages

Categories: math.CO

Subjects: 05C10

Keywords: plane triangulations, maximal planar graph contains, leizhen cai, adjacent vertices, vertex adjacent

Related articles: Most relevant | Search more

arXiv:math/0509478 [math.CO] (Published 2005-09-21, updated 2006-04-26)

Simultaneous Diagonal Flips in Plane Triangulations

Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, David R. Wood

arXiv:2107.00424 [math.CO] (Published 2021-07-01)

A note on 1-2-3 and 1-2 Conjectures for 3-regular graphs

Jing-zhi Chang, Chao Yang, Zhi-xiang Yin, Bing Yao

arXiv:1801.07025 [math.CO] (Published 2018-01-22)