Graphs with n-3 isomorphic vertex-deleted subgraphs and their reconstructibility

Abstract

A vertex-deleted subgraph (or card) G - v of a graph G is obtained from G by deleting the vertex v and all edges incident with v. We prove that a connected graph G on n vertices with at least n-3 of its cards isomorphic is either regular or bidegreed or belongs to one of six mutually disjoint families of T-graphs (where T-graph is a graph which is neither regular nor bidegreed). We use this to prove that such graphs are reconstructible.