The Research On Graceful, Odd-graceful And Odd-elegant Labelings Of Graphs

Graph labelings can be traced to the famous conjecture that all trees are gracefulpresented by Rosa in the late1960s．A graph labelling is an assignment of integersto the vertices or edges, or both, subject to certain conditions. According to the dif-ferent requirements for the condition，many variations of graph labelings have beenevolved．About some conjectures of graph labellings (such as all trees are graceful,all lobsters are graceful, all trees are odd-graceful) no proof of the truth or falsity ofthese conjectures have been found up to now. Graph labelings serve as useful mod-els for a broad range of applications such as coding theory, X-ray crystallography,radar, astronomy, circuit design, communication network broadcasting and address-ing, database management, block design, experimental design, group testings, DNAlibrary screening, scheduling, sharing scheme, synchronous optical network, perfectsystems of diference sets and missile control code design. Therefore, graph labellingas a subbranch of graph theory has been developed rapidly.This thesis is concerned with some problems of graph labelling. More specif-cally, our aim is to discuss some topics on0-rotatability, odd-gracefulness and odd-elegantness of trees. We have constructed our works in four chapters.A short but relatively complete introduction is given in Chapter1. Some nota-tions and terminologies are introduced and defned. Then we describe some progressof above three aspects. At last, we outline the main results of this thesis.In Chapter2, the main focus is to consider the origin of the graceful tree con-jecture. And discussion the0-rotatable tree problem, some constructive methods forbuilding0-rotatable trees are given, and infnite0-rotatable trees are determined byusing the methods.In Chapter3, we investigate the odd-gracefulness of some trees. Firstly, weshow some constructive methods for constructing large scale of odd-graceful tree.Furthermore, we prove·Spiders having legs of lengthes in {m, m+1} for m≥1are odd-graceful.Secondly, we show that a connected graph H is set-ordered odd-graceful if andonly if H is bipartite graceful. By the method of adding leaves to a graph H, showthat for any connected set-ordered odd-graceful graph H, adding leaves to H producesan odd-graceful graphs. Furthermore, we show ·All lobsters are odd-graceful.By the methods of combining the graceful trees and odd-graceful trees to con-structing large odd-graceful trees and the induction on orders of trees, we prove thefollowing results:·Every symmetric tree with a root w admits an odd-graceful labelling such thatw is labelled with0.·Every complete k-ary tree admits an odd-graceful labelling such that its rootis labelled with0.·Every complete (2m1)-ary tree is edge-ordered odd-graceful.In Chapter4, we present a new labelling called an odd-elegant labelling of a graph,and show some constructive methods for constructing large scale of odd-elegant tree.We prove the following results:·An odd-elegant graph G is a bipartite graph.·For every vertex w of an odd-elegant graph G there exists an odd-elegantlabelling such that w is labelled with0.·Every caterpillar is odd-elegant.·Every lobster is odd-elegant.·All trees of diameters at most fve are odd-elegant.·Spiders having legs of lengthes in {m, m+1} for m≥1are odd-elegant.Furthermore, we presentConjecture. All trees are odd-elegant.