PDF
Discussiones Mathematicae Graph Theory 30(4) (2010)
663-669
DOI: https://doi.org/10.7151/dmgt.1521
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
Close