Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-16T14:58:52.872Z Has data issue: false hasContentIssue false
  • English
  • Français

Triangles in an Ordinary Graph

Published online by Cambridge University Press:  20 November 2018

E. A. Nordhaus  and
B. M. Stewart
E. A. Nordhaus
Affiliation:
Michigan State University
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.

An ordinary graph is a finite linear graph which contains no loops or multiple edges, and in which all edges are undirected. In such a graph G, let N, L, and T denote respectively the number of nodes, edges, and triangles. One problem, suggested by P. Erdös (1), is to determine the minimum number of triangles when the number of edges is specified, subject to suitable restrictions.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 15 , 1963 , pp. 33 - 41
Copyright
Copyright © Canadian Mathematical Society 1963

References

1. Erdôs, Paul and Stone, A. H., On the structure of linear graphs, Bull. Amer. Math. Soc, 52 (1946), 1087–1091.Google Scholar
2. Greenwood, R. E. and Gleason, A. M., Combinatorial relations and chromatic graphs, Can. J. Math., 7 (1955), 1–7.Google Scholar
3. Nordhaus, E. A. and Gaddum, J. W., On complementary graphs, Amer. Math. Monthly, 63 (1956), 176–177.Google Scholar
4. Zykov, A. A., On some properties of linear complexes, Math. Sbornik NS 66 (1949). (Amer. Math. Soc. Translation, No. 79.)Google Scholar