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

József Balogh, Gyula O.H. Katona, William Linz, Zsolt Tuza

Research output: Contribution to journalArticlepeer-review

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 Gk,ℓ denote this graph. The domination number of Gk,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 Gk,2. Here we prove the conjecture, determining the asymptotic value of the domination number [Formula presented].

Original languageEnglish (US)
Article number103201
JournalEuropean Journal of Combinatorics
Volume91
DOIs
StatePublished - Jan 2021

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'The domination number of the graph defined by two levels of the n-cube, II'. Together they form a unique fingerprint.

Cite this