Discussiones Mathematicae Graph Theory 29(3) (2009) 573-581
doi: 10.7151/dmgt.1465

[BIBTex] [PDF] [PS]

(H,k) STABLE BIPARTITE GRAPHS WITH MINIMUM SIZE

Aneta Dudek  and  Małgorzata Zwonek

Faculty of Applied Mathematics
AGH University of Science and Technology
Kraków, Poland
e-mail: dudekane@agh.edu.pl
e-mail: malgorzata.zwonek@agh.edu.pl

Abstract

Let us call a graph G (H;k) vertex stable if it contains a subgraph H after removing any of its k vertices. In this paper we are interested in finding the (Kn,n+1;1) (respectively (Kn,n; 1)) vertex stable graphs with minimum size.

Keywords: graph, vertex stable graph.

2000 Mathematics Subject Classification: 05C35.

References

[1] A. Dudek, A. Szymański and M. Zwonek, (H,k) stable graphs with minimum size, Discuss. Math. Graph Theory 28 (2008) 137-149, doi: 10.7151/dmgt.1397.
[2] P. Frankl and G.Y. Katona, Extremal k-edge-hamiltonian hypergraphs, Discrete Math. 308 (2008) 1415-1424, doi: 10.1016/j.disc.2007.07.074.
[3] I. Horváth and G.Y. Katona, Extremal stable graphs, submitted.

Received 23 May 2008
Revised 26 September 2008
Accepted 26 September 2008