Agnieszka Görlich

(WMS AGH)

O grafach (C_n;k) stabilnych

Graf G nazywamy grafem $(H;k)$ wierzchołkowo stabilnym, jeżeli po usunięciu dowolnych k wierzchołków otrzymujemy graf zawierający podgraf izomorficzny z grafem H. Przez $stab (H;k)$ oznaczamy minimalną ilość krawędzi jaką posiada graf $(H;k)$ wierzchołkowo stabilny.
W trakcie referatu zaprezentowane zostaną wyniki otrzymane wspólnie z S. Cichacz, M. Zwonek i A. Żakiem dotyczące grafów $(C_n;k)$ wierzchołkowo stabilnych. Pokazane zostanie m.in, że

$$n+\lceil 2\sqrt{n-1} \rceil \leq stab(C_n;1) \leq n+\lceil 2\sqrt{n-1} \rceil+1,$$

(a więc ten parametr może przybierać jedną z dwóch tylko możliwych wartości!) oraz konstrukcje grafów ekstremalnych $(C_n,1)$ wierzchołkowo stabilnych dla nieskończenie wielu n (z których wynika, że $stab(C_n;1)=n+\lceil 2\sqrt{n-1} \rceil$ dla nieskoćzenie wielu n). Przedstawiony zostanie również rezultat dający szacowanie parametru dla $k>1$,

$$n+2\sqrt{(k-o(1))n} \leq stab(C_n;k)\leq n+2k\left\lceil \sqrt{n} \right\rceil+k^2.$$

Serdecznie zapraszamy wszystkich chętnych !