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

preprint2020arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.