Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T20:51:11.161Z Has data issue: false hasContentIssue false
  • English
  • Français

On Subgraphs of the Complete Bipartite Graph

Published online by Cambridge University Press:  20 November 2018

P. Erdös  and
J. W. Moon
P. Erdös
Affiliation:
University College, London
J. W. Moon
Affiliation:
University College, London
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.

G(n) denotes a graph of n vertices and Ḡ(n) denotes its complementary graph. In a complete graph every two distinct vertices are joined by an edge. Let Ck(G(n)) denote the number of complete subgraphs of k vertices contained in G(n). Recently it was proved [1] that for every k

1

where the minimum is over all graphs G(n).

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 7 , Issue 1 , March 1964 , pp. 35 - 39
Copyright
Copyright © Canadian Mathematical Society 1964

References

1. Erdös, P., On the number of complete subgraphs contained in certain graphs, Publ. Math. Inst. Hung. Acad. Sci. 7 (1962), 459–464.Google Scholar
2. Goodman, A.W., On sets of acquaintances and strangers at any party, Amer. Math. Monthly, 66 (1959) 778–783.Google Scholar
3. Lorden, G., Blue-empty chromatic graphs, Amer. Math. Monthly, 69 (1962) 114–120.Google Scholar
4. Moon, J.W. and Moser, L., On chromatic bipartite graphs, Math. Mag. 35 (1962) 225–227.Google Scholar
5. Sauvé, L., On chromatic graphs, Amer. Math. Monthly, 68 (1961) 107–111.Google Scholar