We give a new upper bound for the length of the largest induced cycle in the hypercube.
1. Introduction
Let G1 and Gz be two graphs. The Cartesian product G= G1 x G2 has V(G)= V(G,) x V(G,), and two vertices (ul, u2) and (vl, u2) of G are adjacent if and only if either ul=vl and uzuz~E(G2) or u2=u2 and uIuI~E(G1). Let Q1=K2. For na2, the n-cube Q" is defined inductively as Q"-' x K2. The n-cube Q" can also be considered as the graph whose vertices are labeled by the binary n-tuples and such that two vertices are adjacent if and only if their corresponding n-tuples differ in precisely one position. Let S denote the longest snake (induced cycle) in Q". We will allow ourselves the freedom of using S to denote V(S), context should make it clear. The problem of determining the size of S originated with Kautz [4] while investigating error checking codes. Computing the exact value of ISJ for all n-cubes, at present, seems hopeless. In fact, at the present time only the first five values are known. They are 4,6,8, 14, and 26 (for n = 2, 3,4,5, and 6, respectively); the value of ISI for Q' is unknown. Recently, Abbott and Katchalski [l] have shown that ISI >(0.30)2" for all n. Previously, the best upper bound was due to Solov'jeva [S], who improved the earlier bound of Diemer