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, \dots ,n\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> where ij is an edge when $$i+j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>+</mml:mo> <mml:mi>j</mml:mi> </mml:mrow> </mml:math> is prime – contain all trees with at most $$\exp ( c \log n / \log \log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>exp</mml:mo> <mml:mo>(</mml:mo> <mml:mi>c</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> vertices as induced subgraphs. We also prove some results for related graphs, and end with some unsolved problems.