Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01291961
Contributor : Dieter Mitsche <>
Submitted on : Tuesday, March 22, 2016 - 12:56:30 PM
Last modification on : Monday, October 12, 2020 - 10:28:03 AM
Long-term archiving on: : Sunday, November 13, 2016 - 10:39:19 PM

File

bondage.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01291961, version 1

Collections

Citation

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

Share

Metrics

Record views

136

Files downloads

214