# On vertex stability with regard to complete bipartite subgraphs

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 4, page 663-669
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAneta Dudek, and Andrzej Żak. "On vertex stability with regard to complete bipartite subgraphs." Discussiones Mathematicae Graph Theory 30.4 (2010): 663-669. <http://eudml.org/doc/270972>.

@article{AnetaDudek2010,

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 $(K_\{m,n\};1)$-vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, $Q(K_\{m,n\};1) = mn+m+n$ and $K_\{m,n\}*K₁$ as well as $K_\{m+1,n+1\} - e$ are the only $(K_\{m,n\};1)$-vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.},

author = {Aneta Dudek, Andrzej Żak},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {vertex stable; bipartite graph; minimal size},

language = {eng},

number = {4},

pages = {663-669},

title = {On vertex stability with regard to complete bipartite subgraphs},

url = {http://eudml.org/doc/270972},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Aneta Dudek

AU - Andrzej Żak

TI - On vertex stability with regard to complete bipartite subgraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 4

SP - 663

EP - 669

AB - 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 $(K_{m,n};1)$-vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, $Q(K_{m,n};1) = mn+m+n$ and $K_{m,n}*K₁$ as well as $K_{m+1,n+1} - e$ are the only $(K_{m,n};1)$-vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.

LA - eng

KW - vertex stable; bipartite graph; minimal size

UR - http://eudml.org/doc/270972

ER -

## References

top- [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. Zbl1152.05035
- [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. Zbl1193.05095

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.