The bondage number of random graphs

Abstract : A dominating set of a graph is a subset D of its vertices such that every vertex not in D is adjacent to at least one member of D. The domination number of a graph G is the number of vertices in a smallest dominating set of G. The bondage number of a nonempty graph G is the size of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. In this note, we study the bondage number of binomial random graph G (n, p). We obtain a lower bound that matches the order of the trivial upper bound. As a side product, we give a one-point concentration result for the domination number of G (n, p) under certain restrictions.
Type de document :
Article dans une revue
Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2016
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01291961
Contributeur : Dieter Mitsche <>
Soumis le : mardi 22 mars 2016 - 12:56:30
Dernière modification le : jeudi 11 janvier 2018 - 17:03:52
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 22:39:19

Fichier

bondage.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01291961, version 1

Collections

Citation

Dieter Mitsche, Xavier Pérez-Giménez, Pawel Pralat. The bondage number of random graphs. Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2016. 〈hal-01291961〉

Partager

Métriques

Consultations de la notice

31

Téléchargements de fichiers

20