19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
$(K_n,k)$ stable graphs
Presented by Prof. Adam Pawel WOJDA
Type: Oral presentation
Track: General session
Content
\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}
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Prof. Jean-Luc FOUQUET Universite d'Orleans, France
- Prof. Jean-Marie VANHERPE Universite d'Orleans, France
- Prof. Henri THUILLIER Universite d'Orleans, France