Spanning triangulations in graphs

Research output: Contribution to journalArticle

10 Citations (Scopus)

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 languageEnglish
Pages (from-to)205-233
Number of pages29
JournalJournal of Graph Theory
Volume49
DOIs
Publication statusPublished - 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