On The Topological Structure Of Network Models With Labelling Constraint Conditions

In1966, in order to settle Ringel’s conjecture, Rosa introduces graph labellingsas: A graph labelling is a mapping from the vertex set of a graph to a set ofintegers. By various constraints we have many types of graph labellings. Clearly,graph labelling is an important branch of graph theory since it can be appliedto a wide of scientific areas. However, there are many new problems yielding inattacking famous conjectures, such as Graceful Tree Conjecture, Strongly GracefulTree Conjecture, Odd-graceful Tree Conjecture, Magic Tree Conjecture and so on.Graph labellings have been used in many applications, such as in the devel-opment of redundant arrays of independent disks which incorporate redundancyutilizing erasure codes, some algorithms, design of highly accurate optical gaugingsystems for use on automatic drilling machines, design of angular synchronizationcodes, design of optimal component layouts for certain circuit-board geometries, hi-erarchical networks and self-similar networks, and so on. We, in this article, willresearch a couple of new graph labellings and construct network models that admitthe new labellings.My thesis is organized as:Chapter One distributes a simple introduction to the development of graphtheory and graph labellings. Basic terminology and notation of graph theory aredefined, and the definitions, conjectures and some results of graph labellings aregiven.Chapter Two works mainly on graceful graphs. The main focus is to considerthe origin and development of the graceful tree conjecture. And discussion the (k, d)-graceful tree problem, some constructive methods for building (k, d)-graceful treesare given, and infinite (k, d)-graceful trees are determined by using the methods.Chapter Three, we investigate the edge-magic property of edge-symmetric graphs.First of all, we show some constructive methods for constructing large scale of edge-magic tree. Furthermore, We can split it, and get the split-graphs and split-trees.Secondly, we discuss the relationship between EMTL and anti-MTL by the meth- ods of combining the edge-magic trees and anti-edge trees (or edge-magic trees andgraceful trees) to construct large edge-magic trees. Finally, we define a new labelling,called the (k, d)-EMTL.Chapter Four, we present a new labelling called a generalized edge-magic totallabelling of a graph, and show some constructive methods for constructing largescale of edge-symmetric Graphs.Chapter Five, we introduce some methods to construct vertex-magic total la-bellings of disconnected graphs.I have done the following work: First I discover the constructive set of “Com-pound Split-trees” based on a group of given trees having edge-magic total labellingssuch that the property of edge-magic total labellings can be preserved; second I gen-eralize the notion of edge-magic total labelling on graphs, called “Generalized Edge-magic Total Labellings”; again I create “Matchable Pairs” for researching gracefullabellings of graphs; finally I propose a conjecture: Every proper labelled Knwithn≥6has at least an edge-graceful tree-decomposition such that at least two ofedge-disjoint labelled trees T1, T2,..., Tn1are neither stars nor paths.