Fibonacci numbers of trees

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

Abstrakty

EN

In [6] it was presented a graph-representation of the Fibonacci numbers Fn and Lucas numbers Ln. It is interesting to know that they are the totał numbers of independent sets of undirected graphs Pn and Cn, respectively. More general concept of the number of all k-independent sets of graphs Pn and Cn was discussed in [5]. In [6], [7] it was bounded the number of all independent sets of a tree Tn. In this paper we propose the method which estimate the number Fk(Tn) of all k-independent sets of Tn. We also describe graphs G for which the numbers Fk(G) are the generalizations of the Fibonacci numbers.

Słowa kluczowe

EN

k-independent set; Fibonacci numbers; trees; graphs

PL

zbiory k-niezależne; liczby Fibonacciego; drzewo; grafy

• Wydawca: Oficyna Wydawnicza Politechniki Rzeszowskiej
• Czasopismo: Journal of Mathematics and Applications
• Rocznik: 2006
• Tom: Vol. 28
• Strony: 137--145
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Startek M.

autor

Włoch A.

autor

Włoch I.

• Department of Mathematics Rzeszów University of Technology ul. W. Pola 2, 35-359 Rzeszów, Poland

Bibliografia

• [1] C. Berge, Principles of combinatorics, Academic Press new York and London 1971.
• [2] G. H. Fricke, S. T. Hedetniemi, M. A. Honning, Distance. independent domination of graphs, Ars Combinatoria 41(1995), 34-44.
• [3] F. Harrary, Graph Theory, Addison Wesley, Reading, Mass. 1969.
• [4] G. Hopkins, W. Staton, Some idenities arising from The Fibonacci numbers of certains graphs, The Fibonacci Quarterly (1984), 225-228.
• [5] M. Kwaśnik, I. Włoch, The total number of generalized stable sets and kernels of graphs, Ars Combinatoria, 55(2000), 139-146.
• [6] H. Prodinger, R. F. Tichy, Fibonacci numbers of graphs, The Fibonacci Quarterly 20 (1982) 16-21.
• [7] B. E. Sagan, A note on independent sets in a tree, SIAM J. Alg. Discrete Math. Vol 1, No 1, February (1988), 105-108.
• [8] M. Startek, I. Włoch, The number of all stable sets in some classes of graphs, Folia Scient. Univ. Tech. Res. 175(23) (1999), 117-123.
• [9] M. Startek, I, Włoch, The total number of stable sets in some classes of trees, Folia Scient. Univ. Tech. Res. 181(24) (2000), 131-135.
• [10] H. S. Wilf, The number of maximal independent sets in a tree, SIAM J.Alg. Discrcte Math. Vol 7, No 1, January (1986), 125-130.
• [11] A. Włoch, I. Włoch, On (k,l)-kernels in generatized products of graphs, Discrete Math. 164(1996), 295-301.
• [12] I. Włoch, Generalized Fibonacci polynomial of graph, Ars Combinatoria 68 (2003), 49-55.