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

We wtorek, 28 lutego 2006 roku, o godzinie 12:45

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

Antoni MARCZYK

(WMS AGH)

wygłosi referat pod tytułem:

Warunek typu Orego dla dowolnej podzielności

Graf $G$ jest dowolnie podzielny, jeśli dla dowolnego ciągu $(a_1,\ldots,a_k)$ liczb naturalnych dających w sumie rząd grafu można znale14ć podział $(V_1,\ldots,V_k)$ zbioru jego wierzchołków taki, że dla każdego $j\in\{1,\ldots,k\}$ $V_j$ indukuje spójny $a_j$-wierzchołkowy podgraf grafu $G$.

Mówimy, że graf $G$ spełnia warunek Orego ze stałą $k$, jeśli dla każdych dwóch niesąsiednich wierzchołków $x$ i $y$ grafu $G$ suma stopni tych wierzchołków jest nie mniejsza niż $k$. Wiadomo, że każdy graf rzędu $n$ spełniający warunek Orego ze stałą $n-1$ jest trasowalny (tzn. posiada ścieżkę Hamiltona), a więc również dowolnie podzielny. W naszym wystąpieniu wykażemy, że jeśli $n$-wierzchołkowy graf spójny spełnia warunek Orego ze stałą $n-3$, to, poza kilku wyjątkami, warunek dowolnej podzielności jest równoważny
istnieniu skojarzenia doskonałego lub skojarzenia pomijającego dokładnie jeden wierzchołek. Przedstawimy również podobny wynik dla grafu dwuspójnego, który spełnia warunek Orego ze stałą $n-4$.

Serdecznie zapraszamy wszystkich chetnych !