点击次数：

论文类型：期刊论文

发表时间：2009-07-01

发表刊物：ARS COMBINATORIA

收录刊物：SCIE、Scopus

卷号：92

页面范围：397-409

ISSN号：0381-7032

关键字：crossing number; the k-th power of path; drawing; non-regular graph

摘要：Let P(n) be a path with n vertices P(n)(k) the k-th power of the path P(n), is a graph on the same vertex set as P(n) and the edges that join all vertices x and y if and only if the distance between them is at most k. In this paper, the crossing numbers of p(n)(k) are studied. Drawings of p(n)(k) are presented and proved to be optimal for the case n <= 8 and for the case k <= 4.