Adversary-reconstruction of trees : the case of caterpillars and sunshine graphs

Abstract

The reconstruction conjecture is one of the foremost unsolved problems in Graph Theory. In an effort to solve this problem, graph theorists work on variants to this problem as well as on particular classes of graphs. A graph G is said to be k- adversary-reconstructible if no k-subset of the deck of G is a subset of the deck of any graph which is not isomorphic to G. The smallest value of k for which G is k- adversary-reconstructible is called the adversary-reconstruction number of G, Adv-rn(G). In this dissertation, adversary weak-reconstruction of a special tree called a caterpillar is considered. It is found that the number of cards in common between a caterpillar and a special unicyclic graph called a sunshine graph is at most n+3 10 • This means that at most n+3 10 + 1 caterpillar cards are needed to distinguish between a caterpillar and a sunshine graph. An algorithm for the adversary weak-reconstruction of caterpillars is devised, needing only three caterpillar leg cards. Finally a brief look at the edge reconstruction problem for caterpillars is taken.