Proofs of two conjectures on generalized Fibonacci cubes

详细信息    查看全文

• 作者：Jianxin Wei^a ; ^b ; ^{wjx0426@163.com" class="auth_mail" title="E-mail the corresponding author} ; Heping Zhang^a ; ^{zhanghp@lzu.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：51
• 期：Complete
• 页码：419-432
• 全文大小：798 K

文摘

A binary string f$f$ is a factor of string f45bb1" title="Click to view the MathML source">u$u$ if f$f$ appears as a sequence of 03fd211dfb03" title="Click to view the MathML source">|f|$\left|f\right|$ consecutive bits of f45bb1" title="Click to view the MathML source">u$u$, where 03fd211dfb03" title="Click to view the MathML source">|f|$\left|f\right|$ denotes the length of f$f$. Generalized Fibonacci cube Q_d(f)$Q_d\left(f\right)$ is the graph obtained from the d$d$-cube Q_d$Q_d$ by removing all vertices that contain a given binary string f$f$ as a factor. A binary string f$f$ is called good if Q_d(f)$Q_d\left(f\right)$ is an isometric subgraph of Q_d$Q_d$ for all d≥1$d\ge 1$, it is called bad otherwise. The index of a binary string f$f$, denoted by B(f)$B\left(f\right)$, is the smallest integer d$d$ such that Q_d(f)$Q_d\left(f\right)$ is not an isometric subgraph of Q_d$Q_d$. Ili膰, Klav啪ar and Rho conjectured that B(f)<2|f|$B\left(f\right)<2\left|f\right|$ for any bad string f$f$. They also conjectured that if Q_d(f)$Q_d\left(f\right)$ is an isometric subgraph of Q_d$Q_d$, then Q_d(ff)$Q_d\left(ff\right)$ is an isometric subgraph of Q_d$Q_d$. We confirm these two conjectures by obtaining a basic result: if there exist p$p$-critical words for Q_B(f)(f)$Q_{B\left(f\right)}\left(f\right)$, then p=2$p=2$ or p=3$p=3$.