Isometric Embeddings Of Generalized Fibonacci Cubes Into Hypercubes

The hypercube of dimension n is the graph Qn whose vertex set is the set of all the binary strings of length n and two vertices are adjacent if they differ in exactly one coordinate. Hypercube has numerous applications, such as in coding theory, computer architecture, mathematical chemistry, phylogenetics, etc. G is called a partial cube if there is an isometric embedding of graph G into hypercubes. Partial cubes have applications in networks theory, location theory and chemical graph theory. Notice that distance between any two vertices of Qn is equal to the Hamming distance of them. So in a partial cube one can get the distance between the vertices of it. The question determining a graph is a partial cube or not is a fundamental question.Fibonacci cube Γn is the subgraph of Qn induced by the binary strings that con-tain no two consecutive Is. When it was introduced as a new model for an intercon-nection network, it soon became increasingly popular. Furthermore, several modifi-cations and generalizations of Fibonacci cube, called Fibonacci-like cubes, have been presented, such as the Lucas cube, Extended-Fibonacci Cube, Enhanced-Fibonacci Cube, Fibonacci (p, r)-cube and generalized Fibonacci cube et al. Fibonacci (p,r)-cube is the subgraph of Qn induced by the strings that contain at most r consecutive Is and at least p Os between two substrings composed of consecutive Is. Generalized Fibonacci cube Qn(f) is the graph obtained from Qn(f) by removing all vertices that contain f as a substring.It is known that Fibonacci cubes are isometric subgraphs of Qn. So it is natural to raise a question of determining which Fibonacci-like cubes are partial cubes.This thesis mainly consider the isometric embeddings of Fibonacci (p, r)-cubes and generalized Fibonacci cubes into hypercubes.This thesis consists five chapters. In Chapter1, firstly we introduce some ba- sic definitions concerning graphs. Secondly, we introduce isometric embeddings of graphs, hypercube and a basic characterization of partial cubes. Thirdly, we introduce Fibonacci cubes and Fibonacci-like cubes and present some of their graph properties and applications. We finish this chapter by presenting the main results of this thesis.In Chapter2, we study the isometric embeddability of Fibonacci (p,r)-cubes into hypercubes. We determine that a Fibonacci (p, r)-cube Γ(p,r)/n■is a partial cube if and only if either p=1, or p≥2and r≤p+1. Furthermore, we point out that Γ(p,r)/n is a partial cube if and only if it is an isometric subgraph of Qn, and for Fibonacci (p, r)-cubes, partial cubes, semi-median graphs and almost-median graphs are all equivalent.In Chapter3we solve one problem and three conjectures on generalized Fibonacci cubes posed by Ilic, Klavzar and Rho. The problem is that Qd(f) is not an isometric subgraph of Qd, is there a dimension d’ such that Qd(f) can be isometrically embedded into Qd’? They conjectured that if Qd(f) is an isometric subgraph of Qd, then Qd(ff) is also an isometric subgraph of Qd.They also conjectured that the index B(f) of a bad word string f is less than2|f|. We give a negative answer to the above problem and confirm those two conjectures by a basic property of critical words given in this chapter. Another conjecture they given is that if f is a bad word that contains exactly two Os, the f is2-isometric if and only if f=12r-1012r-1012r+1for some r≥0. We prove that this conjecture is not true and we show that if f is a bad word that contains exactly two Os, then f is2-isometric if and only if f=1r01r012(r+1) for some r≥0.In Chapter4, firstly we study some good and bad strings with special forms. Sec-ondly we characterize all the good and the bad strings of4and5blocks, and for every bad strings f we give the dimension d such that Qd(f) can be isometrically embedded into Qd-By those discussions, we give the classification of isometric embeddability of generalized Fibonacci cubes with forbidden factors of length6and7.In Chapter5, we summarize the main work of the whole thesis and provide suggestions for future work in this area.