Discussiones Mathematicae Graph Theory 30(4) (2010) 663-669
doi: 10.7151/dmgt.1521

[BIBTex] [PDF] [PS]

ON VERTEX STABILITY WITH REGARD TO COMPLETE BIPARTITE SUBGRAPHS

Aneta Dudek  and  Andrzej Żak

Faculty of Applied Mathematics
AGH University of Science and Technology
Mickiewicza 30, 30-059 Kraków, Poland
e-mail: {dudekane,zakandrz}@agh.edu.pl

Abstract

A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H ever after removing any of its k vertices. Q(H;k) denotes the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we complete the characterization of (Km,n;1)-vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, Q(Km,n;1) = mn+m+n and Km,n*K1 as well as Km+1,n+1−e are the only (Km,n;1)-vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.

Keywords: vertex stable, bipartite graph, minimal size.

2010 Mathematics Subject Classification: 05C70, 11B50, 05C78.

References

[1] R. Diestel, Graph Theory, second ed. (Springer-Verlag, 2000).
[2] A. Dudek, A. Szymaski and M. Zwonek, (H,k) stable graphs with minimum size, Discuss. Math. Graph Theory 28 (2008) 137-149, doi: 10.7151/dmgt.1397.
[3] A. Dudek and M. Zwonek, (H,k) stable bipartite graphs with minimum size, Discuss. Math. Graph Theory 29 (2009) 573-581, doi: 10.7151/dmgt.1465.

Received 23 October 2009
Revised 23 February 2010
Accepted 21 March 2010