Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424080 | European Journal of Combinatorics | 2016 | 8 Pages |
Abstract
The generalized Fibonacci cube Qd(f) is the subgraph of the d-cube Qd induced on the set of all strings of length d that do not contain f as a substring. It is proved that if Qd(f)â Qd(fâ²) then |f|=|fâ²|. The key tool to prove this result is a result of Guibas and Odlyzko about the autocorrelation polynomial associated to a binary string. An example of a family of such strings f, fâ², where |f|=|fâ²|â¥23(d+1) is found. Strings f and fâ² with |f|=|fâ²|=dâ1 for which Qd(f)â Qd(fâ²) are characterized.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jernej Azarija, Sandi Klavžar, Jaehun Lee, Jay Pantone, Yoomi Rho,