路图与线图的一个综述

线图的概念最早是由Whitney提出的,在所有图的变换中,线图可能是研究最广泛的一种变换了。关于线图的研究已经有很多结果,路图变换是线图的一种自然推广。在这篇综述中,我们可以看到有时路图与线图的性质差异很大,有些问题对路图而言变得相当复杂和困难。这篇文章主要通过以下几个方面比较和总结了路图与线图的一些结果:基本事实,判定问题,刻画问题,贯穿性,连通度。

Path Graphs Versus Line Graphs-A Survey

The line graph transformation may be the most widely studied one among all graph trans- formations,the concept of which was first introduced by Whitney.Many results on this topic have been published in various journal papers.The path graph transformation is a natural and interesting generalization of line graph transformation.As one will see in this survey,properties of path graphs are sometimes very different from those of line graphs. Some problems become very complicated and substantially difficult for path graphs.In this paper,we will survey results on path graphs versus line graphs.We classify the results into the following categories:some basic facts,determination problem,characterization prob- lem,traversability,connectivity.For results not in these categories,we skip them because of the space limitation.