The Research On Some Labeling Problems In Graph Theory

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. On the other hand, edge labeling maps edge set into integer set. According to the different requirements for the mapping, many variations of graph labelings have been evolved. In this paper, combining the computer constructive prove with mathe- matical prove, three classes of graph labelings: skolem graceful labeling, magic labeling and harmonious labeling are researched, some problems and conjectures have been solved respectively. Graceful labelings serves as useful models for a broad range of applications such as astronomy and communication networks. The Skolem graceful labelings have been invented analogues of graceful graphs by modifying the permissible vertex labels. The K-stars graph is a disjoint union of K stars with random size. Kishore has shown that a necessary condition for St(n₁, n₂,..., n_k) to be Skolem graceful is that some n_i is even or k≡0, 1 (mod 4). He conjectures that each one of these conditions is sufficient. Lee, Wang, and Wui showed that the 2-stars and 3-stars are Skolem-graceful for some n_i is even. Denham, Leu, and Liu proved all 4-stars are Skolem-graceful. Choudum and Kishore proved that all 5-stars are Skolem graceful. In this thesis, we prove that all K-stars are Skolem graceful.Magic labeling is motivated from magic sequares in number theory. Figueroa-Centeno et al. proved a book not have a super edge-magic total labeling when n is odd and n≠5 (mod 8) and conjectured that the book B_n is super edge-magic total labeling if and only if n is even or n≡5 (mod8). In this paper, we prove that the book B_n is a super edge-magic total labeling graph while a is even(n≥6). We also study the super vertex- magic total labeling with Knodel graph W_3,n and Flower Snark and related graph F_n. It is proved that Knodel graph W_3,n is a super vertex-magic total labeling graph if and only if n≡0 (mod 4). All Flower Snark and related graph F_n are super vertex-magic total labeling graphs.Hamonious labelings arise in the study of additive bases problems stemming from error-correcting codes. Xu proved the triangular snake graph is harmonious if and only is p≠2 (mod 4). We prove all double triangular snake graph are hamonious. Deb and Limye conjecture that all multiple shells are harmonious and have shown that the conjecture is true for the balanced double shells and balanced triple shells. Yang, Xu, Xi, and Qiao proved the conjecture is true for balanced quadruple shells. It is proved that the conjecture is true for the balanced quintuple shells.