On prime labellings
type: Item
instance of: scholarly article
title: On prime labellings
zbMATH Open document ID: 0802.05064
DOI: 10.1016/0012-365X(92)00477-9
author: Hung-Lin Fu
author: Kuo-Ching Huang
published in: Discrete Mathematics
publication date: 1994-12-01T00:00:00Z
review text: The paper is devoted to the study of prime graphs, that is finite graphs that admit a prime labelling. A prime labelling of a graph \(G=(V,E)\) is a bijection \(f: V\to \{1,2,\dots,| V|\}\) such that if \(e= \{u,v\}\in E\) then \(\text{GCD}(f(u),f(v))= 1\). Some results concerning bipartite graphs are obtained; all trees of order up to 15 are proved to be prime graphs. Such a result is a partial answer to the conjecture that all trees are prime graphs.
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 562629
zbMATH Keywords: prime graphs
zbMATH Keywords: prime labelling
zbMATH Keywords: bipartite graphs
zbMATH Keywords: trees
reviewed by: Antonio Andreatta
MaRDI profile type: Publication
cites work: Q3899969
cites work: Q3835502
cites work: Another Tree Labelling Problem
cites work: Q5776927
cites work: Q4194979
full work available at URL: 0012-365x(92)00477-9
OpenAlex ID: W2013161318
description: scientific article; zbMATH DE number 562629