19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

$(K_n,k)$ stable graphs

Presented by Prof. Adam Pawel WOJDA
Type: Oral presentation
Track: General session


\begin{document} \title {$(K_n,k)$ stable graphs} \author{A. Pawe\l Wojda\\ AGH - Krak\'ow (Pl)\\ (Joint work with J.-L. Fouquet, H. Thuillier and J.-M. Vanherpe)} \maketitle Let $H$ be a simple graph. A graph $G$ is called to be {\bf $(H,k)$ stable} if it contains a subgraph isomorphic to $H$ after deletion of any subset of $k$ vertices. The edge version of the problem was considered first (for $H$ beeing paths) by Frankl, Katona and Horvath.\\ The notion of $(H,k)$ stable graphs is relatively new, but there are already several results concerning it. Particulary interesting is the problem of finding the minimum size stab$(H,k)$ of a $(H,k)$ stable graph and characterizing all the $(H,k)$ stable graphs with the minimum size. There are allready known some results concerning $(H,k)$ stable graph when $H$ is a bipartite graph (and $k=1$), when $H$ is a star (for any $k$) and when $H$ is a cycle $C_n$ (exact result for $k=1$ and upper and lower bounds for any $k$).\\ We solve this problem when $H$ is the complete graph $K_n$ and either $n \le 5$ ($k$ abitrary) or else, if $6 \le n \le \frac{k}{2}+1$. \end{document}


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors