ι₁-embeddability Of Some Polygonal Graphs On Surfaces

The distance dG(u, v) between two vertices u and v of a connected graph G = (V, E) is defined as the length of a shortest path connecting them in G. So dG is a metric on V(G), and (V(G), dG) is a graphic metric space associated with G.A graph G= (V, E) is called an l1-graph (sometimes called l1-embeddable), if there exists a positive integer m, such that its graphic metric space (V, dG) can be isometrically embedded into the l1-space (Rm, dl1), that is, there exists a mappingφfrom V(G) onto Rm such that dG(x,y)= dl1(φ(x),φ(y)) for any two vertices x,y of G.In this thesis, we consider the embeddability of open-ended nanotubes into hyper-cubes,l1-embeddability of two classes of regular Mobius hexagonal tiling graphs, the l1-embeddability of graphs under edge-gluing operation, and the l1-embeddability of Mobius quadrilateral tiling graphs.This thesis consists of five chapters. In Chapter one, firstly we introduce the back-ground of the l1-space; secondly, we introduce the basic theory of l1-graphs and the correlative research problems and their developments; thirdly, we introduce some the-ory of a special l1-embedding—isometric embedding; finally, we present the main results obtained in the following chapters.In Chapter two, we study the embeddability of open-ended nanotubes into hyper-cube. Among all the open-ended nanotubes only three classes of special nanotubes, i.e., (0, 1)-type, (1,0)-type and (1, 1)-type nanotubes can be isometrically embedded into hypercubes.In Chapter three, for the two classes of regular Mobius hexagonal tiling graphs H2m,2k and H2m+1,2k+1, by using l1-labels of edges and the recognition algorithm of l1-graphs, we obtain that only H2,2 and H3,3 are l1-embeddalbe.In Chapter four, we discuss the l1-embeddability of graphs obtained from two l1-graphs by gluing an edge. Firstly, we prove that if at least one of the two graphs is bipartite, then the new graph obtained from them by gluing an edge is also an l1-graph. Then, we give two examples to show that for two nonbipartite l1-graphs, the new graph obtained from them by gluing an edge may be an l1-graph or may not be an l1-graph.In Chapter five, we mainly study the h-embeddability of Mobius quadrilateral tiling graphs. First of all, we investigate the balance number of quadrilateral tiling graphs on the Mobius map and the closed disk, and obtain that the balance number of them is 0 and 4, respectively. Secondly, we study the l1-embeddable Mobius quadri-lateral tiling graphs with girth 3 and obtain two forbidden subgraphs of them. Thirdly, for l1-embeddable Mobius quadrilateral tiling graphs with girth 4, we prove that the shortest nonnulhomotopic cycle is an isometric cycle (also convex) and it is unique. Furthermore, cutting the Mobius quadrilateral tiling graphs along the shortest nonnul-homotopic cycle, every component of the resulting graph is a plane square graph. In the last, we construct infinitely many l1-embeddalble Mobius quadrilateral tiling graphs with girth 4.