Search

The k -ary n -cube, denoted Q n k , has the vertex set V n k = { 0 , 1 , ... , k − 1 } n , and two vertices (x 1 , x 2 , x 3 , ... , x n) and (y 1 , y 2 , y 3 , ... , y n) in V n k are adjacent if and only if there is an integer j with 1 ≤ j ≤ n such that x j ≡ y j ± 1 (mod k) and x i = y i for all i ∈ { 1 , 2 , ... , n } ∖ { j }. Let λ (F) be the vertex Turán density of a graph G for a family of forbidden configurations F. Let F 1 = { (0 , 0 , 0) , (1 , 0 , 0) , (0 , 1 , 0) , (0 , 0 , 1) } , F 2 = { (0 , 0 , 0) , (1 , 1 , 0) , (1 , 0 , 1) , (0 , 1 , 1) } , F 3 = { (0 , 0 , 0) , (1 , 1 , 1) } , F d , t , k = { F ⊆ V d k : | F | = t } , and μ (d , k) = max { t : λ (F d , t , k) = 0 }. Johnson and Talbot (2010) determined λ (F i) for i ∈ { 1 , 2 , 3 } and the bounds of μ (d , 2) in Q n 2 (where Q n 2 is the n -dimensional hypercube Q n). In this paper, we derive the exact value λ (F i) for i ∈ { 1 , 2 , 3 } in Q n 3 and determine the bounds of μ (d , k) in Q n k for any k ≥ 3. Furthermore, we consider the forbidden configurations D i = { x ∈ V 3 k : | x | = 0 or | x | = i }. The bounds of λ (D i) in Q n k are derived for any i ∈ { 1 , 2 , 3 } and k ≥ 2 , and λ (G d) = 2 / 3 in Q n 3 is derived, where G d = { x ∈ V d 3 : | x | = 0 , (| x | = 1 , qsupp (x) = i [ 1 ] ) and (| x | = 2 , qsupp (x) = { i [ 1 ] , j [ 1 ] } , i ⁄ ≡ j (mod 2)) } (see Definition 1 for qsupp (x)). [ABSTRACT FROM AUTHOR]