Hansen猜想、Snevily猜想及其相关问题研究

发布时间：2018-04-05 23:00

  本文选题：Szeged参数　切入点：修正的Szeged参数　出处：《华中师范大学》2017年博士论文

【摘要】：图论主要研究图所蕴含的内部结构,包括子图的存在性、计数和算法,超图是有限集的子集系统,不仅推广了图论中的概念,而且在理论计算机科学、信息科学、生命科学等中有着广泛的应用.因此,基于图参数和有限集的研究有助于图论、超图理论等领域的发展.给定连通图G=(VG,EG)任取u,v∈VG,令dG(u,v)表示图G中u,v两点的距离.任取 e = uv ∈ 令 nu(e)= |{w;∈ VG:dG(u,w)dG(v,w)}|,nv(e)=|{iu ∈ VG:dG(v,u;)dG(u,w)}| 以及 n0(e)= |{u;∈ VG:dG(u,w)= dG(v,w)}|,则图G的Wiener参数,Szeged参数和修正的Szeged参数分别定义为:W(G)=∑{u,v}(?)GdG(u,w),Sz(G)=∑e =uv∈EG,nu(e)nv=(e)和Sz*(G)=∑e=uv∈EG∈(nu(e)+n0(e)/2)(nu(e)+ n0(e)/2).2010年,Hansen 等提出 了关于 Sz(G)/W(G)和Sz*(G)/W(G)的三个猜想(简称Hansen猜想)以及Snevily提出了关于有限集的两个猜想(简称Snevily猜想).本论文主要借助于图变换、函数构造法、标准切割法以及空间基方法,研究了Hansen猜想和Snevily猜想及其相关问题.具体内容包括:在第一章中,我们首先给出一些概念和符号定义;其次介绍了研究背景、研究意义以及已有的国内外研究现状;最后列出了本文的主要结果.在第二章中,我们首先证明了 Hansen猜想;其次对于至少含有一个圈的图G,我们确定了*Sz(G)/W(G)和Sz*(G)/W(G)的下确界,并刻画了对应的极图结构.在第三章中,我们刻画了对于至少有一个块不是完全图的图G,Sz(G)/W(G)达到下界时图的结构;对于至少含有一个圈的图G,当Sz*(G)/W(G)取得第二小值时我们刻画了图G的结构特征.在第四章中,我们确定了对于周长至少为4的仙人掌图G,Sz(G)-W(G)的最小值以及第二小值;特别地,当图G是二部仙人掌图时,上述最小值得到改进.对于含有n个顶点kk(n≥3kk + 1,kk ≥ 1)个圈的仙人掌图G,Sz*(G)-W(G)的下确界,并刻画了所有对应极图的组合结构.在第五章中,我们首先得出L[交族在满足一定条件下所含子集个数的上界.其次我们考虑了将该结论推广到kk-wise L-交族以及推广到两个集族等相关问题.这些结论不仅部分解决了 Snevily猜想,而且改进了一些已知结果的上界.在第六章中,在模p(p是素数)及其他限制条件下,我们分别得出了 kk-wise L-交族和两个集族所含子集个数的上界.这些结论不仅改进了一些已知结果的上界,而且将Alon-Babai-Suzuki定理推广到了两个集族.在第七章中,总结全文并作出展望.
[Abstract]:Graph theory mainly studies the internal structure of graph, including the existence, counting and algorithm of subgraph, hypergraph is a subset system of finite set, which not only generalizes the concept of graph theory, but also in theoretical computer science and information science.Life science has a wide range of applications.Therefore, the research based on graph parameters and finite sets is helpful to the development of graph theory and hypergraph theory.Given a connected graph G _ G _ G _ G _ (G), let UG _ v 鈭，

本文编号：1716837