Agnieszka GÖRLICHOWA

(WMS, AGH)

Zanurzanie grafów skierowanych

Niech $\overrightarrow{TT_n}$ oznacza turniej przechodni rzędu n. W pracy [1] pokazaliśmy, że jeżeli rozmiar dowolnego acyklicznego grafu skierowanego $\overrightarrow{G}$ rzędu n nie jest większy niż $\frac{3}{4}(n-1)$, to istnieją dwa krawędziowo rozłączne podgrafy turnieju $\overrightarrow{TT_n}$ izomorficzne z grafem $\overrightarrow{G}$. A więc każdy graf $\overrightarrow{G}$ spełniający powyższe warunki jest dwupakowalny w $\overrightarrow{TT_n}$.
Problemy dwupakowania grafów rzędu n w graf pełny $K_n$ i zanurzania takich grafów w swoje dopełnienie w grafie $k_n$ są problemami równoważnymi. Nie jest to prawdą w sytuacji, gdy rozważamy pakowanie i zanurzanie grafów skierowanych w turnieje przechodnie.
Pokaże, że dowolny acykliczny graf skierowany $\overrightarrow{G}$ rzędu n o rozmiarze nie większym niż $\frac{2}{3}(n-1)$ jest zanurzalny w swoje dopełnienie w turnieju $\overrightarrow{TT_n}$. Co więcej, to ograniczenie jest najlepszym z możliwych.