Article contents
An extremal problem in graph theory
Published online by Cambridge University Press: 09 April 2009
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.
G(n;l) will denote a graph of n vertices and l edges. Let f0(n, k) be the smallest integer such that there is a G (n;f0(n, k)) in which for every set of k vertices there is a vertex joined to each of these. Thus for example fo = 3 since in a triangle each pair of vertices is joined to a third. It can readily be checked that fo = 5 (the extremal graph consists of a complete 4-gon with one edge removed). In general we will prove: Let n > k, andthen f0(n, k) = f(n, k).
- Type
- Research Article
- Information
- Copyright
- Copyright © Australian Mathematical Society 1970
You have
Access
- 8
- Cited by