Prime sum graphs and the induced trees they contain

Abstract

In this paper we show that prime sum graphs on $n$ vertices -- which are graphs on vertex set $\{1,2,...,n\}$ where $ij$ is an edge when $i+j$ is prime -- contain all trees with at most $\exp (c\log n/\log \log n)$ vertices as induced subgraphs. We also prove some results for related graphs, and end with some unsolved problems.

This was part of an undergrad research project that Patrick did with me last year