图论中的第十五个难题

图论中关于“优美图”的研究课题是本世纪60年代提出来的,它一出现就引起了图论研究者们的极大兴趣,取得了不少成果,但至今仍未完全解决.J·A·Bondy 将它作为50个难题的第15个难题收列于“Graph Theory WithApplications”(有中译本)一书末。本文简明轭要地综述了近二十年来国内外的图论研究者们对 Golomb 问题——优美图的特征是什么?和 Rigel 猜想——所有树都是优美树,研究的进展情况及作者的个人心得。文后为广大读者提供了丰富的文献,并为刚开始从事优美图研究的人们指出了阅读的途径和一些研究课题。

The Fifteenth Poser in the Graph Theory

The problems of the exquisite graph in the graph theory were raised in the 1960's,which aroused the great interest of the students of the graph theory.Some problems remain unsolved though fruits have been yielded. The fifteenth in the graph theory appears at the end of S.A.Bondy's Graph Theory with Applications. The present article briefly summarizes the progress made by the gra- ph theory students at home and abroad in their nearly twenty years'resea- rches on the Golomb problem of what characterizes the exquisite graph and the Rigel supposition that all trees are exquisite trees.It also states the writer's personal understanding.The appendix provides the readers with ample documents and points out the way of reading and some research pro- blems for those who have just begun to study the exquisite graph.