Graphs and Combinatorics Discrete Mathematics and Combinatorics

Prime Sum Graphs and the Induced Trees They Contain

Ernie Croot, Patrick Jin
Springer Nature · 2025-12-21 · DOI 10.1007/s00373-025-02999-2

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.

Read at publisher →