ON PRIME LABELINGS

Abstract

Let G = (V, E) be a graph. A bijection f:V--> {1, 2,...,V} is called a prime labelling if for each e = {u, v} in E, we have GCD(f(u),f(v)) = 1. A graph admits a prime labelling is called a prime graph. Around ten years ago, Roger Entringer conjectured that every tree is prime. So far, this conjecture is still unsolved. In this paper, we show that the conjecture is true for trees of order up to 15, and also show that a few other classes of graphs are prime.