点击次数：

论文类型：期刊论文

发表时间：2010-11-01

发表刊物：UTILITAS MATHEMATICA

收录刊物：SCIE、Scopus

卷号：83

页面范围：95-106

ISSN号：0315-3681

关键字：Prime labeling; Prime graph; Generalized Petersen graph

摘要：A graph G with vertex set V is said to have a prime labeling if its vertices can be labeled with distinct integers 1,2, ... , vertical bar V vertical bar such that for every edge xy in G, the labels assigned to x and y are relatively prime or coprime. A graph is called prime if it has a prime labeling. In this paper, we show that generalized Petersen graph P(n, 1) is not prime for odd n, prime for even n <= 2500, and conjecture that P(n, 1) is prime for all even n.