Plane triangulations without large 2-trees
In 1995 Leizhen Cai asked whether each plane triangulation has a spanning 2-tree. This question was recently answered in the negative by Bickle. He gave a plane triangulation on 38 vertices for which each 2-tree contained in it misses at least one vertex. We give a smaller example on 29 vertices and show that for each c>0 there are plane triangulations P=(V,E), so that each 2-tree that is a subgraph of P contains fewer than c|V| vertices. We also give a lower bound for the size of a maximum 2-tree in plane triangulations by proving that each plane triangulation P=(V,E) contains a 2-tree on at least log_2 (|V|-1)+4 -log_2 3 vertices. Finally we give structural criteria based on the decomposition trees of Jackson and Yu that guarantee the existence of spanning 2-trees in plane triangulations.The results are proven by using the close relation of 2-trees to hamiltonian cycles and to induced trees in the dual for plane triangulations without separating triangles.
Authors
- Allan Bickle (ORCID: https://orcid.org/0000-0002-7739-607X)
- Gunnar Brinkmann
Institutions
- Purdue University West Lafayette (US)
- Ghent University Hospital (BE)
Publication Details
- Journal
- Ars Mathematica Contemporanea
- Published
- 2024-12-13
- DOI
- https://doi.org/10.26493/1855-3974.3066.5bf
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00