Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-28T01:32:45.458Z Has data issue: false hasContentIssue false
  • English
  • Français

On Independent Complete Subgraphs in a Graph

Published online by Cambridge University Press:  20 November 2018

J. W. Moon
J. W. Moon*
Affiliation:
University of Alberta, Edmonton, Alberta
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 = G(n, e) consists of a set of n nodes e pairs of which are joined by a single edge; we assume that no edge joins a node to itself. A graph with modes is called a complete -graph if each pair of its nodes is joined by an edge. The graphs belonging to some collection of graphs are independent if no two of them have a node in common. The maximum number of independent complete -graphs contained in a given graph G will be denoted by Ik(G).

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 20 , 1968 , pp. 95 - 102
Copyright
Copyright © Canadian Mathematical Society 1968

References

1. Erdös, P., Über ein Extremalproblem in der Graphentheorie, Arch. Math., 13 (1962), 222–227.Google Scholar
2. Erdös, P. and Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar., 10 (1959), 337–356.Google Scholar
3. Erdös, P. and Pόsa, L., On the maximal number of disjoint circuits in a graph, Publ. Math. Debrecen, 9 (1962), 3–12.Google Scholar
4. Fulkerson, D. R. and Shapley, L. S., Minimal k-arc-connected graphs, The RAND Corp., P-2371 (1961), 1–11.Google Scholar
5. Turán, P., On the theory of graphs, Colloq. Math., 3 (1954), 19–30.Google Scholar