The Crossing Numbers of Products of Path with Graphs of Order Six

Discussiones Mathematicae Graph Theory

Klešč Marián¹  Petrillová Jana¹ 

[1] Faculty of Electrical Engineering and Informatics Technical University of Košice Letná 9, 042 00 Košice, Slovak Republic;

关键词: graph;    drawing;    crossing number;    cartesian product;    path;    tree;   

DOI  :  10.7151/dmgt.1684

来源: DOAJ

【 摘 要 】

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian product H⃞Pn is 2(n − 1). In addition, the crossing numbers of G⃞Pn for fourty graphs G on six vertices are collected

【 授权许可】

Unknown