The graph reconstruction conjecture: some new results and observations

Shuva, Amitesh Saha (2015) The graph reconstruction conjecture: some new results and observations. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (299kB)

Abstract

A vertex-deleted subgraph (or simply a card) of graph G is an induced subgraph of G containing all but one of its vertices. The deck of G is the multiset of its cards. One of the best-known unanswered questions of graph theory asks whether G can be reconstructed in a unique way (up to isomorphism) from its deck. The likely positive answer to this question is known as the Reconstruction Conjecture. In the first part of the thesis two basic equivalence relations are considered on the set of vertices of the graph G to be reconstructed. The one is card equivalence, better known as removal equivalence, by which two vertices are equivalent if their removal results in isomorphic cards. The other equivalence is similarity, also called automorphism equivalence. Two vertices u and v are automorphism-equivalent (similar) if there exists an automorphism of G taking u to v. These relations are analyzed on various examples with special attention to vertices that are card-equivalent but not similar. Such vertices are called pseudo-similar, and they have been studied very extensively in the literature. The first result of the thesis is a structural characterization of card equivalence in terms of automorphism equivalence. A similar result was obtained by Godsil and Kocay in 1982 on the characterization of pseudosimilar vertices, which result is proved in the thesis as a corollary to the characterization theorem on card equivalence. In the second part of the thesis, the concept of relative degree-sequence is introduced for subgraphs of a graph G. By “relative” it is meant that each degree in the degree-sequence of the subgraph is coupled up with the original degree of the corresponding vertex in G. A new conjecture is formulated, which says that G is uniquely determined (up to isomorphism) by the multiset of the relative degree-sequences of its induced subgraphs. The new conjecture is then related to the Reconstruction Conjecture in a natural way. The third part of the thesis contains an original new result on graph reconstruction. Card-minimal graphs are investigated, the deck of which is a set. Thus, the deck of such graphs is free from duplicate cards. It is shown that every card-minimal graph G is reconstructible, provided that G does not have pseudo-similar couples of vertices. This condition is recognizable, that is, it can be checked by looking at the deck of G only. The results of this thesis have been partially published in [1].

Actions (login required)

View Item