Degree-associated Reconstruction Parameters Of Some Graphs

The Reconstruction Conjecture of Ulam and Kelly has been open for more than 50 years, it asserts that every graph with at least three vertices is uniquely determined by its deck. In 1964, Harary proposed Edge-Reconstruction Conjecture, it states that every graph with more than three edges is determined by its edge-deck. These two conjectures have attracted many scholars to study. The conjecture has been proved for many special classes, nevertheless, the full conjecture remains open.In 1985, the reconstruction number of a graph G, introduced by Harary and Plan-tholt, is the minimum number of cards from the deck of G that suffice to determine G. A card is a subgraph of a graph G obtained by deleting one vertex. The multiset of cards is the deck of G. In 1988, Myrvold proposed the adversary reconstruction number, it is the least k such that every multiset of k cards G determines G. In 2001, Ramachandran introduced the degree-associated reconstruction number. In 2012, Monikandan et al introduced the degree-associated analogue of Myrvold’s adversary concept. Similarly, there are two kinds of edge-reconstruction parameters.In this master thesis, we study two kinds of degree-associated reconstruction(edge-reconstruction) numbers of some special graphs. We determine the adversary degree-associated reconstruction number of double-stars, the degree-associated reconstruction parameters of complete multipartite graphs and their complements, and the degree-associated edge-reconstruction parameters of corona graph P3 o Cm.In the first chapter, we introduce some definitions and give a brief survey of re- construction number of graphs. In the second chapter, we mainly determine the adver-sary degree-associated reconstruction number of double-stars. In the third chapter, we mainly determine the degree-associated reconstruction parameters of complete multi-partite graphs and their complements. In the fourth chapter, we mainly determine the degree-associated edge-reconstruction parameters of corona graph P3 o Cm.