On prime labellings

Hung-Lin Fu*, Kuo Ching Huang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


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.

Original languageEnglish
Pages (from-to)181-186
Number of pages6
JournalDiscrete Mathematics
Issue number1-3
StatePublished - 15 Mar 1994

Fingerprint Dive into the research topics of 'On prime labellings'. Together they form a unique fingerprint.

Cite this