On    (   K  q   ;  k  )   ‐Stable Graphs | Zendy

Żak Andrzej | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

On ( K q ; k ) ‐Stable Graphs

Author(s) -

Żak Andrzej

Publication year - 2013

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.21705

Subject(s) - mathematics , combinatorics , conjecture , vertex (graph theory) , graph , discrete mathematics , integer (computer science) , computer science , programming language

A graph G is called ( H ; k ) ‐ vertex stable if G contains a subgraph isomorphic to H even after removing any k of its vertices. By stab ( H ; k ) we denote the minimum size among the sizes of all ( H ; k ) ‐vertex stable graphs. Given an integer q ≥ 2 , we prove that, apart of some small values of k , stab ( K q ; k ) = ( 2 q − 3 ) ( k + 1 ) . This confirms in the affirmative the conjecture of Dudek et al. [Discuss Math Graph Theory 28(1) (2008), 137–149]. Furthermore, we characterize the extremal graphs.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research