P_(2r,b)图的优美性  

THE GRACEFULNESS OF GRAPH P_(2r,b)

作　　者：容青[1] 熊冬春[1] 

机构地区：[1]广西师范学院计算机与信息工程学院,南宁530023

出　　处：《系统科学与数学》2010年第5期703-709,共7页Journal of Systems Science and Mathematical Sciences

基　　金：广西教育厅科研项目(200807LX431);广西师范学院青年科研基金项目(0709B006)资助课题

摘　　要：Kathiresan KM证实P_(2r,2m-1)(r,m皆为任意正整数)是优美的且猜想:除了(a,b)=(2r-1,4m-2)外,所有的P_(a,b)都是优美的.杨元生证实P_(2r+1,2m+1)是优美的,并且证实了当r≤7,r=9时的P_(2r,2m)是优美的.严谦泰证实r为奇数时P_(2r,2m)是优美的.采用回溯和分支限界算法搜索到了一个适合于所有P_(2r,b)图(r,b皆为任意正整数)的优美标号,用函数构造法提取其规律并从数学的严格性进行了证明,使得所有的P_(2r,b)图(r,b皆为任意正整数)的优美性得到了证实.Kathiresan K M showed that P2r,2m-1 is graceful and conjectured that Pa,b is graceful except when a = 2r - 1 and b = 4m - 2. Professor Yang Yuansheng showed that g2r＋l,2m＋l and P2r,2m （r≤7, r = 9） are graceful. Yan Qiantai pointed out that P2r,2m are graceful when r is odd. In this paper, a graceful label adapting to all the P2r,b is searched by trace and branch bound method. So the gracefulness of P2r, b for any positive integers r and b is proved.

关 键 词：优美图 顶点标号 边标号 

分 类 号：O157.5[理学—数学]