Research On Labeling Problems In Graph Theory

Graph theory is a branch of mathematics, especially an important branch of discrete mathemtics. It has been applied in many different fields in the modern world, such as physics, chemistry, astronomy, geography, biology, as well as in computer science and engineering.This dissertation mainly researches on graph labeling. Graph labeling traces its origin to the famous conjecture that all trees are graceful presented by A.Rosa in 1966. Vertex labeling is a mapping that maps the vertex set into integer set (in general into an Abelian group). On the other hand, edge labeling maps edge set into integer set. According to the different requirement for the mapping, many variations of graph labelings have been evolved.Based on the theory of Branch and Bound in the field of algorithm design and analysis, in this dissertation, an algorithm is designed to search for graph labeling. Combining the computer constructive prove with mathematical prove, three classes of graph labelings: graceful labeling, harmonious labeling and magic labeling are researched, some problems and conjectures have been solved respectively.Graceful labelings serves as useful models for a broad range of applications such asastronomy and communication networks. In 1979, K.M.Koh et.al conjectured that C_n^t isgraceful if and only if nt=0,3(mod 4). By dividing vertices into different groups reasonably, utilizing an effective bound strategy and the algorithm of graph labeling, this dissertation searches for the graceful labelings of C_n^t and prove that Koh's conjecture is true for n=7,9,11.Hamonious labelings arise in the study of additive bases problems stemming from error-correcting codes. Deb and Limye conjecture that all multiple shells are harmonious. This dissertation analyzes the characteristic of multiple shells, gives the rational vertex groups and effective bound strategy and searches the harmonious labelings of the balanced quadruple shells. It is proved that the conjecture is true for the balanced quadruple shells. The dissertation also proves that gear graph is harmonious graph by the same strategy.Magic labeling is motivated from magic sequares in number theory. Super edge-magic labeling is one of magic labeling with more strict limits, and is related with other well-known classes of labelings. It is helpful to study it for solving other labeling problems. This dissertation transforms the problem of super edge-magic total labeling into an equivalent problem, and give a rational bound condition. It is proved that the magic constant of generalized Petersen graph P(n,k) is (11n+3)/2 and that P(n,3) has super edge-magic total labeling. (a,d)-antimagic labeling is another class of magic labeling. This dissertation also studies (a,d)-antimagic labeling of P(n,3). By the algorithm of graph labeling, it is proved that generalized Petersen graph P(n,k) has ((3n+6)/2,3)-antimagic labeling for k=3.