圖的k-walk.pdf

1、江西師范大學(xué)碩士學(xué)位論文圖的kwalk姓名：金澤民申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：基礎(chǔ)數(shù)學(xué)指導(dǎo)教師：劉展鴻熊黎明2002.5.1江西師范大學(xué)2002屆碩士學(xué)位論文固偽k一伽髓圖的k—walk一、引言設(shè)G是—個(gè)圖分別用y(G)和E(G)表示圖G的頂點(diǎn)集和邊集，dG(x)表示頂點(diǎn)z在圖G中的度數(shù)，zx(G)表示G的最大度圖G的uu強(qiáng)指的是非空有限可重復(fù)序列W=voel。le2“鞏，其中趴q分別為圖G中的邊和頂點(diǎn)，且e；的端點(diǎn)為礬一1和q設(shè)s冬y(G

2、)，“(G—s)表示G—S的分支數(shù)本文僅考慮簡(jiǎn)單有限無向圖因此我們簡(jiǎn)記圖G的walk為W=。o口1口2仇文中未定義的術(shù)語和記號(hào)見文獻(xiàn)[1]圖的k—walk是圖的哈密頓圈的一種推廣圖的k—zvalk指的是圖G的—個(gè)閉生成walk，其經(jīng)過G中每個(gè)點(diǎn)至多k次若經(jīng)過G中每個(gè)點(diǎn)的次數(shù)恰好為k，則稱為ezactk—walk因此在頂點(diǎn)數(shù)至少為3的圖G中，1一walk即為哈密頓圈圖的k—tree指的是指圖的最大度不大于^的生成樹圖的k—walk與k—t

3、ree有如下的關(guān)系：定理1112](1)若圖G含有^一tree，則圖G含有k—toalk(2)若圖G含有k—walk，則圖G含有(^1)一tree七十年代，在研究哈密頓問題時(shí)，人們提出了一種新的思想方法，也就是禁用子圖的方法，并得到許多優(yōu)美的結(jié)果稱圖G是K1，一加的，若圖G中不存在導(dǎo)出子圖與K1，同構(gòu)基于這種方法，BillJactBonandNCWomudd在文[2]中得到豐富的圖G含有k—walk的充分條件本文也是主要受其中—個(gè)猜想(

4、本文的猜想A)啟發(fā)而成定理12[2]設(shè)圖G為連通，K1^1一free圖，則(1)圖G有k—tvalk(2)若8(G)≥^，則圖G含有e：rmactk—walk考慮到圖的連通性時(shí)，文[2]證明：定理13[2】設(shè)j≥1，k≥3，且圖G為j一連通，K1，，(p2)1一free圖，則圖G含有k一議_咀lk基于定理12，文[2]中作者提出如下猜想：猜想A[2】設(shè)j≥1，^≥2，且圖G為J一連通，K11一free圖，則圖G含有k—walkOberl

5、yandSumner在文[3]中證明：連通的，局部連通的，且K13一free圖為哈密頓圖下述定理推廣了該有名的結(jié)論定理14[2】設(shè)^≥1，圖G(1y(G)I／3)為連通的，局部連通且K“2一free圖，則圖G含有k—walk并提出如下猜想：猜想B[2】設(shè)j≥l，^≥2，圖G為連通的，局部J一連通且KL(，1)^1一free圖，則圖G含有k—walk若猜想B成立，它實(shí)際上是定理12及[3]中—個(gè)猜想的推廣圖的堅(jiān)韌度與k—walk也有密切的