【摘要】：設(shè)G是一個E(G)非空的圖.圖G的Gallai圖Gal(G)是把G的邊集作為它的點(diǎn)集,若G中的兩條邊e和f是相鄰的但不在同一個三角形中,則Gal(G)中的兩個不同頂點(diǎn)e和f是相鄰的.顯然,圖G的Gallai圖Gal(G)是線圖L(G)的一個生成子圖.本文我們首先刻畫了Gallai圖分別是圈和完全k-部圖的原圖.我們證明了兩個結(jié)論:一個圖G的Gallai圖Gal(G)是一個圈當(dāng)且僅當(dāng)G是F1,F3,F5或者Ck(k≥ 4)(見圖2);圖G是一個簡單圖,圖G的Gallai圖Gal(G)是一個完全k-部圖當(dāng)且僅當(dāng)G是k-star(k ≥ 2),P4或者C4.著名圖論學(xué)者Chartrand和Kronk證明了只有完全圖、完全二部圖和圈可以使得其任意線性森林可以擴(kuò)充成哈密頓路.本文的剩余部分我們研究了任意線性森林可以擴(kuò)充成哈密頓圈的圖的刻畫,在不應(yīng)用Chartrand和Kronk結(jié)論的情況下本文給出一個直接的結(jié)構(gòu)刻畫.
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

1 薛男;幾類特殊的Gallai圖[D];太原理工大學(xué);2018年

，

本文編號：2629753