Badakhshian–Katona–Tuza asymptotic conjecture for the domination number of Gk,2G_{k,2}

Let Gk,2G_{k,2} be the bipartite graph with vertex classes ([n]k)\binom{[n]}{k} and ([n]2)\binom{[n]}{2}, where a kk-element set SS is adjacent to a 2-element set TT exactly when TST\subset S, and let γ(G)\gamma(G) denote the domination number of a graph GG. Badakhshian–Katona–Tuza conjecture. For every fixed integer k3k\geq 3,

γ(Gk,2)=k+32(k1)(k+1)n2+o(n2).\gamma(G_{k,2}) = \frac{k+3}{2(k-1)(k+1)}n^{2} + o(n^{2}).

Badakhshian, Katona and Tuza had previously established upper and lower bounds for this domination number; the conjecture predicts its precise leading asymptotic term.

Sources & referencesView supporting material

Primary source

Yeshwant Pandit, S. L. Sravanthi, Suresh Dara and S. M. Hegde, “Some results on domination number of the graph defined by two levels of the n-cube”, arXiv:1910.00007 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.