$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

We wtorek, 18 maja 2004 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Iwona WŁOCH

(Politechnika Rzeszowska)

wygłosi referat pod tytułem:

Uogólnione liczby i wielomiany Fibonacciego

grafów i ich produktów

Zbiór $S \subseteq V(G)$ nazywamy zbiorem niezależnym grafu $G$ jeżeli dowolne dwa wierzchołki ze zbioru $S$ nie są sąsiednie. Ponadto każdy podzbiór jednoelementowy zbioru $V(G)$ oraz zbiór pusty jest zbiorem niezależnym grafu $G$. Niech $X=\{1,2,...,n\}$ i $f(n,p)$ oznacza liczbę wszystkich $p$-elementowych podzbiorów zbioru $X$ takich, że żadne dwie liczby nie są sąsiednie. Liczbę $F_n=\sum\limits_{p\geq 0} f(n,p)$ nazywamy liczbą Fibonacciego. W interpretacji grafowej liczba Fibonacciego jest równa liczbie wszystkich zbiorów niezależnych grafu $P_n$. Ogólnie, liczbę wszystkich zbiorów niezależnych grafu $G$ nazywamy liczbą Fibonacciego grafu $G$ i oznaczamy $F(G)$. W referacie zostaną przedstawione rezultaty dotyczące liczby wszystkich zbiorów $k$-niezależnych, $k\geq 2$, w grafach i ich produktach. Liczby te są wyrażane za pomocą uogólnionych liczb Fibonacciego i wielomianu Fibonacciego.

Literatura:
[1] G. Hopkins, W. Staton, Some idenities arising from The Fibonacci numbers of certains graphs, The Fibonacci Quarterly (1984), 225-228. >
[2] M. Kwaśnik, I. Włoch, The total number of generalized stable sets and kernels of graphs, Ars Combinatoria, 55(2000), 139-146.
[3] H. Prodinger, R.F. Tichy, Fibonacci numbers of graphs, The Fibonacci Quarterly 20, (1982) 16-21.
[4] I. Włoch, Generalized Fibonacci polynomial of graph, Ars Combinatoria 68, (2003), 49-55.

Serdecznie zapraszamy wszystkich chętnych !