TY - JOUR

T1 - On prime labellings

AU - Fu, Hung-Lin

AU - Huang, Kuo Ching

PY - 1994/3/15

Y1 - 1994/3/15

N2 - 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{script})) = 1. A graph admits a prime labelling is called a prime graph. Around ten years ago, Roger Entriger 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.

AB - 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{script})) = 1. A graph admits a prime labelling is called a prime graph. Around ten years ago, Roger Entriger 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.

UR - http://www.scopus.com/inward/record.url?scp=38149148516&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(92)00477-9

DO - 10.1016/0012-365X(92)00477-9

M3 - Article

AN - SCOPUS:38149148516

VL - 127

SP - 181

EP - 186

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -