On minimum (Kq; k) stable graphs
Résumé
A graph G is a (K_q; k) vertex stable graph (q >= 3) if it contains a clique K_q after deleting any subset of k vertices (k >= 0). We are interested by the (K_q; kappa(q)) vertex stable graphs of minimum size where kappa(q) is the maximum value for which for every nonnegative integer k < kappa(q) the only (Kq; k) vertex stable graph of minimum size is K_{q+k}.
Un graphe G est (K_q; k) stable (avec q >=3) s'il contient une clique K_q après destruction de n'importe quel sous-ensemble de k sommets (k>=0). Nous nous intéressons aux graphes (K_q; kappa(q)) stables ayant un nombre d'arêtes minimum, où kappa(q) est la plus grande valeur possible pour laquelle pour tout entier k < kappa(q) le seul graphe (Kq; k) stable minimum est la clique K_{q+k}.
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...