The bondage number of random graphs

zbMATH Open1335.05162arXiv1502.00169MaRDI QIDQ281604FDOQ281604

Authors: D. Mitsche, Xavier Pérez-Giménez, Paweł Prałat 

Publication date: 11 May 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1502.00169

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The bondage number of a graph
• On the bondage number of a graph
• The bondage number of \((n-3)\)-regular graphs of order \(n\).
• New results about the bondage number of a graph
• scientific article; zbMATH DE number 876673

zbMATH Keywords

random graphdomination numberbondage number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Random graphs.
• On the concentration of the domination number of the random graph
• On the domination number of a random graph
• The bondage number of a graph
• Bounds on the bondage number of a graph
• On bondage numbers of graphs: a survey with some comments
• Domination alteration sets in graphs
• Domination critical graphs

Cited In (2)

• Linking number and writhe in random linear embeddings of graphs
• Betti numbers and anti-lecture Hall compositions of random threshold graphs

This page was built for publication: The bondage number of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281604)