Journal of Guangxi Normal University(Natural Science Edition) ›› 2021, Vol. 39 ›› Issue (6): 112-118.doi: 10.16088/j.issn.1001-6600.2021012006

Previous Articles     Next Articles

On the Crossing Numbers of the Joins of a Graph H on 6 Vertices with Path or Cycle

ZHOU Zhidong1,2, ZHAI Ying1*, LUO Zhengyan1   

  1. 1. School of Mathematics and Statistics, Guangxi Normal University, Guilin Guangxi 541006, China;
    2. College of Mathematics and Statistics, Hengyang Normal University, Hengyang Hunan 421002, China
  • Received:2021-01-20 Revised:2021-04-01 Online:2021-11-25 Published:2021-12-08

Abstract: The crossing numbers of a graph is a vital parameter. Garey and Johnson showed that the problem of determining the crossing numbers of an arbitrary graph is NP-complete. Because of its difficultly, the classes of graphs whose crossing numbers have been determined are very scarce at present. Based on the result of the crossing number of complete bipartite graph cr(K6,n)=Z(6,n) given by Kleitman, in this paper, for a 6-vertex graph H, it is shown that the crossing numbers of its join with n isolated vertices as well as the path Pn on n vertices and with the cycle Cn are $c r\left(H+n K_{1}\right)=Z(6, n)+2\left\lfloor\frac{n}{2}\right\rfloor$, $c r\left(H+P_{n}\right)=Z(6, n)+2\left\lfloor\frac{n}{2}\right\rfloor$, and $c r\left(H+C_{n}\right)=Z(6, n)+2\left\lfloor\frac{n}{2}\right\rfloor$.

Key words: drawing, crossing number, joint graph, path, cycle

CLC Number: 

  • O157.5
[1] BONDY J A, MURTY M S R. Graph theory with application[M]. North-Holland: Elsevier Science Ltd, 1976.
[2] KLEŠČ M. The join of graphs and crossing numbers[J]. Electronic Notes in Discrete Mathematics, 2007, 28: 349-355.
[3] TANG L, WANG J, HUANG Y Q. The crossing number of the join of Cn and Pn[J]. International Journal of Mathematical Combination, 2007, 11: 110-116.
[4] BHATT S N, LEIGHTON F T. A framework for solving VLSI graph layout problems[J]. Journal of Computer and System Sciences, 1984, 28: 300-343.
[5] LEIGHTON F T. New lower bound techniques for VLSI[J]. Mathematics System Theory, 1984, 17: 47-70.
[6] SZEKELY L A. Crossing numbers and hard Erdos problems in discrete geometry[J]. Combinatorics,Probability and Computing, 1997, 6: 353-358.
[7] GAREY M R. JOHNSON D S. Crossing number is NP-complete[J]. SIAM Journal of Algebric Discrete Mathematics, 1993, 4: 312-316.
[8] BOKAL D. On the crossing numbers of Cartesian products with paths[J]. Journal of Combinatorial Theory (Series B), 2007, 97: 381-384.
[9] KLEŠČ M. The crossing numbers of Cartesian products of paths with 5-vertex graphs[J]. Discrete Mathematics, 2001, 233: 353-359.
[10] MA D J, REN H, LU J J. The crossing numbers of the circular graph C(2m+2, m)[J]. Discrete Mathematics, 2005, 304: 88-93.
[11] 马祖强, 蔡俊亮. W5×Sn的交叉数[J]. 应用数学学报, 2008, 31(4): 615-623.
[12] YANG Y S, LIN X H, LU J, et al. The crossing numbers of C(n; {1, 3})[J]. Discrete Mathematics, 2004, 289: 107-118.
[13] OPOROWSKI B, ZHAO D. Coloring graphs with crossings[J]. Discrete Mathematics, 2009, 309: 2948-2951.
[14] KLEŠČ M. The crossing numbers of products of paths and stars with 4-vertex graphs[J]. Journal of Graph Theory, 1994, 6: 605-614.
[15] 苏振华, 黄元秋. 五阶图与路Pn的联图的交叉数[J]. 高校应用数学学报, 2014, 29(2): 245-252.
[16] 李敏. 一个5阶图与点, 路, 圈联图的交叉数[J]. 扬州大学学报(自然科学版), 2015,18(1): 4-8.
[17] 李丽萍. 一个五阶图与路, 圈的联图的交叉数[J]. 数学的实践与认识, 2014, 44(11): 203-211.
[18] KLEŠČ M. The crossing numbers of join of the special graph on six vertices with path and cycle[J]. Discrete Mathematics, 2010, 310: 1475-1481.
[19] 周志东, 黄元秋,彭小多,等. 一个小图与路和圈的联图的交叉数[J]. 系统科学与数学, 2013, 33(2): 206-216.
[20] 周志东, 吕胜祥. 关于一个特殊六阶图与路和圈的联图的交叉数[J]. 数学进展, 2014, 43(1): 69-80 .
[21] 王晶, 欧阳章东, 黄元秋. 关于交叉数为1的联图[J]. 应用数学学报, 2017, 40(5):727-733.
[22] 王晶, 张作政, 黄元秋. 关于交叉数为2的联图[J]. 数学进展, 2019, 48(4): 497-503.
[1] XU Lunhui, LIN Shicheng. Research on Full Coverage Path Planning Algorithm of Sweeping Robot Based on Divide and Conquer [J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(6): 54-62.
[2] HU Juntao, SHI Xiaohu, MA Deyin. Nursing Workers Scheduling Based on Mean Shift and Genetic Algorithm [J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(3): 27-39.
[3] ZHONG Liming, FAN Jianghua. Connectedness of Weakly Effective Solution Sets for Convex Vector Optimization Problems [J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(3): 62-68.
[4] JIANG Pinqun, GU Shen, SONG Shuxiang, CEN Mingcan. Harmonic Analysis and Anti-aliasing Research of N-path Band-stop Filter [J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(2): 81-89.
[5] LIU Shili, ZHU Xiaohu, LIU Li, FANG Tianrui. Life Cycle Cost Estimation of 110 kV GIS Substation in Anhui Based on Fuzzy Theory [J]. Journal of Guangxi Normal University(Natural Science Edition), 2020, 38(5): 24-33.
[6] LÜ Xiaojun, ZHAO Kaihong, LI Rui. Multiple Positive Periodic Solutions of a Discrete Non-autonomousPlankton Allelopathy System [J]. Journal of Guangxi Normal University(Natural Science Edition), 2020, 38(4): 66-73.
[7] ZHANG Erli, XING Yuqing. Bifurcation of Limit Cycle for Non-Hamilton System with Invariant Straight Lines [J]. Journal of Guangxi Normal University(Natural Science Edition), 2020, 38(3): 45-51.
[8] LI Zhanyong, JIANG Guirong. Some New Results on Lyapunov-branch Theorem [J]. Journal of Guangxi Normal University(Natural Science Edition), 2020, 38(2): 128-133.
[9] XIE Lina, JIANG Pinqun, SONG Shuxiang, CEN Mingcan. A Low-Loss, Low-Noise, Wide-Tuned High-Order Cascade N-Path Filter [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(4): 37-44.
[10] HE Dongping,HUANG Wentao ,WANG Qinlong. Limit Cycle Flutter and Chaostic Motion of Two-Dimensional Airfoil System [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(3): 87-95.
[11] XU Lidan, ZHAO Min, LI Meilin, ZENG Chen, MO Xiuyu, LIU Meina, ZHU Pingchuan, HE Yongqiang. Comparative Study on Basic Phenotypes and Chemotaxis of the Two Pathovars of Xanthomonas oryzae [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(2): 179-187.
[12] XU Yuanjing, HU Weiping. Identification of Pathological Voice of Different Levels Based on Random Forest [J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(4): 34-41.
[13] MA Yuqing, WU Zhuoling,HUO Minyao, YANG Liu. LMNA Mutation Result in the Structural and FunctionalAbnormal of Nuclear Envelope [J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(4): 122-126.
[14] HU Yucong, CHEN Jie, ZOU Xiaojian, CHEN Zhiwei. Research on Mode Choice of Electric Bicycle Travelers Basedon Two-Step Cluster Method [J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(3): 22-29.
[15] WEI Yangjiang, LIANG Yiyao, TANG Gaohua, SU Leilei, CHEN Weining. Cubic Mapping Graphs on the Quotient Ringsof the Gaussian Integer Rings of Modulo n [J]. Journal of Guangxi Normal University(Natural Science Edition), 2016, 34(3): 53-61.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] HU Jinming, WEI Duqu. Hybrid Projective Synchronization of Fractional-order PMSM with Different Orders[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 1 -8 .
[2] WU Kangkang, ZHOU Peng, LU Ye, JIANG Dan, YAN Jianghong, QIAN Zhengcheng, GONG Chuang. FIR Equalizer Based on Mini-batch Gradient Descent Method[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 9 -20 .
[3] LIU Dong, ZHOU Li, ZHENG Xiaoliang. A Very Short-term Electric Load Forecasting Based on SA-DBN[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 21 -33 .
[4] ZHANG Weibin, WU Jun, YI Jianbing. Research on Feature Fusion Controlled Items Detection Algorithm Based on RFB Network[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 34 -46 .
[5] WANG Jinyan, HU Chun, GAO Jian. An OBDD Construction Method for Knowledge Compilation[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 47 -54 .
[6] LU Miao, HE Dengxu, QU Liangdong. Grey Wolf Optimization Algorithm Based on Elite Learning for Nonlinear Parameters[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 55 -67 .
[7] LI Lili, ZHANG Xingfa, LI Yuan, DENG Chunliang. Daily GARCH Model Estimation Using High Frequency Data[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 68 -78 .
[8] LI Songtao, LI Qunhong, ZHANG Wen. Co-dimension-two Grazing Bifurcation and Chaos Control of Three-degree-of-freedom Vibro-impact Systems[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 79 -92 .
[9] ZHAO Hongtao, LIU Zhiwei. Decompositions of λ-fold Complete Bipartite 3-uniform Hypergraphs λK(3)n,n into Hypergraph Triangular Bipyramid[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 93 -98 .
[10] LI Meng, CAO Qingxian, HU Baoqing. Spatial-temporal Analysis of Continental Coastline Migration from 1960 to 2018 in Guangxi, China[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(4): 99 -108 .