We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On the Crossing Number of K <sub> m </sub> □ P <sub> n </sub>.
- Authors
Zheng Wenping; Lin Xiaohui; Yang Yuansheng; Cui Chong
- Abstract
Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr( K m □ P n ), the crossing number of the Cartesian product K m □ P n . We prove that $$cr(K_{m} \square P_n)\leq \frac{1}{4}\lfloor\frac{m+1}{2}\rfloor\lfloor\frac{m-1}{2} \rfloor\lfloor\frac{m-2}{2}\rfloor(n\lfloor\frac{m+4}{2} \rfloor+ \lfloor\frac{m-4}{2}\rfloor)$$ for m ≥ 3, n ≥ 1 and cr( K m □ P n )≥ ( n − 1) cr( K m+2 − e) + 2 cr( K m+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr( K 6 □ P n ) = 15 n + 3.
- Subjects
COMPLETE graphs; PATH integrals; GRAPH theory; ALGEBRA; COMBINATORICS; TOPOLOGY
- Publication
Graphs & Combinatorics, 2007, Vol 23, Issue 3, p327
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-007-0726-z