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 -