The domination number of the graph defined by two levels of the n-cube, II

2019/10/24 by Balogh, József, Katona, Gyula O. H., Linz, William +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1910.10876

Abstract

Consider all k-element subsets and ℓ-element subsets (k>ℓ ) of an n-element set as vertices of a bipartite graph. Two vertices are adjacent if the corresponding ℓ-element set is a subset of the corresponding k-element set. Let G_k,ℓ denote this graph. The domination number of G_k,1 was exactly determined by Badakhshian, Katona and Tuza. A conjecture was also stated there on the asymptotic value (n tending to infinity) of the domination number of G_k,2. Here we prove the conjecture, determining the asymptotic value of the domination number γ(G_k,2)=k+3\over 2(k-1)(k+1)n²+o(n²).

Related

• Some results on domination number of the graph defined by two levels of the n-cube
• Bipartite graphs with close domination and k-domination numbers
• A New Upper Bound on Total Domination Number of Bipartite Graphs
• Bounds on the 2-domination number
• On the equality of domination number and 2 -domination number