On (Kq,k) vertex stable graphs with minimum size

A graph G is a (Kq,k) vertex stable graph if it contains a Kq after deleting any subset of k vertices. We give a characterization of (Kq,k) vertex stable graphs with minimum size for q=3,4,5.

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2012-07, Vol.312 (14), p.2109-2118
Main Authors: Fouquet, J.-L., Thuillier, H., Vanherpe, J.-M., Wojda, A.P.
Format: Article
Language:English
Subjects:
Computer Science
Discrete Mathematics
Stable graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph G is a (Kq,k) vertex stable graph if it contains a Kq after deleting any subset of k vertices. We give a characterization of (Kq,k) vertex stable graphs with minimum size for q=3,4,5.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2011.04.017