广西师范大学学报（自然科学版） ›› 2021, Vol. 39 ›› Issue (6): 112-118.doi: 10.16088/j.issn.1001-6600.2021012006

• 研究论文 • 上一篇    下一篇

一个6 阶图H与路Pn,圈Cn的联图的交叉数

周志东1,2, 翟莹1*, 罗正炎1   

  1. 1.广西师范大学 数学与统计学院, 广西 桂林 541006;
    2.衡阳师范学院 数学与统计学院, 湖南 衡阳 421002
  • 收稿日期:2021-01-20 修回日期:2021-04-01 出版日期:2021-11-25 发布日期:2021-12-08
  • 通讯作者: 翟莹(1980—), 女, 广西南宁人, 广西师范大学副教授。E-mail: zhaiying0773@sohu.com
  • 基金资助:
    国家自然科学基金(11301172); 广西自然科学基金(2019JJG110003); 湖南省科技计划项目(2016TP1020); 广西科技计划项目(2019AC20214)

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

PDF (PC)

127

摘要： 图的交叉数是表征图的一个重要参数, Garey 和Johnson 证明了确定图的交叉数是NP-完全问题。因为其难度, 目前能够确定交叉数的图类甚少。在Kleitman给出的完全二部图的交叉数cr(K6,n)=Z(6,n)的基础上,本文证明了一个6阶图H与n个孤立点nK1、Pn及Cn的联图交叉数分别为$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$和$c r\left(H+C_{n}\right)=Z(6, n)+2\left\lfloor\frac{n}{2}\right\rfloor$。

关键词: 画法, 交叉数, 联图, 路, 圈

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

中图分类号: 

  • 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] 田晟, 李成伟, 黄伟, 王蕾. 疫情下基于GC-rBPNN模型的公路货运量预测方法[J]. 广西师范大学学报（自然科学版）, 2021, 39(6): 24-32.
[2] 张顺生, 罗玉玲, 丘森辉. 面向AES密码硬件系统的马氏距离随机旁路攻击方法[J]. 广西师范大学学报（自然科学版）, 2021, 39(6): 33-43.
[3] 许伦辉, 林世城. 基于分治思想的扫地机器人全覆盖路径规划算法研究[J]. 广西师范大学学报（自然科学版）, 2021, 39(6): 54-62.
[4] 翁小雄, 谢志鹏. 基于多层复杂网络的高速公路节点重要性研究[J]. 广西师范大学学报（自然科学版）, 2021, 39(5): 78-88.
[5] 胡竣涛, 时小虎, 马德印. 基于均值漂移和遗传算法的护工调度算法[J]. 广西师范大学学报（自然科学版）, 2021, 39(3): 27-39.
[6] 钟丽明, 范江华. 凸向量优化问题弱有效解集的连通性[J]. 广西师范大学学报（自然科学版）, 2021, 39(3): 62-68.
[7] 李广, 徐保根, 张君霞. 两类图的Fractional控制数[J]. 广西师范大学学报（自然科学版）, 2021, 39(2): 112-118.
[8] 徐建闽, 杨招波, 马莹莹. 面向移动瓶颈的高速公路流量控制模型研究[J]. 广西师范大学学报（自然科学版）, 2020, 38(3): 1-10.
[9] 郭俊良, 薛飞, 刘璇, 侯蓉, 吴蔚, 黎大勇, 齐敦武, 张志和. 大熊猫双胞胎行为节律特征的研究[J]. 广西师范大学学报（自然科学版）, 2020, 38(1): 127-132.
[10] 许伦辉,黄宝山,钟海兴. AGV系统路径规划时间窗模型及算法[J]. 广西师范大学学报（自然科学版）, 2019, 37(3): 1-8.
[11] 许凯, 田晟, 朱泽坤. 短时事件下的地铁乘客路径选择行为研究[J]. 广西师范大学学报（自然科学版）, 2019, 37(2): 9-14.
[12] 胡郁葱, 陈栩, 罗嘉陵. 多起终点多车型混载的定制公交线路规划模型[J]. 广西师范大学学报（自然科学版）, 2018, 36(4): 1-11.
[13] 姜影星, 黄文念. 非线性薛定谔-麦克斯韦方程的基态解[J]. 广西师范大学学报（自然科学版）, 2018, 36(4): 59-66.
[14] 袁伟强,宋树祥,程 洋,张勇敢. 超宽带微带带通滤波器的设计[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 32-38.
[15] 张腾月,翁小雄. 基于收费数据的高速公路行程时间可靠性估计模型[J]. 广西师范大学学报（自然科学版）, 2016, 34(4): 70-77.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 胡锦铭, 韦笃取. 不同阶次分数阶永磁同步电机的混合投影同步[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 1 -8 .
[2] 武康康, 周鹏, 陆叶, 蒋丹, 闫江鸿, 钱正成, 龚闯. 基于小批量梯度下降法的FIR滤波器[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 9 -20 .
[3] 刘东, 周莉, 郑晓亮. 基于SA-DBN的超短期电力负荷预测[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 21 -33 .
[4] 张伟彬, 吴军, 易见兵. 基于RFB网络的特征融合管制物品检测算法研究[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 34 -46 .
[5] 王金艳, 胡春, 高健. 一种面向知识编译的OBDD构造方法[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 47 -54 .
[6] 逯苗, 何登旭, 曲良东. 非线性参数的精英学习灰狼优化算法[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 55 -67 .
[7] 李莉丽, 张兴发, 李元, 邓春亮. 基于高频数据的日频GARCH模型估计[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 68 -78 .
[8] 李松涛, 李群宏, 张文. 三自由度碰撞振动系统的余维二擦边分岔与混沌控制[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 79 -92 .
[9] 赵红涛, 刘志伟. λ重完全二部3-一致超图λK(3)n,n分解为超图双三角锥[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 93 -98 .
[10] 李梦, 曹庆先 , 胡宝清. 1960—2018年广西大陆海岸线时空变迁分析[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 99 -108 .
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发