Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-28T23:25:03.131Z Has data issue: false hasContentIssue false
  • English
  • Français

The Construction of Certain Graphs

Published online by Cambridge University Press:  20 November 2018

P. Erdös  and
C. A. Rogers
P. Erdös
Affiliation:
University College London
C. A. Rogers
Affiliation:
University of Toronto
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.

A graph G is called complete if any two of its vertices are connected by an edge; a set of vertices of G are said to be independent if no two of them are connected by an edge. It follows from a well-known theorem of Ramsay (1) that for each pair of positive integers k, l there is an integer f(k, l), which we take to be minimal, such that every graph with f(k, l) vertices either contains a complete graph of k vertices or a set of l independent points.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 14 , 1962 , pp. 702 - 707
Copyright
Copyright © Canadian Mathematical Society 1962

References

1. Ramsay, F. P., On a problem of formal logic, Proc. London Math. Soc. (2), 30 (1930), 264–286.Google Scholar
2. Erdös, P. and Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2 (1935), 463–470.Google Scholar
3. Erdös, P., Some remarks on the theory of graphs, Bull. Amer. Math. Soc, 53 (1947), 292–294.Google Scholar
4. Erdös, P., Remarks on a theorem of Ramsay, Bull. Research Council Israel, 7 (1957), 21–24.Google Scholar
5. Schmidt, E., Die Brunn-Minkowski Ungleichung und ihr Spiegelbild sowie die isoperimetrische Eigenschaft der Kugel in der euklidischen und nichteuklidischen Géométrie I, Math. Nach. Berlin, 1 (1948), 81–157.Google Scholar
6. Erdös, P. and Rogers, C. A., Covering space with convex bodies, Acta Arithmetica 7 (1962), 281–285.Google Scholar