##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 843.05056

**Autor: ** Erdös, Paul; Sós, V.T.; Faudree, Ralph J.

**Title: ** The k-spectrum of a graph. (In English)

**Source: ** Alavi, Y. (ed.) et al., Graph theory, combinatorics, algorithms and applications. Vol. 1. Proceedings of the seventh quadrennial international conference on the theory and applications of graphs, Kalamazoo, MI, USA, June 1-5, 1992. New York, NY: Wiley, 377-389 (1995).

**Review: ** The k-spectrum s_{k}(G) of a graph G is the set of integers that occur as the sizes of the induced subgraphs of G of order k. Properties of those sets S\subseteq **{**0, 1, 2,..., \binom{k}{2}**}** that are the k-spectrum s_{k}(G) of some graph G will be investigated. Gap theorems, which indicate the distribution of elements in s_{k}(G), will be proved, and the k-spectra of large order trees will be characterized as the union of two intervals. The number of subsets that are the k-spectrum of a graph will be studied, and extremal problems concerning the k-spectrum will be considered.

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C05 Trees

**Keywords: ** spectrum gap; gap degree; gap theorems; k-spectrum; trees; extremal problems

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag