Generalized Fibonacci cubes
Generalized Fibonacci cubes
复制标题
DOI：
10.1016/j.disc.2011.02.015
复制
发表时间：
2012-01-06
影响因子：
0.8
通讯作者：
Rho, Yoomi
中科院分区：
文献类型：
--
作者：
Ilic, Aleksandar;Klavzar, Sandi;Rho, Yoomi
广义Fibonacci立方体Q（d）（f）被引入作为从d-立方体Qd通过移除包含给定二进制串f作为子串的所有顶点而获得的图。在这个符号中，斐波那契立方Gamma（d）是Q（d）（11）。研究了Q（d）（f）是否是Q（d）的等距子图的问题.给出了可嵌入和不可嵌入的无穷级数。这个问题是完全解决的字符串f的长度最多为5和字符串组成的最多三个块。推导了广义Fibonacci立方体的若干性质。斐波那契立方体是除了平凡情况Q（d）（10）和Q（d）（01）之外，唯一的广义斐波那契立方体是相应超立方体的中值闭子图。对于容许串f，引入了图的f-维数。文中还列举了几个问题和建议。(C)2011爱思唯尔有限公司版权所有。
Generalized Fibonacci cube Q(d)(f) is introduced as the graph obtained from the d-cube Qd by removing all vertices that contain a given binary string f as a substring. In this notation, the Fibonacci cube Gamma(d) is Q(d)(11). The question whether Q(d)(f) is an isometric subgraph of Q(d) is studied. Embeddable and non-embeddable infinite series are given. The question is completely solved for strings f of length at most five and for strings consisting of at most three blocks. Several properties of the generalized Fibonacci cubes are deduced. Fibonacci cubes are, besides the trivial cases Q(d)(10) and Q(d)(01), the only generalized Fibonacci cubes that are median closed subgraphs of the corresponding hypercubes. For admissible strings f, the f-dimension of a graph is introduced. Several problems and conjectures are also listed. (C) 2011 Elsevier B.V. All rights reserved.