Graphs of diameter three are recognizable

Abstract

A vertex-deleted subgraph (or card ) G − v of a graph G is the unlabelled subgraph obtained from G by deleting the vertex v and all edges incident with v . The collection of all cards of G is the deck of G . A graph H is a reconstruction of G if H has the same deck as G . A graph is said to be reconstructible if it is isomorphic to all its reconstructions. A family F of graphs is recognizable if, for each G ∈ F , every reconstruction of G is also in F . In this paper, it is shown that the family of all graphs of diameter three is recognizable.