Labelling Properties Of Special Graphs Served As Network Models

In1966, in order to settle Ringel’s conjecture, Rosa introduced the conceptof graph labellings: A graph labelling is a mapping from the vertex set of a graphto a set of integers. By various constraints we have many types of graph labellings.Clearly, graph labelling is an important branch of graph theory since it can be ap-plied to a wide of scientifc areas. However, there are many new problems yieldingin attacking famous conjectures, such as Graceful Tree Conjecture and so on. Graphlabellings have been used in many applications, such as in the development of re-dundant arrays of independent disks which incorporate redundancy utilizing erasurecodes, some algorithms, design of highly accurate optical gauging systems for use onautomatic drilling machines, design of angular synchronization codes, design of op-timal component layouts for certain circuit-board geometries, hierarchical networksand self-similar networks, so we, in this article, will research some new graph labellingand construct network models that admit the new labellings.Based on research of complex networks, we defne classes of graphs, called uni-formly (k, m)-dragon graphs and irregular dragon graphs, as models of complex net-works. This thesis is concerned with some problems of graph labelling. More specif-cally, our aim is to discuss some topics on graceful labellings, odd-graceful labellingsand (k, m) odd-graceful labellings of uniformly (k, m)-dragon graphs and irregulardragon graphs. Our works consist of four chapters.Chapter One distributes a simple introduction to the development of graph theoryand graph labellings. Basic terminology and notation of graph theory are defned, andthe defnitions, conjectures and some results of graph labellings are given.Chapter Two works mainly on graceful labelling of graphs. The main focus is toconsider the origin and development of the graceful tree conjecture. Then some con-structive methods for building uniformly (k, m)-dragon graphs and irregular dragongraphs are given, and gracefulness dragon graphs are determined by using the meth-ods.Chapter Three, we investigate the odd-gracefulness of some dragon graphs. Firstly,we show some constructive methods for building large scale of gracefulness dragongraphs and prove it. Secondly, we show that required graphs can be gotten by meth-ods of dividing and constructing an edge set E. Finally, we can construct large uniformly (k, m)-dragon graphs and irregular dragon graphs.Chapter Four works mainly investigate the (k, d) odd-gracefulness of some dragongraphs. Firstly, we present some constructive ways for constructing large scale ofgracefulness dragon graphs in advance. Furthermore, we show that the graceful graphshave (k, d) odd-graceful labelling. Ultimately, by combining the methods we con-struct large uniformly (k, m)-dragon graphs and irregular dragon graphs. Throughthe defnition of dragon graphs and proofs of Theorems, we get some simple but usefulconclusions.