论文部分内容阅读
图论主要研究图所蕴含的内部结构,包括子图的存在性、计数和算法.超图是有限集的子集系统,不仅推广了图论中的概念,而且在理论计算机科学、信息科学、生命科学等中有着广泛的应用.因此,基于图参数和有限集的研究有助于图论、超图理论等领域的发展. 给定连通图G=(VG,EG),任取u,v∈VG,令dG(u,v)表示图G中u,v两点的距离.任取e=uv∈EG,令nu(e)=|{w∈VG:dG(u,w)<dG(v,w)}|,nv(e)=|{w∈VG:dG(v,w)<dG(u,w)}|以及n0(e)=|{w∈VG:dG(u,w)=dG(v,w)}|,则图G的Wiener参数,Szeged参数和修正的Szeged参数分别定义为:W(G)=∑{u,v}(∈)VGdG(u,v),Sz(G)=∑e=uv∈EGnu(e)nu(e)和Sz*(G)=∑e=uv∈EG(nu(e)+n0(e)/2)(nv(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个顶点k(n≥3k+1,k≥1)个圈的仙人掌图G,Sz*(G)-W(G)的下确界,并刻画了所有对应极图的组合结构. 在第五章中,首先得出L-交族在满足一定条件下所含子集个数的上界.其次我们考虑了将该结论推广到k-wise L-交族以及推广到两个集族等相关问题.这些结论不仅部分解决了Snevily猜想,而且改进了一些已知结果的上界. 在第六章中,在模p(p是素数)及其他限制条件下,我们分别得出了k-wise L-交族和两个集族所含子集个数的上界.这些结论不仅改进了一些已知结果的上界,而且将Alon-Babai-Suzuki定理推广到了两个集族. 在第七章中,总结全文并作出展望.