Independent domination in the graph defined by two consecutive levels of the n-cube

Fix a positive integer n and consider the bipartite graph whose vertices are the 3-element subsets and the 2-element subsets of [n] = {1, 2, ... , n}, and there is an edge between A and B if A subset of B. We prove that the domination number of this graph is (n ) - & LeftFloor; (n+1)2 8 & RightFloor;, we characterize the dominating sets of minimum size, and we observe that the minimum size dominating set can be chosen as an independent set. This is an exact version of an asymptotic result by Balogh, Katona, Linz and Tuza (2021). For the corresponding bipartite graph between the (k+ 1)-element subsets and the k-element subsets of [n] (k >= 3), we provide a new construction for small independent dominating sets. This improves on a construction by Gerbner, Kezegh, Lemons, Palmer, P & aacute;lv & ouml;lgyi and Patk & oacute;s (2012), who studied these independent dominating sets under the name saturating flat antichains. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).