Journal of Combinatorics

Volume 9 (2018)

Number 1

A new approach to graph reconstruction using supercards

Pages: 95 – 118

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

Authors

Paul Brown (Department of Computer Science and Information Systems, Birkbeck, University of London, United Kingdom)

Trevor Fenner (Department of Computer Science and Information Systems, Birkbeck, University of London, United Kingdom)

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

Full Text (PDF format)

Received 23 January 2015

Published 5 January 2018