Algorithm for Reconstruction Number of Split Graphs

A card \(G-v\) of a graph G is obtained by deleting the vertex v and all edges incident with v. The multiset of all cards of G is called the deck of G. A graph is reconstructible if it is determined up to isomorphism from the collection of all its cards. The Reconstruction Conjecture asserts that all graphs of order at least three are reconstructible. The minimum number of cards of G that do not belong to the deck of any graph not isomorphic to G is called the reconstruction number of G. A split graph is a graph in which the vertices can be partitioned into an independent set and a clique. In this paper, we prove that the degree sequence of a split graph G can be found by using some six cards of G. We give an algorithm to find the reconstruction number of split graphs G which uses only six cards of G for most of the cases.