Abstract
We prove that every graph of sufficiently large order n and minimum degree at least 2n/3 contains a triangulation as a spanning subgraph. This is best possible: for all integers n, there are graphs of order n and minimum degree [2n/3] - 1 without a spanning triangulation. (c) 2005 Wiley Periodicals, Inc.
| Original language | English |
|---|---|
| Pages (from-to) | 205-233 |
| Number of pages | 29 |
| Journal | Journal of Graph Theory |
| Volume | 49 |
| DOIs | |
| Publication status | Published - 1 Jul 2005 |
Keywords
- triangulations
- extremal graph theory
- planar graphs
- regularity lemma
Fingerprint
Dive into the research topics of 'Spanning triangulations in graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver