Hits:

Indexed by:期刊论文

Date of Publication:2009-07-01

Journal:ARS COMBINATORIA

Included Journals:SCIE、Scopus

Volume:92

Page Number:397-409

ISSN No.:0381-7032

Key Words:crossing number; the k-th power of path; drawing; non-regular graph

Abstract: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.