Study On Prime Labeling Of Grid Graphs

The problem of prime labeling of graphs is one of the most important research topics in graph theory.In this thesis,we give some kinds of prime labeling of graphs.This article is divided into four parts.The first chapter mainly introduces the concept and research status of the prime labeling problem.In Chapter 2,based on the results of Sundaram,Ponraj and Somasundaram,we further prove that for some special values of m and n,P_m×P_nis a prime graph,precisely:（1）P_n-1×P_n-1（2）P_n×P_n+3（3）P_n×P_n+4are prime graphs,where n is an odd prime number.In Chapter 3,we give a prime labeling of lower order grid graphs P_n×P_nfor n≤31.Chapter 4,based on research results of Prajapati,Gajjar,and combined with Zhongping Zhao’s research on prime labeling of the generalized Petersen graph,we prove that if n<2500,P₂×P_nis also a prime graph,and give a prime labeling.Finally,we put forward a conjecture:for any n,P₂×P_nis prime graph.