A new approach to graph reconstruction using supercards

摘要

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 vertexdeleted subgraphs. The number of common cards of G and H is the cardinality of a maximum multiset of common cards, i.e., the multiset intersection of the decks of G and H. We introduce a new approach to the study of common cards using supercards, where we define a supercard G~+ of G and H to be a graph that has at least one vertex-deleted subgraph isomorphic to G, and at least one isomorphic to H. We show how maximum sets of common cards of G and H correspond to certain sets of permutations of the vertices of a supercard, which we call maximum saturating sets. We then show how to construct supercards of various pairs of graphs for which there exists some maximum saturating set X contained in Aut(G~+). For certain other pairs of graphs, we show that it is possible to construct G~+ and a maximum saturating set X such that the elements of X that are not in Aut(G~+) are in oneto- one correspondence with a set of automorphisms of a different supercard G_λ~+ of G and H. Our constructions cover nearly all of the published families of pairs of graphs that have a large number of common cards.