I m folgenden sei mit r stets ein endlicher, schlichter und zusammenhangender Graph i ) bezeichnet.
Zur Gewinnung von Aussagen uber Graphen r kann man so vorgehen, da13 man eine gewisse ,,Grundeigenschaft" E von r vorgibt und nach weiteren Eigenschaften E, fragt. Man erhalt auf diese Weise Aussagen von der Form: Besitzt der Graph r die Eigenschaft E , so kommen r auch die Eigenschaften Ei zu.
Als ,,Grundeigenschaft" eines Graphen r sei im folgenden der Kompositionsgrad c ( r ) vorgegeben, welcher sich auf die ,,Zusammensetzung" eines Graphen r aus besonders ,,einfachen" Graphen bezieht. Definition 1. Unter dem Kornpositionsgrad c ( r ) eines Graphen I' sei die kleinste unter den naturlichen Zahlen z verstanden, fur welche r eine Darstellung 2 r = U B , i-1 als Vereinigung geeigneter Baume B, 5 I' zuliiBt. Ein n-komponierburer Graph I' sei ein Graph T mit c ( r ) = n. Fur eine beliebige Graphenfunktion cp stellt sich jetzt die Frage : Wie groB ist q(T) fur einen Graphen I ' , wenn der Kompositionsgrad c ( r ) von r vorgegeben wird? Es zeigt sich, da13 man dazu fur eine Reihe von Graphenfunktionen v obere Schranken fur y ( r ) als Funktion von c ( r ) herleiten kann. Zur geeigneten Formulierung dieser Ergebnisse wird der Hegriff der Kompositionsklassenzahl eingefuhrt. Definition 2. Die Klasse aller Graphen Tvom Kompositionsgrad c ( r ) = c moge als Kompositionsklusse re bezeichnet werden. Fur eine Graphenfunktion qj sei dann unter der Kompoaitionsklussenzahl v( re) eine reelle Zahl verstanden , welche durch gegeben wird. 1) Die Definition aller in der vorliegenden Arbeit verwendeten und nicht niiher definierten graphentheoretischen Begriffe findet man bei K. WAGNER [l].