RESEARCH ARTICLE

Two recursive inequalities for crossing numbers of graphs

  • Zhangdong OUYANG , 1 ,
  • Jing WANG 2 ,
  • Yuanqiu HUANG 3
Expand
  • 1. Department of Mathematics, Hunan First Normal University, Changsha 410205, China
  • 2. Department of Mathematics, Changsha University, Changsha 410003, China
  • 3. Department of Mathematics, Hunan Normal University, Changsha 410081, China

Received date: 29 Jul 2015

Accepted date: 28 Nov 2016

Published date: 20 Apr 2017

Copyright

2016 Higher Education Press and Springer-Verlag Berlin Heidelberg

Abstract

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 K1,3,nand K4,n\e are determined, respectively.

Cite this article

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

DOI

2
BondyJ A, MurtyU S R. Graph Theory with Applications. London: Macmillan Press Ltd, 1976

DOI

3
GareyM R, JohnsonD S. Crossing number is NP-complete. SIAM J Algebraic Discrete Methods, 1983, 4: 312–316

DOI

4
GroheM. Computing crossing number in quadratic time. In: Proceedings of the 33rd ACM Symposium on Theory of Computing STOC’01. 2001, 231–236

DOI

5
HliněnýP. Crossing number is hard for cubic graphs. J Combin Theory Ser B, 2006, 96: 455–471

DOI

6
KleitmanD J. The crossing number of K5,n.J Combin Theory, 1970, 9: 315–323

DOI

7
SzékelyL A. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math, 2004, 276: 331–352

DOI

Outlines

/