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 C2k and Cn, Fans, Helms, Flowers, Stars, K2,n and K3,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 W3,n（n≤130） and Mobius ladder Mn（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: Cn if and only if n≥6; Pn if and only if n≠3 or 5; K1,n （n odd）; bistars; dragons; crowns; triangular snakes Tn 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 Gn（Hn）, generalized Petersen graph P（n, k）（n≠4, k≠1）, Kn（o|¨）del graph W3,n（n≠8）.

论文目录

• Abstract
• 1 Introduction
• 1.1 Basic graph theoretic concepts
• 1.2 Graph labeling concepts
• 1.3 Definitions of various graph labeling and known results
• 1.3.1 Cordial labeling
• 1.3.2 Prime cordial labeling
• 1.3.3 Prime labeling
• 1.4 Thesis objectives
• 2 Prime cordial labeling
• 2.1 Introduction
• 2.2 Prime cordial labeling of Flower snark and its related graphs
• 2.3 Prime cordial labeling of generalized Petersen graph P（n,k）
• 3,n'>2.4 Prime cordial labeling" of Kno|¨del graph W_3,n
• 2.5 Chapter summary
• 3 Prime labeling
• 3.1 Introduction
• 3.2 Prime labeling of generalized Petersen graph P（n, 1）
• 3.3 Prime labeling of generalized Petersen graph P（n, 3）
• 3,n'>3.4 Prime labeling of Kno|¨del graph W_3,n
• n'>3.5 Prime labeling of Mo|¨bius ladder M_n
• 3.6 Chapter summary
• Conclusions
• References
• Author's innovations
• List of Publications
• Acknowledgements
• Authorization