Prime Labelings

Graph theoretical properties of prime and super-prime graphs are listed. Entringerʹs prime tree conjecture is verified for all trees of order n < 15 using the construction of a class of tree-complete graphs. Towards the solution of Erdos question ‘What is the minimum number of edges in a non-prime graph?’, good upper bounds are obtained. More conjectures are proposed.