本文選題：禁止子圖　切入點(diǎn)：重子圖　出處：《西北工業(yè)大學(xué)》2016年博士論文

【摘要】：如果一個(gè)圖中含有Hamilton圈,即經(jīng)過(guò)圖中所有頂點(diǎn)的圈,那么這個(gè)圖被稱為是Hamilton的.本論文研究了圖的Hamilton性的一類充分條件——重子圖條件,推廣了 Bedrossian和Faudree等人關(guān)于圖的Hamilton性的禁止子圖條件的結(jié)論.本論文的研究基于如下的問(wèn)題:我們已知在圖中禁止了某些子圖結(jié)構(gòu)時(shí),能夠保證所給的圖是Hamilton的.如果我們?cè)试S這些子圖結(jié)構(gòu)存在,那么在這種子圖結(jié)構(gòu)上限制什么樣的條件,能夠仍然保證所給的圖含有Hamilton圈?設(shè)G是一個(gè)圖.對(duì)于給定的圖H,如果G不含同構(gòu)于H導(dǎo)出子圖,那么我們說(shuō)G是無(wú)H的(或H是G的禁止子圖).1991年Bedrossian在其博士論文中刻畫了這樣的連通圖對(duì){R,S}:使得任何2-連通無(wú)R無(wú)S圖是Hamilton的.設(shè)P是關(guān)于G的導(dǎo)出子圖的某種性質(zhì).如果G中每個(gè)同構(gòu)于H的導(dǎo)出子圖G"都滿足P，那么我們說(shuō)G滿足P(H).顯然,如果G是無(wú)H的,那么G自然滿足P(H).本論文研究的主要問(wèn)題是:對(duì)于什么樣的子圖R和什么樣的子圖性質(zhì)P，，一個(gè)圖G滿足P(R)可以保證G是Hamilton的.我們稱這種類型的充分條件為重子圖條件.因此重子圖條件有兩個(gè)要素,即子圖R和附加于子圖的限制條件P.本論文對(duì)于所考慮的幾類限制條件,完整刻畫了能夠保證任意2-連通圖是Hamilton的所有子圖.這些結(jié)論推廣了 Bedrossian等人關(guān)于禁止子圖條件的結(jié)果.此外,本文還討論了有關(guān)圖的Hamilton性的一些相關(guān)性質(zhì),包括圖的最長(zhǎng)圈經(jīng)過(guò)大度頂點(diǎn)的性質(zhì)和圖中2-因子的存在性.在第一章,我們介紹了一些基本概念和本文所研究的問(wèn)題的背景,并且列出了本論文得到的結(jié)論.從第二章到第六章,我們給出了某些類型的重子圖條件.我們研究了所給條件下能夠保證圖的Hamilton性的子圖.對(duì)于給定的圖H,我們稱圖G是H-o-重的,如果圖G的每一個(gè)同構(gòu)于H的導(dǎo)出子圖都含有兩個(gè)不相鄰的頂點(diǎn)度和至少為n(n是圖G的階).為研究無(wú)爪圖和爪-o-重圖的Hamilton性,Ryjacek和Cada分別提出了無(wú)爪圖的閉包理論和爪-o-重圖的閉包理論.在第二章我們介紹了閉包理論,這是本論文的一個(gè)重要工具.Ryjacek在2002年刻畫了無(wú)爪圖的閉包的結(jié)構(gòu).基于Ryjacek的刻畫,我們刻畫了爪-o-重圖的閉包的結(jié)構(gòu).第三章考慮了無(wú)爪圖的子圖端點(diǎn)度條件.對(duì)于給定的圖H,如果圖G的每一個(gè)同構(gòu)于H的子圖的每個(gè)端點(diǎn)的度至少為(n+ k)3,那么我們稱G滿足Φ(H,k).Broersma在1993年提出一個(gè)猜想:任意2-連通無(wú)爪圖若滿足Φ(N,-2)則是Hamilton的.在第三章,我們刻畫了所有這樣的連通圖R:使得任意2-連通無(wú)爪圖若滿足Φ(R,3)則是Hamilton的.我們的結(jié)論部分證明了Broersma的猜想.第四章考慮了爪-o-重圖的c-重子圖條件.對(duì)于給定的圖H,如果G的每一個(gè)同構(gòu)于H的導(dǎo)出子圖G′和G″的每個(gè)極大團(tuán)G″-C的每個(gè)非平凡分支都有一個(gè)頂點(diǎn)的度至少為n/2,那么我們稱G是H-c-重的.我們完整刻畫了使得任意2-連通爪-o-重R-c-重圖是Hamilton的所有連通圖R.第五章考慮了爪-o-重圖的p-重子圖條件.對(duì)于給定的連通圖H,如果G的每一個(gè)同構(gòu)于H的導(dǎo)出子圖僅有一個(gè)中心且度至少為n/2,或存在兩個(gè)中心度和至少為n,那么我們稱G是H-p-重的.我們刻畫了使得任意2-連通爪-o-重R-p-重圖是Hamilton的所有連通圖R.圖G被稱為是1-堅(jiān)韌的,如果對(duì)任意頂點(diǎn)割S,G-S的分支數(shù)不超過(guò)|S|.顯然所有Hamilton圖都是1-堅(jiān)韌的.在第六章我們考慮了 1-堅(jiān)韌圖的Hamilton性的禁止子圖條件.我們幾乎找到了所有的圖R：使得任何階至少為3的1-堅(jiān)韌無(wú)R圖是Hamilton的.在本論文的第七章和第八章,我們考慮了禁止子圖條件和重子圖條件下有關(guān)圖的Hamilton性的一些相關(guān)性質(zhì).第七章研究了圖的最長(zhǎng)圈經(jīng)過(guò)大度頂點(diǎn)的性質(zhì).對(duì)于給定的常數(shù)α ≤ 1,我們考慮對(duì)于什么樣的子圖R,一個(gè)2-連通圖G是無(wú)R的可以保證G的任意最長(zhǎng)圈都經(jīng)過(guò)所有度至少為αn+ O(1)的頂點(diǎn).我們完整刻畫了滿足這種性質(zhì)的連通子圖R.一個(gè)圖的2-正則生成子圖稱為這個(gè)圖的2-因子.Faudree等在2008年刻畫了所有這樣的連通圖對(duì){R,S}:使得任意2-連通無(wú)R無(wú)S圖含有2-因子.在第八章我們討論了圖中2-因子的存在性的-o-重子圖對(duì)條件.我們完全刻畫了所有這樣的子圖對(duì){R,S}：使得任意2-連通R-o-重S-o-重圖含有2-因子.最后一章對(duì)本論文的工作做了一個(gè)簡(jiǎn)要總結(jié),并提出了一些有待進(jìn)一步考慮的問(wèn)題.
[Abstract]:If there is a Hamilton circle map, the map after all vertices in the circle, then this map is called Hamilton. This paper studies a class of sufficient conditions of Hamilton graph, graph baryon generalization of Hamilton, Bedrossian and Faudree et al on the map of the forbidden subgraph conditions the conclusion. This paper is based on the following questions: we have known some forbidden subgraphs in the graph structure, can guarantee the picture is Hamilton. If we allow these sub graph structure exists, then the limit of what kind of conditions in this subgraph structure, can still ensure the picture containing Hamilton ring? Let G be a graph. For a given graph H, if G contains no induced subgraph isomorphic to H, then we say that G is H (or H is forbidden subgraph of G).1991 Bedrossian in his doctoral dissertation depicts a connected graph of the {R like this ,S}:浣垮緱浠諱綍2-榪為

本文編號(hào)：1678107