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 sk(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 sk(G) of some graph G will be investigated. Gap theorems, which indicate the distribution of elements in sk(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