Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T06:32:29.376Z Has data issue: false hasContentIssue false

The Slimming Number and Genus of Graphs

Published online by Cambridge University Press:  20 November 2018

Richard K. Guy*
Affiliation:
University of Calgary, Calgary, Alberta
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

J. Ch. Boland suggested, and Mrs. Sheehan named, the idea of the slimming number of a graph G, i.e. the minimum number, s(G), of edges, e 1e 2,…, e s, which must be removed from G in order that G—∪ e i be planar.

For the complete graph, K n (n≥3), it may be seen by Euler's formula that a planar subgraph contains at most 3n—6 edges; moreover one may construct such a subgraph inductively, starting from K 3, and adding points successively, joining them to the three vertices of the region in which they lie, so

1

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1972