WHICH TREES ARE UNIQUELY FRAMED BY THE HEAWOOD GRAPH?

Abstract

A graph F is called a frame of a graph G if F is a graph of minimum order having the property that for every vertex x of G and every vertex y of F, there exists and embedding of G in F as an induced subgraph with x at y. We determine all those trees having the Heawood graph, the unique 6-cage, as their frame. It is shown that there are at most three trees for which the Heawood graph is the unique frame.