On isomorphism classes of generalized Fibonacci cubes

详细信息    查看全文

• 作者：Jernej Azarija^a ; ^{jernej.azarija@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Sandi Klav啪ar^a ; ^b ; ^c ; ^{sandi.klavzar@fmf.uni-lj.si" class="auth_mail" title="E-mail the corresponding author} ; Jaehun Lee^d ; ^{dlwogns257@naver.com" class="auth_mail" title="E-mail the corresponding author} ; Jay Pantone^e ; ^{jay.pantone@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Yoomi Rho^d ; ^{rho@incheon.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：51
• 期：Complete
• 页码：372-379
• 全文大小：387 K

文摘

The generalized Fibonacci cube Q_d(f)$Q_d\left(f\right)$ is the subgraph of the d$d$-cube Q_d$Q_d$ induced on the set of all strings of length d$d$ that do not contain f$f$ as a substring. It is proved that if Q_d(f)≅Q_d(f^′)$Q_d\left(f\right)\cong Q_d\left(f^{\prime }\right)$ then |f|=|f^′|$\left|f\right|=\left|f^{\prime }\right|$. 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$, f^′$f^{\prime }$, where $\left|f\right|=\left|f^{\prime }\right|\ge \frac{2}{3}(d+1)$ is found. Strings f$f$ and f^′$f^{\prime }$ with |f|=|f^′|=d−1$\left|f\right|=\left|f^{\prime }\right|=d-1$ for which Q_d(f)≅Q_d(f^′)$Q_d\left(f\right)\cong Q_d\left(f^{\prime }\right)$ are characterized.