Research On Some Selected Graph Labeling Topics In Graph Theory

Graph labeling is a relatively young sub-field of graph theory. The first bona fidegraph labeling problem is the bandwidth problem, which is concerned with minimizing the difference between the labels of adjacent vertices. Bandwidth was originally studied in the 1950's, in relation to matrices with all non-zero elements lying within a narrow band about the main diagonal. In 1966 A. Rosa introduced the famous conjecture that all trees are graceful with a new type of graph labeling "Graceful labeling". In this thesis, combining the computer constructive prove with mathematical prove, some classes of graph labelings: Prime cordial labeling and Prime labeling are researched.Many number puzzles involve prime numbers. Prime numbering or prime labeling is motivated from Magic matrix. A graph is called prime if it has a prime labeling. This concept was originated with Entringer and introduced by Tout, Dabboucy, and Howalla. In 1980 Entringer conjectured that all trees are prime. From recent research we know that following graphs are prime: every tree with n≤50, disjoint union of C_2k and C_n, Fans, Helms, Flowers, Stars, K_2,n and K_3,n unless n = 3 or 7. In this thesis, we prove tha,t following graphs axe prime: generalized Petersen graphs P(n,1)(n≤2500) and P(n,3)(n≤100) for even n, Knodel graph W_3,n(n≤130) and Mobius ladder M_n(5≤n≤2001) for odd n. We also prove that generalized Petersen graphs P(n, 1) and P(n, 3) are not prime for odd n.The concept of prime cordial labeling introduced by M. Sumndarm, R. Ponraj, and S. Somasundram. They proved that the following graphs are prime cordial: C_n if and only if n≥6; P_n if and only if n≠3 or 5; K_1,n (n odd); bistars; dragons; crowns; triangular snakes T_n if and only if n≥3; ladders. In this thesis, we prove that the following graphs are prime cordial: Flower snark and its related graphs G_n(H_n), generalized Petersen graph P(n, k)(n≠4, k≠1), Kn(o|¨)del graph W_3,n(n≠8).