The structures of bad words

详细信息    查看全文

• 作者：Jianxin Wei ^{wjx0426@163.com" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：59
• 期：Complete
• 页码：204-214
• 全文大小：544 K

文摘

The generalized Fibonacci cube Q_d(f)$Q_d\left(f\right)$ is the graph obtained from the hypercube 254278eec" title="Click to view the MathML source">Q_d$Q_d$ by removing all vertices that contain a given binary word f$f$. A word f$f$ is called good if Q_d(f)$Q_d\left(f\right)$ is an isometric subgraph of 254278eec" title="Click to view the MathML source">Q_d$Q_d$ for all d≥1$d\ge 1$, and bad otherwise. The index B(f)$B\left(f\right)$ of a word f$f$ is the smallest integer 259aade5bbcaf1be49d2a41" title="Click to view the MathML source">d$d$ such that Q_d(f)$Q_d\left(f\right)$ is not an isometric subgraph of 254278eec" title="Click to view the MathML source">Q_d$Q_d$. Klavžar and Shpectorov showed that a bad word has a 2-error overlap. In this paper, we show that if a word has a 2-error overlap then it is bad, and we characterize the structures of all bad words. Ilić, Klavžar and Rho showed that a word f$f$ is bad if there exist 250426242c0a40f4360f3" title="Click to view the MathML source">p$p$-critical words for Q_d(f)$Q_d\left(f\right)$ for some 259aade5bbcaf1be49d2a41" title="Click to view the MathML source">d$d$. We find that a word is bad if and only if there exists only a pair of 2-critical words, or only a pair of 3-critical words, or both only a pair of 2-critical words and only a pair of 3-critical words for 13a124bfd839d8b4528c4ac2d979cd" title="Click to view the MathML source">Q_B(f)(f)$Q_{B\left(f\right)}\left(f\right)$. We also design an O(|f|³)$O\left({\left|f\right|}^3\right)$ algorithm which can output the index B(f)$B\left(f\right)$ of f$f$, and give all pairs of 250426242c0a40f4360f3" title="Click to view the MathML source">p$p$-critical words for 13a124bfd839d8b4528c4ac2d979cd" title="Click to view the MathML source">Q_B(f)(f)$Q_{B\left(f\right)}\left(f\right)$.