本文選題：Szeged參數(shù)　切入點：修正的Szeged參數(shù)　出處：《華中師范大學》2017年博士論文

【摘要】：圖論主要研究圖所蘊含的內(nèi)部結(jié)構(gòu),包括子圖的存在性、計數(shù)和算法,超圖是有限集的子集系統(tǒng),不僅推廣了圖論中的概念,而且在理論計算機科學、信息科學、生命科學等中有著廣泛的應用.因此,基于圖參數(shù)和有限集的研究有助于圖論、超圖理論等領域的發(fā)展.給定連通圖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參數(shù),Szeged參數(shù)和修正的Szeged參數(shù)分別定義為: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猜想).本論文主要借助于圖變換、函數(shù)構(gòu)造法、標準切割法以及空間基方法,研究了Hansen猜想和Snevily猜想及其相關問題.具體內(nèi)容包括:在第一章中,我們首先給出一些概念和符號定義;其次介紹了研究背景、研究意義以及已有的國內(nèi)外研究現(xiàn)狀;最后列出了本文的主要結(jié)果.在第二章中,我們首先證明了 Hansen猜想;其次對于至少含有一個圈的圖G,我們確定了*Sz(G)/W(G)和Sz*(G)/W(G)的下確界,并刻畫了對應的極圖結(jié)構(gòu).在第三章中,我們刻畫了對于至少有一個塊不是完全圖的圖G,Sz(G)/W(G)達到下界時圖的結(jié)構(gòu);對于至少含有一個圈的圖G,當Sz*(G)/W(G)取得第二小值時我們刻畫了圖G的結(jié)構(gòu)特征.在第四章中,我們確定了對于周長至少為4的仙人掌圖G,Sz(G)-W(G)的最小值以及第二小值;特別地,當圖G是二部仙人掌圖時,上述最小值得到改進.對于含有n個頂點kk(n≥3kk + 1,kk ≥ 1)個圈的仙人掌圖G,Sz*(G)-W(G)的下確界,并刻畫了所有對應極圖的組合結(jié)構(gòu).在第五章中,我們首先得出L[交族在滿足一定條件下所含子集個數(shù)的上界.其次我們考慮了將該結(jié)論推廣到kk-wise L-交族以及推廣到兩個集族等相關問題.這些結(jié)論不僅部分解決了 Snevily猜想,而且改進了一些已知結(jié)果的上界.在第六章中,在模p(p是素數(shù))及其他限制條件下,我們分別得出了 kk-wise L-交族和兩個集族所含子集個數(shù)的上界.這些結(jié)論不僅改進了一些已知結(jié)果的上界,而且將Alon-Babai-Suzuki定理推廣到了兩個集族.在第七章中,總結(jié)全文并作出展望.
[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