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

At least 6 years old · documented by

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 T⊂ST\subset S, and let γ(G)\gamma(G) denote the domination number of a graph GG. Badakhshian–Katona–Tuza conjecture. For every fixed integer k≥3k\geq 3,

γ(Gk,2)=k+32(k−1)(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.

References

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.