On vertex stability with regard to complete bipartite subgraphs | Zendy

Aneta Dudek | Zendy; Andrzej Żak | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On vertex stability with regard to complete bipartite subgraphs

Author(s) -

Aneta Dudek,

Andrzej Żak

Publication year - 2010

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1521

Subject(s) - combinatorics , mathematics , vertex (graph theory) , bipartite graph , conjecture , graph , induced subgraph , vertex connectivity , discrete mathematics

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 (Km;n; 1)vertex stable graphs with minimum size. Namely, we prove that for m 2 and n m + 2, Q(Km;n; 1) = mn+m+n and Km;n K1 as well as Km+1;n+1 e are the only (Km;n; 1)-vertex stable graphs with minimum size, conrming the conjecture of Dudek and Zwonek.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research