STRONGER RECONSTRUCTION OF DISTANCE-HEREDITARY GRAPHS

STRONGER RECONSTRUCTION OF DISTANCE-HEREDITARY GRAPHS

P. Devi Priya, S. Monikandan

[PDF]

Abstract

Agraphissaidtobeset-reconstructibleifitisuniquelydetermineduptoiso- morphism 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 ver- tices is set-reconstructible. A graph G is said to be distance-hereditary if for all connected inducedsubgraphF ofG, dF(u,v)=dG(u,v)foreverypairofverticesu,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(G) = 3 are set-reconstructible.

Keywords

Set-reconstruction, connectivity, distance, distance-hereditary