The bondage number of random graphs

MaRDI QIDQ281604zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1502.00169, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p13

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Bounds on the bondage number of a graph
• Domination alteration sets in graphs
• Domination critical graphs
• On bondage numbers of graphs: a survey with some comments
• On the concentration of the domination number of the random graph
• On the domination number of a random graph
• Random graphs.
• The bondage number of a graph

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)