Frontiers of Mathematics in China >
Two recursive inequalities for crossing numbers of graphs
Received date: 29 Jul 2015
Accepted date: 28 Nov 2016
Published date: 20 Apr 2017
Copyright
In this paper, two recursive inequalities for crossing numbers of graphs are given by using basic counting method. As their applications, the crossing numbers of and are determined, respectively.
Key words： Graph; drawing; crossing number; recursive inequality
Zhangdong OUYANG , Jing WANG , Yuanqiu HUANG . Two recursive inequalities for crossing numbers of graphs[J]. Frontiers of Mathematics in China, 2017 , 12(3) : 703 -709 . DOI: 10.1007/s11464-016-0618-8
| 1 |
AsanoK. The crossing number of K1,3,n and K2,3,n.J Graph Theory, 1980, 10: 1–8
|
| 2 |
BondyJ A, MurtyU S R. Graph Theory with Applications. London: Macmillan Press Ltd, 1976
|
| 3 |
GareyM R, JohnsonD S. Crossing number is NP-complete. SIAM J Algebraic Discrete Methods, 1983, 4: 312–316
|
| 4 |
GroheM. Computing crossing number in quadratic time. In: Proceedings of the 33rd ACM Symposium on Theory of Computing STOC’01. 2001, 231–236
|
| 5 |
HliněnýP. Crossing number is hard for cubic graphs. J Combin Theory Ser B, 2006, 96: 455–471
|
| 6 |
KleitmanD J. The crossing number of K5,n.J Combin Theory, 1970, 9: 315–323
|
| 7 |
SzékelyL A. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math, 2004, 276: 331–352
|
/
| 〈 |
|
〉 |