On the Maximum Number of Common Cards between Various Classes of Graphs
Paul H. Brown · 2008
On the Maximum Number of Common Cards between Various Classes of Graphs The Reconstruction Conjecture is one of the foremost unsolved problems in graph theory. It conjectures that a graph can be uniquely determined, up to isomorphism, by its collection of unlabelled vertex-deleted subgraphs (called its deck of cards). Like many mathematical problems, its appeal lies in the simplicity of its hypothesis and its accessibility to non-experts. However, although many graph theorists have tried to resolve the status of conjecture, it is still an open problem. Since the conjecture has remained unresolved, attention has focused on related reconstruction problems. One such area is the study of the two reconstruction numbers of some particular graph G: the existential reconstruction number rn(G), defined to be the minimum k such that there exists k cards from which G can be reconstructed, and the universal reconstruction number urn(G), defined to be the minimum k such that G can be reconstructed from any k cards. Most work on reconstruction numbers yet published concerns rn(G). This thesis instead focusses on urn(G) and will be one of the first to contain substantial results on this topic. urn(G) can also be studied in terms of the maximum number of common cards that G can have with any other graph, and that is the approach that we take. We find upper bounds for the maximum number of common cards between pairs of graphs in various classes and, in all cases, we show that these bounds can be attained by infinite families. Moreover, we completely characterise the families of pairs of graphs that attain the bounds. In doing so, we present many families of graph pairs with different values on various parameters that have, by far, the largest number of common cards yet published.