课题基金基金详情
k-连通图子式的相关问题研究
结题报告
批准号:
11401119
项目类别:
青年科学基金项目
资助金额:
23.0 万元
负责人:
覃城阜
依托单位:
学科分类:
A0409.图论及其应用
结题年份:
2017
批准年份:
2014
项目状态:
已结题
项目参与者:
邓天炎、邓贵新、苏华东、谭丽、黄乐贤、章丽丽
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
客服二维码
微信扫码咨询
中文摘要
图子式研究是图论中理论性强、所得到的成果影响深刻的研究方向之一。在其研究过程中所建立的理论和所创造的方法深刻地影响着图论的发展。连通图中的子式问题与Hadwiger猜想有密切关系,对k-连通图的子式进行有意义的刻划将对Hadwiger猜想的解答有深远的影响。 研究发现k=5时Hadwiger猜想等价于四色定理且此时Hadwiger猜想的极小反例是5-连通图,因此研究5-连通图的子式是十分有意义的工作。本项目主要围绕P.Seymour 提出的关于5-连通图拓扑子式的猜想以及G.Fijvaz提出的关于5-连通图子式的猜想,对5-连通图的拓扑子式和子式开展研究。将图子式问题转化为一些附加了具体条件的结构问题,利用研究图连通性的重要工具-断片理论以及我们所创立的5-连通图的研究技巧,尝试去解决这两个问题。在此过程中进一步探索图子式研究方法,为解决k较小时的Hadwiger 猜想提供可借鉴的方法。
英文摘要
The study on graph minor is one of graph theory topics which are considered to be so theoretical and have deepest impact. Its results and techniques will influence the development of graph theory for many years to come. The minors of k-connected graph has a close relation with the famous Hadwiger Conjecture. So it may be give a way to deal with the Hadwiger Conjecture if we can determine the minors of k-connected graph. The Hadwiger Conjecture is known to be equitvalent to the famous Four Colour Theorem for the case k=5. Further, it is found that the minimal counterexamples of Hadwiger Conjecture is 5-connected for the case k=5. Therefore the study on the minor of 5-connected graph is of great significance.. In this project, base on the Conjecture about the topological minor of 5-connected graphs which was posted by P.Seymour and the Conjecture about the minors of 5-connected graphs which was posted by G.Fijvaz, we will study the topological minors and the minors of 5-connected graphs. We will tranfer these problems to determine the structure of 5-connected graph which was imposed some detailed conditions. By the theory of fragment which is the most important tool in the graph connnectivity theory and by some techniques that we were developted in the study of 5-connected graphs, we try to deal with these two conjectures. During the course, we will develop further some tools for the study of graph minor and offer some new methods to deal with the Hadwiger Conjecture with some lower value of k..
图子式研究是图论中理论性强、所得到的成果影响深刻的研究方向之一。在其研究过程中所建立的理论和所创造的方法深刻地影响着图论的发展。本项目最初是想围绕P.Seymour 提出的关于5-连通图拓扑子式的猜想对5-连通图的子式开展研究。但是由于郁星星教授在2016年宣布他们证明了P.Seymour 猜想,所以我们对研究内容作了一定的修改,对图的可收边的分布, 图的约简方法,图的子式进行了研究。我们的主要结果有:.对具有可收缩边4-连通图的最小子式进行了完全刻画,证明了其中的平面图可以由C_6^2 通过一系列顶点剖分和加边得到,非平面图可以由C_5^2=K_5一系列顶点剖分和加边得到。这是一个具有本质特性而又具有广泛应用的结论。它完全解决了4-连通图的构造问题, 这是自1982年M.Martimov定理证明以来的重大进展。.其次,我们对internally 4-连通图的约简问题进行了研究,给出了10种约简运算,并构造例子说明了其中的8种是必不可少的。基本解决了internally 4-连通图的约简问题。.再次,我们证明了最小度为9的收缩临界8-连通图一定是由收缩临界4-连通图通过2-顶点分裂运算得到。在此基础上我们完全决定了子式极小且最小度为9的收缩临界8-连通图。我们的结论完全刻画了这类图的结构。.最后,我们对包含有由不可收缩边构成的生成树的3-连通的结构(称之为fox)进行刻画,证明了这类图中的每个3度点只关联一条不可收缩边。由此我们证明了在边极小的情况下这样的生成树是唯一存在的。进一步我们证明了3-连通图任意的深度优先搜索算法生成树一定有两条可收缩边,并举例说明我们的结果是最好可能的。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
DOI:DOI 10.1007/s40840-015-0286-y
发表时间:2016
期刊:Bull. Malays. Math. Sci. Soc.
影响因子:--
作者:Weihua Yang;覃城阜;陈美润
通讯作者:陈美润
On the depth spectrum of binary linear codes and their dual
二进制线性码及其对偶的深度谱
DOI:--
发表时间:2017
期刊:Discrete Mathematics
影响因子:0.8
作者:邓贵新
通讯作者:邓贵新
DOI:10.16601/j.cnki.issn1001-8743.2016.04.004
发表时间:2017
期刊:连通图; 最长圈; 可收缩边; 断片
影响因子:--
作者:刘希;邓天炎;覃城阜
通讯作者:覃城阜
Long minimal zero-sum sequences over a finite subset of Z
Z 的有限子集上的长最小零和序列
DOI:--
发表时间:2018
期刊:European Journal of Combinatorics
影响因子:--
作者:邓贵新;曾详能
通讯作者:曾详能
DOI:--
发表时间:2017
期刊:连通图; 最长圈; 可收缩边; 断片
影响因子:--
作者:刘希;邓天炎;覃城阜
通讯作者:覃城阜
连通图的可收缩子图与子式
  • 批准号:
    11961051
  • 项目类别:
    地区科学基金项目
  • 资助金额:
    40.0万元
  • 批准年份:
    2019
  • 负责人:
    覃城阜
  • 依托单位:
Minor 极小k-连通图的刻画
  • 批准号:
    11126321
  • 项目类别:
    数学天元基金项目
  • 资助金额:
    3.0万元
  • 批准年份:
    2011
  • 负责人:
    覃城阜
  • 依托单位:
国内基金
海外基金