通過圖中每個(gè)頂點(diǎn)一次且僅一次的回路稱為哈密爾頓圈。存在哈密爾頓圈的圖就是哈密爾頓圖。哈密爾頓圖是圖論中的一個(gè)重要問題。截至目前,對(duì)哈密爾頓圖的研究,已經(jīng)有了豐富的結(jié)果,并且這些結(jié)果仍在進(jìn)一步完善之中。本文對(duì)最小度是3的哈密爾頓圖進(jìn)行了研究。Entringer和Swart在1978年構(gòu)造了這樣一個(gè)圖:最小度是3恰有唯一哈密爾頓圈含有某一條邊的圖,他們給出了一個(gè)11階的這樣的圖。在第一章,我們將證明這類圖的最低階數(shù)是10,在證明中,我們引入了一個(gè)圖G中關(guān)于某個(gè)哈密爾頓圈C的3度極小圖來簡(jiǎn)化證明,然后從4階到9階依次證明都沒有圖符合以上條件,從而得證。圖G中最小圈的長(zhǎng)度叫做G的圍長(zhǎng)。一個(gè)圍長(zhǎng)是g的k正則圖叫做（k,g）-圖。一個(gè)（k,g）-圖如果有最小的階數(shù)稱為（k,g）-籠子。塔特在1947年引入了籠子的概念。后來Daven和Rodger,Jiang和Mubayi獨(dú)立地證明了所有的（k,g）-籠子是3-連通的。在第二章我們給出了（k,g）-籠子是3-連通的新證明。 

【文章來源】：華東師范大學(xué)上海市 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：46 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

這個(gè)圖只有個(gè)哈密頓圈，分別是


本文編號(hào)：3514358