On vertex stability with regard to complete bipartite subgraphs

Aneta Dudek; Andrzej Żak

Discussiones Mathematicae Graph Theory, Tome 30 (2010), p. 663-669 / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

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) = m n + 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.

Publié le : 2010-01-01

Zbl 1217.05112

EUDML-ID : urn:eudml:doc:270972

@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1521,
     author = {Aneta Dudek and Andrzej \.Zak},
     title = {On vertex stability with regard to complete bipartite subgraphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {30},
     year = {2010},
     pages = {663-669},
     zbl = {1217.05112},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1521}
}

Aneta Dudek; Andrzej Żak. On vertex stability with regard to complete bipartite subgraphs. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 663-669. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1521/

Bibliographie

[000] [1] R. Diestel, Graph Theory, second ed. (Springer-Verlag, 2000).

[001] [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. | Zbl 1152.05035

[002] [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. | Zbl 1193.05095