科研之友
微信
新浪微博
Facebook
分享链接
摘要
Generalized Fibonacci cube Q(n)(f) is the graph obtained from the n-cube Q(n) by removing all vertices that contain a given binary string f as a consecutive substring. A binary string f is called bad if Q(n)(f) is not an isometric subgraph of Q(n) for some n, and the smallest such integer n, denoted by B(f), is called the index of f. Ilic, Klavzar and Rho posed a problem that if Q(n)(f) is not an isometric subgraph of Q(n) is there a dimension n' such that Q(n)(f) can be isometrically embedded into Q(n') ? We give a negative answer to this problem by showing that if f is bad, then for any n >= B(f), Q(n)(f) cannot be isometrically embedded to any hypercube.
