On vertex stability with regard to complete bipartite subgraphs

• Autorzy: Aneta Dudek , Andrzej Żak
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

vertex stable; bipartite graph; minimal size

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C78: Graph labelling (graceful graphs, bandwidth, etc.)
• 11B50: Sequences (mod m )

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2010
• Tom: 30
• Numer: 4
• Strony: 663-669

Daty

wydano

2010

otrzymano

2009-10-23

poprawiono

2010-02-23

zaakceptowano

2010-03-21

Twórcy

autor

Aneta Dudek

• Faculty of Applied Mathematics, AGH University of Science and Technology, Mickiewicza 30, 30-059 Kraków, Poland

autor

Andrzej Żak

• Faculty of Applied Mathematics, AGH University of Science and Technology, Mickiewicza 30, 30-059 Kraków, Poland

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1521