Dissertation > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Pattern Recognition and devices > Image recognition device

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
Download Dissertation

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).

Related Dissertations
More Dissertations