Premium
Spanning triangulations in graphs
Author(s) -
Kühn Daniela,
Osthus Deryk
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20076
Subject(s) - combinatorics , mathematics , discrete mathematics , triangulation , degree (music) , graph , geometry , physics , acoustics
We prove that every graph of sufficiently large order n and minimum degree at least 2 n /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 ⌈2 n /3⌉ − 1 without a spanning triangulation. © 2005 Wiley Periodicals, Inc. J Graph Theory
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom