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

We wtorek, 6 grudnia 2005 roku, o godzinie 12:45

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

Jakub PRZYBYŁO

(WMS)

wygłosi referat pod tytułem:

Dowolne rozkłady na drogi zamknięte.

Pseudografy

Ciąg $\tau=(t_1,\ldots,t_p)$ liczb naturalnych większych od dwójki nazywamy dopuszczalnym dla grafu (pseudografu) $G$, jeżeli $\sum\limits_{i=1}^p t_i=\vert\vert G\vert\vert$. Jeżeli ponadto istnieje krawędziowo-rozłączny rozkład $G$ na drogi zamknięte $T_1,\ldots,T_p$ długości odpowiednio $t_1,\ldots,t_p$, to ciąg $\tau$ nazywamy $G$-realizowalnym.
P.N. Balister udowodnił, że dowolny ciąg dopuszczalny jest jednocześnie realizowalny w grafach pełnych $K_n$.
Celem referatu jest przedstawienie analogicznego wyniku dla pseudografów $L_n$ o $n$ - parzystym, czyli grafów pełnych z usuniętym pełnym skojarzeniem oraz dołączoną pojedynczą pętlą w każdym wierzchołku, przy założeniu, że ciąg $\tau$ składa się wyłącznie z liczb parzystych. Zostanie także przedstawiony związek tego wyniku z krawędziowym kolorowaniem grafów dwuregularnych rozróżniającym wierzchołki.

Serdecznie zapraszamy wszystkich chętnych!