若干典型图类的交叉数及其相关问题研究

若干典型图类的交叉数及其相关问题研究

论文摘要

图的交叉数是图的一个经典的拓扑不变量,形象地说,它是衡量一个图离平面图有多远的一个重要参数.图的交叉数问题起源于上世纪五十年代初匈牙利数学家Turan在砖厂中碰到的一个实际难题(Turan’s brick factory problem).因此,图的交叉数概念被提出,随后引发图论学者对这一参数的广泛研究,使之成为图论领域中的一个活跃的研究方向.对图的交叉数问题的研究不仅具有深刻理论意义,而且还有广泛的实际应用价值.确定具体图类交叉数是图的交叉数问题研究中的一个经典但非常难的内容,事实上,早期的研究表明,确定图的交叉数是一个NP-完备问题.计算图的交叉数没有一个统一的方法,且同一方法运用在结构非常相似的图类上也往往失效.因此,只有少数特殊图类交叉数被确定,本篇论文采用一些新的方法研究了一些特殊图类的交叉数,具体结论如下:在第二章中,首先得到了旋系和交叉数之间的一些关系,利用这些关系,确定了一个五阶不连通图与n个孤立点的联图的交叉数,其中,五阶不连通图是由一个完全图K4和一个孤立点组成.在第三章中,运用“点度局部修改法”,首先得到了轮图W5与n个孤立点的联图的交叉数.然后,结合拉链积的性质,确定了轮图Wm,m=3,4,5,与任意树T的笛卡尔积图的交叉数,这是对Klesc在2017年得到的一个结果的扩充.在第四章中,我们引入一种新方法,确定了K5,n+1e的交叉数,其中n≥0且为整数.这是Chia和Lee在2015年提出的一个猜想.此外,在本文的第一章中,我们还详细地阐述了本文所涉及的概念和术语以及有关交叉数问题研究现状.

论文目录

  • 中文摘要
  • 英文摘要
  • 第一章 绪论
  •   1.1 交叉数问题的起源及意义
  •   1.2 基本概念与术语
  •   1.3 交叉数的研究现状
  •   1.4 本文结构安排
  •   1.5 符号说明
  • 第二章 一个五阶不连通图与n个孤立点的联图交叉数
  •   2.1 引言
  •   2.2 旋系与交叉数
  • 1的交叉数'>  2.3 H+nK1的交叉数
  • 第三章 轮图与树的笛卡尔积图交叉数
  •   3.1 引言
  •   3.2 点度局部修改法
  • 5+nK1的交叉数'>  3.3 W5+nK1的交叉数
  • m□T的交叉数'>  3.4 Wm□T的交叉数
  • 5,n+1\e的交叉数'>第四章 K5,n+1\e的交叉数
  •   4.1 引言
  •   4.2 相关引理
  •   4.3 定理及证明
  • 第五章 总结与展望
  •   5.1 本文总结
  •   5.2 工作展望
  • 参考文献
  • 攻读博士学位期间完成的论文
  • 致谢
  • 文章来源

    类型: 博士论文

    作者: 王雨溪

    导师: 黄元秋

    关键词: 不连通图,联图,笛卡尔积图,完全二部图,画法,交叉数,旋系

    来源: 湖南师范大学

    年度: 2019

    分类: 基础科学

    专业: 数学

    单位: 湖南师范大学

    分类号: O157.5

    总页数: 113

    文件大小: 5399K

    下载量: 64

    相关论文文献

    • [1].两类完全二部图的一般点可区别全染色[J]. 东北师大学报(自然科学版) 2018(04)
    • [2].部分完全二部图与完全三部图的厚度关系[J]. 南开大学学报(自然科学版) 2019(04)
    • [3].完全二部图优美性质探索[J]. 大连理工大学学报 2017(06)
    • [4].完全二部图K_(10,n)(10≤n≤90)的点可区别E-全染色[J]. 山东大学学报(理学版) 2018(12)
    • [5].完全二部图K_(10,n)(91≤n≤214)的点可区别E-全染色[J]. 兰州大学学报(自然科学版) 2019(03)
    • [6].完全二部图K_(6,n)(6≤n≤38)的点可区别E-全染色[J]. 吉林大学学报(理学版) 2018(04)
    • [7].完全二部图的邻接谱(英文)[J]. 兰州大学学报(自然科学版) 2011(03)
    • [8].几乎完全二部图的距离标号边跨度[J]. 天津师范大学学报(自然科学版) 2016(04)
    • [9].完全二部图k_(4,n)去掉两条边的交叉数[J]. 衡阳师范学院学报 2008(06)
    • [10].完全二部图的超k-Steiner Wiener指数[J]. 太原师范学院学报(自然科学版) 2019(04)
    • [11].完全图及完全二部图的点可区别Ⅳ-全染色[J]. 数学的实践与认识 2012(06)
    • [12].完全二部图的t-pebbling数[J]. 科技信息 2010(24)
    • [13].图的主独立数[J]. 安庆师范大学学报(自然科学版) 2020(02)
    • [14].偶图K_(n,n)-I的循环m-圈分解[J]. 信阳师范学院学报(自然科学版) 2010(02)
    • [15].完全二部图的全符号{k}-控制数和全符号{k}-色数[J]. 数学进展 2018(04)
    • [16].完全二部图的拓扑指数[J]. 西北大学学报(自然科学版) 2015(06)
    • [17].C_n∨mC_n是反魔幻图[J]. 哈尔滨商业大学学报(自然科学版) 2018(04)
    • [18].完全二部图K_(n,n)的H_2-cordial问题[J]. 阴山学刊(自然科学版) 2008(02)
    • [19].关于余一维图的实现的探究[J]. 海南大学学报(自然科学版) 2017(01)
    • [20].Schrijver图SG(2k+2,k)的Hamilton性[J]. 数学的实践与认识 2014(08)
    • [21].完全图与树、圈、完全图、完全二部图的笛卡尔乘积图的消圈数[J]. 海南大学学报(自然科学版) 2009(04)
    • [22].P_5-等可填充的特殊图[J]. 南开大学学报(自然科学版) 2018(01)
    • [23].有关连通图的连通包数的一些结果[J]. 广西师范学院学报(自然科学版) 2013(01)
    • [24].关于图的交叉数的研究成果[J]. 南国博览 2019(04)
    • [25].最佳匹配的应用[J]. 佳木斯教育学院学报 2012(10)
    • [26].关于图的符号边全控制[J]. 山东大学学报(理学版) 2012(06)
    • [27].赋权图的拉普拉斯能量的下界[J]. 南宁师范大学学报(自然科学版) 2020(01)
    • [28].完全二部图的K_(p,p)-分解大集的存在谱[J]. 应用数学学报 2018(05)
    • [29].完全二部图最小亏格嵌入的数目[J]. 河北工业大学学报 2014(04)
    • [30].K_(2,3)∨C_n的交叉数[J]. 华东师范大学学报(自然科学版) 2011(05)

    标签:;  ;  ;  ;  ;  ;  ;  

    若干典型图类的交叉数及其相关问题研究
    下载Doc文档

    猜你喜欢