The total number of stable sets in some classes of trees

• Autorzy: Startek M. , Włoch I.
• Języki publikacji: EN

Abstrakty

EN

A graph representation of the Fibonacci numbers Fn it was given in [3]. They proved that Fn is the number of all stable sets of undirected graph Pn. In [4], [5] authors bounded the number of all maximal stable sets in trees on n vertices. In this paper we determine the number of all stable sets in some kinds of trees. These results are given by the linear recurrence relations containing generalized Fibonacci number.

Słowa kluczowe

EN

undirected graph; Fibonacci numbers; stable sets

PL

graf nieskierowany; liczby Fibonacciego; zbiory stabilne

• Wydawca: Oficyna Wydawnicza Politechniki Rzeszowskiej
• Czasopismo: Zeszyty Naukowe Politechniki Rzeszowskiej. Matematyka
• Rocznik: 2000
• Tom: z. 24 [181]
• Strony: 131--135
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Startek M.

• Department of Mathematics, Technical University of Rzeszów, Poland

autor

Włoch I.

• Department of Mathematics, Technical University of Rzeszów, Poland

Bibliografia

• [1] C. Berge, Principles of combinatorics, Academic Press New York and London 1971.
• [2] F. Harary, Graph Theory, Addison - Wesley, Reading, Mass. 1969.
• [3] H. Prodinger, R. F. Tichy, Fibonacci numbers of graphs, The Fibonacci Quarterly 20, No 1(1982) 16-21.
• [4] B. E. Sagan, A note on independent sets in trees, SIAM J. Alg. Discrete Math. Vol 1, No 1, February (1988) 105-108.
• [5] H. S. Wilf, The number of maximal independent sets in a tree, SIAM J. Alg. Discrete Math. Vol 7, No 1, January (1986) 125-130.