Andrzej ŻAK

(WMS, AGH)

Multigrafy z maksymaln± liczb± rozkładów hamiltonowskich

Niech $G$ bedzie multigrafem rzedu n dekomponowalnym na k $k \geq 2$, krawedziowo rozacznych cykli Hamiltona. Mówimy wtedy, ze $G$ ma k-zbiór hamiltonowski (jesli k=2, to mówimy, ze $G$ ma pare hamiltonowska). Niech $h_k(G)$ oznacza liczbe róznych k-zbiorów hamiltonowskich multigrafu $G$. Thomasson udowodnił, że jesli $h_2(G) \neq 0$, to $h_2(G) \geq 4$. W referacie zajmiemy sie ograniczeniem górnym na $h_k(G)$. Wykazemy m.in., ze jesli $G$ jest multigrafem rzedu n to $h_k(G)\leq (k!)^{n-1}$, przy czym wartosc maksymalna przyjmowana jest jedynie dla $G=\,^kC_n$.

Bedzie tez niespodzianka - pewien dowód z Ksiegi.

Serdecznie zapraszamy wszystkich chętnych !