Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-11T07:03:43.921Z Has data issue: false hasContentIssue false
  • English
  • Français

A Remark on the Number of Complete and Empty Subgraphs

Published online by Cambridge University Press:  01 June 1998

RICHARD H. SCHELP  and
ANDREW THOMASON
RICHARD H. SCHELP
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA (e-mail: schelpr@msci.memphis.edu)
ANDREW THOMASON
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA (e-mail: schelpr@msci.memphis.edu) Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, UK (e-mail: A.G.Thomason@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

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.

Let kp(G) denote the number of complete subgraphs of order p in the graph G. Bollobás proved that any real linear combination of the form [sum ]apkp(G) attains its maximum on a complete multipartite graph. We show that the same is true for a linear combination of the form [sum ]apkp(G) +bpkp(G¯), provided bp[ges ]0 for every p.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 7 , Issue 2 , June 1998 , pp. 217 - 219
Copyright
1998 Cambridge University Press