Generalized Fibonacci Cubes And Z-transformation Graphs

Based on Fibonacci number, the Fibonacci cube was proposed by Hsu as an inter-connection topology for multiprocessors. The Fibonacci cube is a subgraph of hypercube induced by the vertices without two consecutive ones. In network design, the Fibonacci cube with its many appealing properties is used to emulate many hypercube algorithms efficiently. And then its many interesting topological properties have been studied. One of these is given by Klavzar et al. They proved that Fibonacci cubes are precisely the Z-transformation graphs (also called resonance graphs) of zigzag hexagonal chains, i.e. fibonaccenes. Furthermore, several modifications for the Fibonacci cube have been pre-sented, such as the extended Fibonacci cube, the Lucas cube, the Enhanced Fibonacci cube, the Widened Fibonacci cube and the Fibonacci (p, r)-cube et al.The concept of the Z-transformation graphs for some Chemical graphs was intro-duced under the name resonance graphs. And the concept of Z-transformation graphs on the set of perfect matchings of hexagonal systems was introduced by professor Fuji Zhang et al. from a mathematical point of view. This concept has been extended already to plane bipartite graphs by Heping Zhang et al., and further studied afterward. The Z-transformation graph of a plane bipartite graph G, denoted by Z(G), is a graph whose vertices are the perfect matchings of G, two perfect matchings are adjacent if and only if their symmetric difference is exactly the boundary of an interior face of G, and such boundary is a cycle of G.This thesis mainly consider the relation between various kinds of generalized Fi-bonacci cubes and the Z-transformation graphs, and is structured as follows.In Chapter 1, we summarize the investigation and progression about Fibonacci-like cubes and Z-transformation graphs. We introduce some basic definitions and notations concerning graphs. And the main results of this thesis are also listed.In Chapter 2, we completely characterize hexagonal systems whose Z-transformation graphs are exactly Fibonacci cubes. Note that hexagonal systems are plane bipartite graphs. So we further determine all plane bipartite graphs whose Z-transformation graphs are Fibonacci cubes.In Chapter 3, we introduce some Fibonacci-like cubes. We characterize plane bi-partite graphs whose Z-transformation graphs are exactly extended Fibonacci cubes; We show, however, that none of the Lucas cubes, the Enhanced Fibonacci cubes and the Widened Fibonacci cubes are Z-transformation graphs for plane elementary bipartite graphs; In addition, we present a kind of graphs like Lucas cubes, and we show that such kind of graphs can be the Z-transformation graphs of plane bipartite graphs, and hence we determine all plane bipartite graphs whose Z-transformation graphs are such kind of graphs.In Chapter 4, we introduce a generalized interconnection topology called the Fi-bonacci (p, r)-cube, which includes a wide range of interconnection topologies as its spe-cial cases, such as the hypercube, the Fibonacci cube, the postal network, etc. We discuss values of p, r and n for which Fibonacci (p, r)-cubes can be the Z-transformation graphs of plane bipartite graphs. To see this, we begin with extending the concept of the Z-transformation graphs of plane bipartite graphs to plane graphs, then mainly characterize Fibonacci (p, r)-cubes which can be the Z-transformation graphs of plane graphs. And then we determine all Fibonacci (p, r)-cubes which can be the Z-transformation graphs of plane bipartite graphs.In Chapter 5, we consider the Z-transformation graphs for plane non-bipartite graphs, especially for 1-extendable plane non-bipartite graphs. We prove that none of the Fi-bonacci cubes are Z-transformation graphs for 1-extendable connected plane non-bipartite graphs. Further, we characterize Fibonacci (p, r)-cubes which can be the Z-transformation graphs of 1-extendable connected plane non-bipartite graphs.