On the concentration of the domination number of the random graph

DOI10.1137/12090054XMaRDI QIDQ5499732zbMATH OpenOpenAlexFDO

Authors Roman Glebov, Anita Liebenau, Tibor Szabó

Publication date 31 July 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

domination numberrandom graphstwo-point concentration

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this paper we study the behaviour of the domination number of the ErdH{o}s-R'enyi random graph $mathcalG(n,p)$. Extending a result of Wieland and Godbole we show that the domination number of $mathcalG(n,p)$ is equal to one of two values asymptotically almost surely whenever $pggfracl{n}^{2}nsqrtn$. The explicit values are exactly at the first moment threshold, that is where the expected number of dominating sets starts to tend to infinity. For small $p$ we also provide various non-concentration results which indicate why some sort of lower bound on the probability $p$ is necessary in our first theorem. Concentration, though not on a constant length interval, is proven for every $pgg1/n$. These results show that unlike in the case of $pggfracl{n}^{2}nsqrtn$ where concentration of the domination number happens around the first moment threshold, for $p=O(lnn/n)$ it does so around the median. In particular, in this range the two are far apart from each other.

Recommendations

• On the domination number of a random graph
• A note on domination parameters in random graphs
• The domination number of a random graph
• On the tree domination number of a random graph.
• scientific article; zbMATH DE number 553912

Cites work

• A note on the sharp concentration of the chromatic number of random graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• On the chromatic number of random graphs
• On the domination number of a random graph
• On the independence number of random graphs
• Random graphs.
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• The chromatic number of random graphs
• The chromatic number of random graphs
• The concentration of the chromatic number of random graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The two possible values of the chromatic number of a random graph
• Two-point concentration in random geometric graphs
• Upper-bounding the k-colorability threshold by counting covers

Cited in

(27)

• The Slater and sub-\(k\)-domination number of a graph with applications to domination and \(k\)-domination
• The total acquisition number of random graphs
• Graphs with diameter 2 and large total domination number
• Concentration of rainbow \(k\)-connectivity of a multiplex random graph
• Bounds on the maximum number of minimum dominating sets
• The bondage number of random graphs
• The domination number of a random graph
• A detailed study of the dominating cliques phase transition in random graphs
• \((1, j)\)-set problem in graphs
• The domination number of on-line social networks and random geometric graphs
• On a Conjecture of Godsil Concerning Controllable Random Graphs
• On the tree domination number of a random graph.
• A note on domination parameters in random graphs
• (Total) domination in prisms
• Non-concentration of the chromatic number of a random graph
• Approximation algorithms for stochastic clustering
• On the Distribution of the Domination Number of a New Family of Parametrized Random Digraphs
• On the domination number of a random graph
• Connected domination in random graphs
• Two-Point Concentration of the Independence Number of the Random Graph
• How does the chromatic number of a random graph vary?
• Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings
• Robust domination in random graphs
• The message complexity of distributed graph optimization
• Rigid partitions: from high connectivity to random graphs
• Distributed algorithms for random graphs
• The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data

This page was built for publication: On the concentration of the domination number of the random graph

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