Research on Some Selected Graph Labeling Topics in Graph Theory 

Author  Khandoker Mohammed Mominul Haque 
Tutor  YangYuanSheng 
School  Dalian University of Technology 
Course  Computer Science and Engineering 
Keywords  Prime labeling Prime cordial labeling generalized Petersen graph Flower snark Mo ¨bius ladder Kno ¨del graph 
CLC  TP391.41 
Type  PhD thesis 
Year  2008 
Downloads  34 
Quotes  0 
Graph labeling is a relatively young subfield 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 nonzero 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）.