一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数

doi:10.15960/j.cnki.issn.1007-6093.2016.04.014

Abstract

Abstract:

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

Cite this article

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, doi: 10.15960/j.cnki.issn.1007-6093.2016.04.014.

share this article

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2016.04.014

https://www.ort.shu.edu.cn/EN/Y2016/V20/I4/115

References

[1] Kle\v{s}\v{c} M. The join of graphs and crossing numbers [J]. Electronic Notes in Discrete Mathematics, 2007, 28: 349-355.

[2] Tang L, Wang J, Huang Y Q. The crossing number of the join of C_{n} and P_{n} [J]. International Journal of Mathematical Combinatorics, 2007, 11: 110-116.

[3] Bondy J A, Murty U S R. Graph Theory with Applications} [M]. {Great Britain: The Macmillan Press Ltd, 1976, 135.

[4] Garey M R, Johnson D S. Crossing number is NP-complete [J]. SIAM Journal on Algebraic Discrete Methods, 1993, 4: 312-316.

[5] Woodall D R. Cyclic-order graphs an Zarankiewicz's crossing number conjecture [J]. Journal of Graph Theory, 1993, 17(6): 657-671.

[6] 苏振华, 黄元秋. 五阶图与路 P_{n} 的联图的交叉数 [J]. 高校应用数学学报, 2014, 29(2): 245-252.

[7] 李敏. 一个 5 阶图与点, 路, 圈联图的交叉数 [J]. 扬州大学学报 (自然科学版}), 2015, 18(1): 4-8.

[8] 李丽萍. 一个五阶图与路, 圈的联图的交叉数 [J]. 数学的实践与认识, 2014, 44(11): 203-211.

[9] 周志东, 黄元秋等. 一个小图与路和圈的联图的交叉数 [J]. 系统科学与数学, 2013, 33(2): 206-216.

[10] Kle\v{s}\v{c} M. The crossing numbers of join of the special graph on six vertices with path and cycle [J]. Discrete Mathematics, 2010, 310: 1475-1481.

[11] 周志东, 吕胜详. 关于一个特殊六阶图与路和圈的联图的交叉数 [J]. 数学进展, 2014, 43(1): 69-80.

Related Articles 15

[1]	TIAN Shuangliang, YANG Huan, SUOLANG Wangqing, YANG Qing. Neighbor sum distinguishing edge coloring of the lexicographic product of paths [J]. Operations Research Transactions, 2020, 24(1): 140-146.
[2]	SUN Guanglei, LI Xiaoshen, SHANG Youlin. Optimal production ordering policy for an integrated supply chain with time varying demand [J]. Operations Research Transactions, 2019, 23(4): 143-154.
[3]	LIU Yan, LEI Mengxia, HUANG Xiaoxian. Path-transformation graph of maximum matchings [J]. Operations Research Transactions, 2019, 23(2): 104-112.
[4]	LUO Zhaoyang, SUN Lin. The linear aboricity of planar graphs with 6-cycles containing at most one chord [J]. Operations Research Transactions, 2019, 23(2): 113-119.
[5]	CHEN Hongyu, TAN Xiang. An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles [J]. Operations Research Transactions, 2019, 23(1): 104-110.
[6]	LV Xuezheng, WEI Erling, SONG Hongye. The basis number of join graphs [J]. Operations Research Transactions, 2018, 22(4): 148-152.
[7]	SU Zhenhua. The crossing number of the join product of C_6+3K_2 with P_n and C_n [J]. Operations Research Transactions, 2017, 21(3): 23-34.
[8]	HE Zhiquan. Simulation of value of CM strategy multi-period return guarantee under asset jump [J]. Operations Research Transactions, 2017, 21(1): 87-102.
[9]	HAN Shilian. An extended label correcting method for the SUM-MIN bi-criterion path problem in logistics transportation network [J]. Operations Research Transactions, 2016, 20(3): 121-128.
[10]	LIU Changhe, SHANG Youlin, LI Jinrui. Path-following interior point algorithms based on wide neighborhoods and a new class of directions [J]. Operations Research Transactions, 2016, 20(1): 43-53.
[11]	GUAN Meigu. A historical review on the research and development [J]. Operations Research Transactions, 2015, 19(3): 1-7.
[12]	SUN Lin, LUO Zhaoyang. Edge colourings of embedded special graphs [J]. Operations Research Transactions, 2015, 19(1): 125-130.
[13]	HE Shengxue. Determining optimal routes for transit vehicles in no-notice emergency evacuation [J]. Operations Research Transactions, 2014, 18(3): 47-59.
[14]	DING Lushun, WANG Guanghui, YAN Jin. The properly colored paths and cycles for the triangle-free graphs [J]. Operations Research Transactions, 2014, 18(3): 116-120.
[15]	YU Guidong, ZHANG Chao, GONG Qijuan. Energy and Hamiltonicity of graphs [J]. Operations Research Transactions, 2014, 18(2): 40-48.

Metrics

Viewed

Full text

Abstract

Comments

Abstract
References
Related Articles
Recommended Articles
Metrics
Comments

TOP

On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n

PDF

Knowledge