Two recursive inequalities for crossing numbers of graphs

doi:10.1007/s11464-016-0618-8

Front. Math. China

2017, Vol. 12

Issue (3) : 703-709 https://doi.org/10.1007/s11464-016-0618-8

RESEARCH ARTICLE

Two recursive inequalities for crossing numbers of graphs

Zhangdong OUYANG¹(

), Jing WANG², Yuanqiu HUANG³

¹. Department of Mathematics, Hunan First Normal University, Changsha 410205, China
². Department of Mathematics, Changsha University, Changsha 410003, China
³. Department of Mathematics, Hunan Normal University, Changsha 410081, China

Download: PDF(119 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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 $K 1, 3, n$ and $K 4, n \ e$ are determined, respectively.

Keywords Graph drawing crossing number recursive inequality

Corresponding Author(s): Zhangdong OUYANG

Issue Date: 20 April 2017

Cite this article:

Zhangdong OUYANG,Jing WANG,Yuanqiu HUANG. Two recursive inequalities for crossing numbers of graphs[J]. Front. Math. China, 2017, 12(3): 703-709.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-016-0618-8
https://academic.hep.com.cn/fmc/EN/Y2017/V12/I3/703

1	AsanoK. The crossing number of K1,3,n and K2,3,n.J Graph Theory, 1980, 10: 1–8 https://doi.org/10.1002/jgt.3190100102
2	BondyJ A, MurtyU S R. Graph Theory with Applications. London: Macmillan Press Ltd, 1976 https://doi.org/10.1007/978-1-349-03521-2
3	GareyM R, JohnsonD S. Crossing number is NP-complete. SIAM J Algebraic Discrete Methods, 1983, 4: 312–316 https://doi.org/10.1137/0604033
4	GroheM. Computing crossing number in quadratic time. In: Proceedings of the 33rd ACM Symposium on Theory of Computing STOC’01. 2001, 231–236 https://doi.org/10.1145/380752.380805
5	HliněnýP. Crossing number is hard for cubic graphs. J Combin Theory Ser B, 2006, 96: 455–471 https://doi.org/10.1016/j.jctb.2005.09.009
6	KleitmanD J. The crossing number of K5,n.J Combin Theory, 1970, 9: 315–323 https://doi.org/10.1016/S0021-9800(70)80087-4
7	SzékelyL A. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math, 2004, 276: 331–352 https://doi.org/10.1016/S0012-365X(03)00317-0

[1]	Wen-Huan WANG, Ling YUAN. Uniform supertrees with extremal spectral radii[J]. Front. Math. China, 2020, 15(6): 1211-1229.
[2]	Yizheng FAN, Zhu ZHU, Yi WANG. Least H-eigenvalue of adjacency tensor of hypergraphs with cut vertices[J]. Front. Math. China, 2020, 15(3): 451-465.
[3]	Hongmei YAO, Li MA, Chunmeng LIU, Changjiang BU. Brualdi-type inclusion sets of Z-eigenvalues and l^k,s-singular values for tensors[J]. Front. Math. China, 2020, 15(3): 601-612.
[4]	Xin LI, Jiming GUO, Zhiwen WANG. Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)[J]. Front. Math. China, 2019, 14(6): 1213-1230.
[5]	Lihua YOU, Xiaohua HUANG, Xiying YUAN. Sharp bounds for spectral radius of nonnegative weakly irreducible tensors[J]. Front. Math. China, 2019, 14(5): 989-1015.
[6]	Kinkar Chandra DAS, Huiqiu LIN, Jiming GUO. Distance signless Laplacian eigenvalues of graphs[J]. Front. Math. China, 2019, 14(4): 693-713.
[7]	Thomas BRÜSTLE, Jie ZHANG. Non-leaving-face property for marked surfaces[J]. Front. Math. China, 2019, 14(3): 521-534.
[8]	Ziqiu LIU, Yunfeng ZHAO, Yuqin ZHANG. Perfect 3-colorings on 6-regular graphs of order 9[J]. Front. Math. China, 2019, 14(3): 605-618.
[9]	Jun HE, Yanmin LIU, Junkang TIAN, Xianghu LIU. Upper bounds for signless Laplacian Z-spectral radius of uniform hypergraphs[J]. Front. Math. China, 2019, 14(1): 17-24.
[10]	Xiaoxiao ZHANG, Aijin LIN. Positive solutions of p-th Yamabe type equations on graphs[J]. Front. Math. China, 2018, 13(6): 1501-1514.
[11]	Xiaofeng XUE. Phase transition for SIR model with random transition rates on complete graphs[J]. Front. Math. China, 2018, 13(3): 667-690.
[12]	Zhihe LIANG. *Super (a, d)-edge-antimagic total labelings of complete bipartite graphs*[J]. Front. Math. China, 2018, 13(1): 129-146.
[13]	Xiying YUAN, Xuelian SI, Li ZHANG. Ordering uniform supertrees by their spectral radii[J]. Front. Math. China, 2017, 12(6): 1393-1408.
[14]	Dongmei CHEN, Zhibing CHEN, Xiao-Dong ZHANG. Spectral radius of uniform hypergraphs and degree sequences[J]. Front. Math. China, 2017, 12(6): 1279-1288.
[15]	Shiying WANG, Zhenhua WANG, Mujiangshan WANG, Weiping HAN. *g-Good-neighbor conditional diagnosability of star graph networks under PMC model and MM model**[J]. Front. Math. China, 2017, 12(5): 1221-1234.

Viewed

Full text

Abstract

Cited

Shared

Discussed