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

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

本文編號(hào)：1716837