On Independent [1, 2]-sets in Hypercubes

¹ Department of Mathematics Education, Sanata Dharma University, Indonesia
² Department of Mathematics, Ateneo de Manila University, Philippines

^* Corresponding author: ekobudisantoso@usd.ac.id

Abstract

Given a simple graph G, a subset S ⊆ V(G) is an independent [1, 2]-set if no two vertices in S are adjacent and for every vertex υ ϵ V(G)\S, 1 ≤ |N(υ) ∩ S | ≤ 2, that is, every vertex υ ϵ V(G)\S is adjacent to at least one but not more than two vertices in S. This paper investigates the existence of independent [1, 2]-sets of hypercubes. We show that for some positive integer k, if n = 2^k − 1, then hypercubes Q_n and Q_n+1 have an independent [1, 2]-set. Furthermore, for 1 ≤ n ≤ 4, we find bounds for the minimum and maximum cardinality of an independent [1, 2]-set of hypercube Q_n, while for n = 5, 6, we get the maximum of cardinality of an independent [1, 2]-set of hypercube Q_n.