On vertex stability with regard to complete bipartite subgraphs

Aneta 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 -