Research On Prime Labeling And FFI Set Of Some Graphs

Graph labeling is one of the most important fields in Graph Theory. Our research bases on the theory of branch and bound in the field of algorithm design and analysis in this dissertation. By combining the computer constructive prove with the mathematical prove, two classes of graph labeling: prime labeling , FFI set are studied.Prime labeling was originated with Entringer and introduced by Tout, Dabboucy, and Howalla.Roger Entringer conjectured that all trees are prime. Up to now among the classes of trees known to have prime labeling are: paths, stars, caterpillars, complete binary trees, spide, oliver trees, and all trees of order up to 50. From recent research we know that following graphs are also prime : all cycles, the disjoint of C_2n and C_n, W_n (n is even), Fans, Helms,Flowers, K_2,nand K_3,n(n≠3,7), Books, S_n^m, C_n(?)P_m, P_n×(?)₂(n = 2 or n is odd). Vilfredconjectured that the grid P_m×P_n is prime when n is prime and n>m, this conjecture was proved by Sundaram et.al. In the same paper they also showed that P_n×P_n is prime when n is prime. Carlson proved that all generalized books and Cn-Snakes are prime. Yao, Cheng, Zhongfu have shown: a tree of order n with maximum degree at least n/2 is prime. FFI Set is introduced by Harris Kwong, Sin. Min. Lee, Ho. Kuen. Ng with the definition :{ i_f(G)|f is the Friendly labeling of G} in 2006, the result of FFI(C_n) is given. They proved that totalgraph of trees, cycles with parallel chords, prisms and Mobius ladders, bipartite graphs are all have FI(G). Later Wai Chee Shiu, Harris Kwong proved that P₂×P_n has FFI(G).This paper proves these two graphs are prime: the generalized petersen graph P(n,1) when n≤2500 and m is even, the Knodel graph W(3,n) when n≤130 and n is even. The paper also gives the FFI(G) of generalized petersen graph P(n,2):...