✦ LIBER ✦

Trees in Triangulations

✍ Scribed by C. Thomassen

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 338 KB
Volume: 60
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1005

No coin nor oath required. For personal study only.

✦ Synopsis

Every triangulation of the orientable surface of genus (g) with no noncontractible cycle of length less than (2^{3 \mathrm{p}+4}) contains a spanning tree of maximum degree at most four. 1994 Academic Press, Inc

📜 SIMILAR VOLUMES

Spanning triangulations in graphs

✍ Daniela Kühn; Deryk Osthus 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 467 KB

## Abstract 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 triangul

Hamilton cycles in plane triangulations

✍ Bill Jackson; Xingxing Yu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

## Abstract We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation __G__ into 4‐connected ‘pieces,’ and show that if each piece shares a triangle

Colouring Eulerian Triangulations

✍ Joan Hutchinson; R.Bruce Richter; Paul Seymour 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 125 KB

We show that for every orientable surface S there is a number c so that every Eulerian triangulation of S with representativeness \ c is 4-colourable.

Simultaneous diagonal flips in plane tri

Simultaneous diagonal flips in plane triangulations

✍ Prosenjit Bose; Jurek Czyzowicz; Zhicheng Gao; Pat Morin; David R. Wood 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 468 KB

## Abstract Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with __n__ ≥ 6 vertices has a simultaneous flip into a 4‐connected triangulation, and that the set of edges to be flipped can be computed in $\cal O$(__n__) time. It follows that

Dominating sets in triangulations on sur

Dominating sets in triangulations on surfaces

✍ Tatsuya Honjo; Ken-ichi Kawarabayashi; Atsuhiro Nakamoto 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB 👁 1 views

## Abstract Let __G__ be a graph and let __S__⊂__V__(__G__). We say that __S__ is __dominating__ in __G__ if each vertex of __G__ is in __S__ or adjacent to a vertex in __S__. We show that every triangulation on the torus and the Klein bottle with __n__ vertices has a dominating set of cardinality

Quasi-Greedy Triangulations Approximatin

Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation

✍ Christos Levcopoulos; Drago Krznaric 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 334 KB