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

Abstract: Consider all

k

-element subsets and

e l l

-element subsets

(k > e l l)

of an

n

-element set as vertices of a bipartite graph. Two vertices are adjacent if the corresponding

e l l

-element set is a subset of the corresponding

k

-element set. Let

G_{k, e l l}

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 a m m a (G_{k, 2}) = k + 3 o v e r 2 (k - 1) (k + 1) n^{2} + o (n^{2})

.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: The domination number of the graph defined by two levels of the \(n\)-cube. II