Séminaire Lotharingien de Combinatoire, B19g (1988), 1 p.
[Formerly: Publ. I.R.M.A. Strasbourg, 1988, 361/S-19, p. 134.]

Robert Tichy

Graphentheoretische Abzählprobleme

1. Bestimmung der Anzahl t(C²_n) der spannenden Bäume im Quadrat C²_n eines Kreises C² der Länge n (cf. Th Fibonacci Quart. 23 (1985), 258-264, gemeinsam mit G. Baron, T. Boesch, H. Prodinger and J. F. Wang).

Ein rein kombinatorischer Beweis (etwas umfangreicher) der Formel t(C²_n) = nF²_n (F_n ... Fibonaccizahlen) wurde von D. J. Kleitman and B. Golden (Amer. Math. Monthly (1975), 40-44) gegeben. Es wird ein einfacher Beweis mit Hilfe des Kirchhoffschen Matrix-Baum-Satzes vorgestellt.

2. Explizite und asymptotische Bestimmung der Anzahl unabhäbhängiger Knotenmengen im vollständigen t-ären Baum der Höhe n. Für den Weg der Länge n (d.h. t=1) ergibt sich F_n+1 für die Anzahl.

3. Mittlere Anzahl unabhängiger Knotenmengen in der Familie der t-ären Bäume mit n inneren Knoten.

Literatur zu 2., 3.: P. Kirschenhofer, H. Prodinger und R. F. Tichy, in: Fibonacci-Numbers and Their Applications, D. Reidel, Dordrecht, 1986.