Hostname: page-component-848d4c4894-m9kch Total loading time: 0 Render date: 2024-05-06T06:58:40.791Z Has data issue: false hasContentIssue false
  • English
  • Français

The Thickness of the Complete Graph

Published online by Cambridge University Press:  20 November 2018

Lowell W. Beineke  and
Frank Harary
Lowell W. Beineke
Affiliation:
The University of Michigan
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 consists of a finite set of p points and q lines joining pairs of these points. Each line joins two distinct points and no pair of points is joined by more than one line. A subgraph of G is a graph whose points and lines are also in G. If every pair of points of a graph is joined by a line, the graph is called complete and is denoted by Kp. A planar graph can be embedded in the plane, that is, drawn in the plane in such a way that none of its lines intersect.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 17 , 1965 , pp. 850 - 859
Copyright
Copyright © Canadian Mathematical Society 1965

References

1. Battle, J., Harary, F., and Kodama, Y., Every planar graph with nine points has a nonplanar complément, Bull. Amer. Math. Soc, 68 (1962), 569–571.Google Scholar
2. Beineke, L. W. and Harary, F., On the thickness of the complete graph. Bull. Amer. Math. Soc, 70 (1964), 618–620.Google Scholar
3. Beineke, L. W. and Harary, F., Some inequalities involving the genus of a graph and its thicknesses, Proc. Glasgow Math. Assoc, 7 (1965), 19–21.Google Scholar
4. Harary, F., Recent results in topological graph theory, Acta Math. Acad. Sci. Hungar., 15 (1964), 405–412.Google Scholar
5. Kuratowski, C., Sur le problème des courbes gauches en topologie, Fund. Math., 15 (1930), 271–283.Google Scholar
6. Tutte, W. T., The nonbiplanar character of the complete 9-graph, Can. Math. Bull., 6 (1963), 319–330.Google Scholar
7. Tutte, W. T., The thickness of a graph, Indag. Math., 25 (1963), 561–577.Google Scholar
8. Ringel, G., Die toroidale Dicke des vollstdndigen Graphen, Math. Z., 87 (1965), 19–26.Google Scholar