A polynomial time algorithm recognizing link trees

The link of a vertex v of a graph G is the subgraph induced by all vertices adjacent to v. If all the links of G are isomorphic to a finite graph L, then G is called a realization of L, and L is called a link graph. At the Smolenice symposium of 1963, Zykov posed the problem of recognizing link graphs. There are two versions of that problem, namely the finite (the existence of a finite realization is required) and the infinite one. Bulitko (see “On Graphs with Prescribed Links of Vertices” in Russian], Trudy mat. inst. im. Steklova, Vol. 133, 1973, pp. 78-94) proved that the infinite version is algorithmically unsolvable. The solution of both versions is known only for special classes of graphs as paths, cycles, and graphs homeomorphic to a star (see M. Brown and R. Connelly, “On Graphs with a Constant Link I,” New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 19-51; On Graphs with a Constant Link II, Discrete Mathematics, Vol. 11, 1975, pp. 199-232). The finite version for trees with less than 10 vertices has been solved by Blass, Harary, and Miller (see “Which Trees Are Link Graphs?” Journal of Combinatorics Theory Series B, Vol. 29, 1980, pp. 277-292). Trees that are link graphs are called link trees. Using some previous results of Bulitko (see “On a Recursive Property of Block-Complete Graphs” in Russian], Proceedings of Czechoslovak Conference on Graphs, Zemplínska ?irava, 1978, p. 20-30), we present a polynomial time algorithm recognizing link trees. The applied methods have some remarkable consequences concerning the study of link graphs. © 1995 John Wiley & Sons, Inc.