Discussiones Mathematicae Graph Theory 28(1) (2008) 137-149

(H,k) STABLE GRAPHS WITH MINIMUM SIZE

Aneta Dudek, Artur Szymański  and  Małgorzata Zwonek

Faculty of Applied Mathematics AGH
Mickiewicza 30, 30-059 Kraków, Poland

Abstract

Let us call a G (H,k) graph vertex stable if it contains a subgraph H ever after removing any of its k vertices. By Q(H,k) we will denote the minimum size of an (H,k) vertex stable graph. In this paper, we are interested in finding Q(C3,k), Q(C4,k), Q(K1,p,k) and Q(Ks,k).

Keywords: graph, stable graph.

2000 Mathematics Subject Classification: 05C35.

References

[1] P. Frankl and G.Y. Katona, Extremal k-edge-hamiltonian hypergraphs, accepted for publication in Discrete Math.
[2] I. Horváth and G.Y. Katona, Extremal stable graphs, manuscript.
[3] R. Greenlaw and R. Petreschi, Cubic Graphs, ACM Computing Surveys, No. 4, (1995).

Received 8 January 2007
Revised 16 October 2007
Accepted 26 October 2007