Contents Online

# Journal of Combinatorics

## Volume 13 (2022)

### Number 1

### Supercards, sunshines and caterpillar graphs

Pages: 41 – 78

DOI: https://dx.doi.org/10.4310/JOC.2022.v13.n1.a3

#### 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 cards. The *number of common cards* $b(G, H)$ of $G$ and $H$ is the cardinality of the multiset intersection of the decks of $G$ and $H$. A *supercard* $G^+$ of $G$ and $H$ is a graph whose deck contains at least one card isomorphic to $G$ and at least one card 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 apply the theory of supercards and maximum saturating sets to the case when $G$ is a sunshine graph and $H$ is a caterpillar graph. We show that, for large enough $n$, there exists some maximum saturating set that contains at least $b(G, H)-2$ automorphisms of $G^+$, and that this subset is always isomorphic to either a cyclic or dihedral group. We prove that $b(G,H) \leq \frac{2(n+1)}{5}$ for large enough $n$, and that there exists a unique family of pairs of graphs that attain this bound. We further show that, in this case, the corresponding maximum saturating set is isomorphic to the dihedral group.

#### Keywords

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

Received 24 January 2019

Accepted 8 January 2021

Published 31 January 2022