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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page