Neighborhoods of Unbordered Words in the \(n\)-Cube

The \( n \)-cube is the graph whose vertices are all binary words of length \( n > 1 \) and whose edges join vertices that differ in exactly one entry; i.e., are at Hamming distance \( 1 \) from each other. If a word has a non-empty prefix, not the entire word, which is also a suffix, then it is said to be bordered. A word that is not bordered is unbordered. Unbordered words have been studied extensively and have applications in synchronizable coding and pattern matching. The neighborhood of an unbordered word \( w \) is the word itself together with the set of words at Hamming distance \( 1 \) from \( w \). Over the binary alphabet, the neighborhood of an unbordered word \( w \) always contains two bordered words obtained by complementing the first and last entries of \( w \). We determine those unbordered words \( w \) whose neighborhoods otherwise contain only unbordered words.