Operations Research Transactions >
2016 , Vol. 20 >Issue 4: 115 - 126
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.04.014
On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n
Received date: 2016-02-29
Online published: 2016-12-15
The crossing numbers of a graph is a vital parameter and a hard problem in the forefront of topological graph theory. Determining the crossing number of an arbitrary graphs is NP-complete problem. Because of its difficultly, the classes of graphs whose crossing number have been determined are very scarce. In this paper, for the special graph Q on six vertices, we through the disk drawing method to prove that the crossing numbers of its join with n isolated vertices as well as with the path P_{n} and with the cycle C_{n} are cr(Q+nK_{1})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor, cr(Q+P_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+1 and cr(Q+C_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+3, respectively.
Key words: drawing; crossing number; disk drawing; joint graph; path; cycle
ZHOU Zhidong, LI Long . On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n[J]. Operations Research Transactions, 2016 , 20(4) : 115 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.014
/
| 〈 |
|
〉 |