Families of pairs of graphs with a large number of common cards

The vertex-deleted subgraph G−v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex-deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n ≥ 4 that have at least equation image common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have equation image common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of n≥10. We also present infinite families of pairs of forests and pairs of trees with equation image and equation image common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree