On the Concentration of the Domination Number of the Random Graph

DOI10.1137/12090054XzbMath1317.05137arXiv1209.3115OpenAlexW1575931478MaRDI QIDQ5499732

Anita Liebenau, Tibor Szabó, Roman Glebov

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

random graphsdomination numbertwo-point concentration

Mathematics Subject Classification ID

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

Related Items (15)

Bounds on the maximum number of minimum dominating sets ⋮ The bondage number of random graphs ⋮ \((1, j)\)-set problem in graphs ⋮ The total acquisition number of random graphs ⋮ Unnamed Item ⋮ Graphs with diameter 2 and large total domination number ⋮ Distributed algorithms for random graphs ⋮ 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 rainbow \(k\)-connectivity of a multiplex random graph ⋮ Non-concentration of the chromatic number of a random graph ⋮ (Total) domination in prisms ⋮ Tropical dominating sets in vertex-coloured graphs ⋮ The Slater and sub-\(k\)-domination number of a graph with applications to domination and \(k\)-domination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper-bounding the \(k\)-colorability threshold by counting covers
• On the independence number of random graphs
• On the chromatic number of random graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• A note on the sharp concentration of the chromatic number of random graphs
• The concentration of the chromatic number of random graphs
• Two-point concentration in random geometric graphs
• The chromatic number of random graphs
• The chromatic number of random graphs
• The two possible values of the chromatic number of a random graph
• On the domination number of a random graph

This page was built for publication: On the Concentration of the Domination Number of the Random Graph