Graphs and Combinatorics Discrete Mathematics and Combinatorics
Prime Sum Graphs and the Induced Trees They Contain
Abstract
Abstract In this paper we show that prime sum graphs on n vertices – which are graphs on vertex set $$\{1,2, \dots ,n\}$$ { 1 , 2 , ⋯ , n } where ij is an edge when $$i+j$$ i + j is prime – contain all trees with at most $$\exp ( c \log n / \log \log n)$$ 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.