Research On Sum Graph Labeling Problems In Graph Theory

Graph theory is a branch of mathematics, especially an important branch of discrete mathematics. It has been applied in many different fields in the modern world, such as physiccs, chemistry, astronomy, geography, biology, as well as in computer science and engineering.This thesis mainly researches on graph labeling. Graph labeling traces its origin to the famous conjecture that all trees are grceful presented by A. Rosa in 1966. Vertex labeling is a mapping that maps the vertex set into integer set. According to the different requirement for the mapping, many variations of graph labeling have been evolved. In 1988, F. Harary introduced the notion of a (integral) sum graph. Sum graph was generalied to mod sum graph by Bolland, Laskar, Yurner and Domke in 1990. The concepts of sum graph and integral sum graph have been extended to hypergraphs by Sonntag and Teichert in 2000.Sum graph labelings serves as useful models for a broad range of applications such as astronomy and communication networks. Three classes of graph labeling: (integral) sum graph labeling, mod sum graph labeling, (integral) sum hypergraph labeling are researched, some problems and conjectures have been solved respectively. The main results obtained in this thesis can be summarized as follows:The author gives σ(K_1,1,r) = ζ(K_1,1,r) = r r≥3 and gives the upper(lower) bound of (ζ)σ K_1,r,r r≥ 2; proves Dutch.m-wind mill,fan and flower tree are integral sum graphs; constructs a integral sum graph by identifying three-path tree with a connected integral sum graph; proves the union of unit graph and star and the union of any stars are integral sum graph.The author proves that fan(F_n) is not a mod sum graph and give the mod sum number of F_n (n is even); gives a upper bound of the mod sum number of symmetric complete graph.The author proves σ(K_n^d) = ζ,(K_n^d) = d(n-d) + 1 for n≥2d +1; for d ≥ 4 we prove that every d-uniform hypercycle l is an integral sum hypergraph; we show that for d ≥ 3 d-uniform hypertree and d-uniform hypercycle are mod sum hypergraphs; we prove that d-uniform complete hypergraphs are mod sum hypergraphs when d = n, n-1, d-uniform complete hypergraphs are not mod sum hypergraphs when n≥2^d + d.