Stronger reconstruction of distance-hereditary graphs

Abstract

A graph is said to be set-reconstructible if it is uniquely determined up to isomorphism from the set S of its non-isomorphic one-vertex deleted unlabeled subgraphs. Harary’s conjecture asserts that every finite simple undirected graph on four or more vertices is set-reconstructible. A graph G is said to be distance-hereditary if for all connected induced subgraph F of G, dF (u, v) = dG(u, v) for every pair of vertices u, v ∈ V (F). In this paper, we have proved that the class of all 2-connected distance-hereditary graphs G with diam(G) = 2 or diam(G) = diam(Ḡ) = 3 are set-reconstructible.