On vertex stability with regard to complete bipartite subgraphs

Aneta Dudek; Andrzej Żak

Discussiones Mathematicae Graph Theory (2010)

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

Abstract

top
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.

How to cite

top

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 -

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.