Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 1

### A new approach to graph reconstruction using supercards

Pages: 95 – 118

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n1.a6

#### Authors

#### Abstract

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$ 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 $\mathrm{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 $\mathrm{Aut}(G^{+})$ are in one-to-one correspondence with a set of automorphisms of a different supercard $G^{+}_{\lambda}$ 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.

#### Keywords

graph reconstruction, reconstruction numbers, vertex-deleted subgraphs, supercards, graph automorphisms

Received 23 January 2015

Published 5 January 2018