關(guān)于圖的哈密頓因子的若干結(jié)果.pdf

1、　　本文考慮的圖若無特殊聲明均為簡(jiǎn)單、無向有限圖,對(duì)于一個(gè)圖G=G(V(G),E(G)),我們用V(G)和E(G)分別表示圖的頂點(diǎn)集合和邊集合。對(duì)任意的v∈V(G),我們用d_G(v)表示頂點(diǎn)v在G中的度數(shù)。Δ(G)和δ(G)分別表示圖G的最大度和最小度,對(duì)V(G)的子集S,用G-S表示從G中刪去頂點(diǎn)集合S及其關(guān)聯(lián)的邊所得到的子圖。若S={v},則令G-v=G-{v}。對(duì)E(G)的子集X,用G-X表示從G中刪去邊集合X所得的子圖,若X=

2、{e},則G-{e}簡(jiǎn)記為G-e。若存在V(G)的兩個(gè)不交子集X、Y,使得V(G)=X∪Y,且G的所有邊均一個(gè)端點(diǎn)在X內(nèi),另一個(gè)端點(diǎn)在Y內(nèi),則稱G為二部圖,記為G=(X,Y,E(G))。如果|X|=|Y|,則稱G為均衡二部圖。
　　設(shè)g和f是定義在V(G)上的兩個(gè)整數(shù)值函數(shù),使對(duì)任意的v∈V(G)有0≤g(v)≤f(v)。若H是圖G的一個(gè)支撐子圖,且滿足對(duì)任意頂點(diǎn)v∈V(H),g(v)≤d_H(v)≤f(v),那么我們就稱H是圖G

3、的一個(gè)(g,f)-因子。如果對(duì)任意的v∈V(H)有g(shù)(v)=a、f(v)=b,則稱G的(g,f)-因子為[a,b]-因子。若a=b=k,則此時(shí)稱[a,b]-因子為k-因子,k=1時(shí)也稱1-因子為完美對(duì)集。對(duì)于圖G的一個(gè)因子,如果它同時(shí)包含G的一個(gè)哈密頓圈,我們就稱該因子為G的一個(gè)哈密頓因子。圖G的頂點(diǎn)數(shù)|V(G)|我們通常稱為G的階,一般用n來表示。如果圖G的最小度δ(G)≥n/2,但對(duì)于G的任意一條邊e,δ(G-e)

4、n/2-臨界圖。
　　設(shè)h是定義在圖G的邊集合E(G)上的一個(gè)函數(shù),使對(duì)任意的e∈E(G)有h(e)∈[0,1]。對(duì)G中的任意頂點(diǎn)v,令d_G~h(v)=∑e∈E_vh(e),其中E_v={e：e=vw∈E(G)},則稱d_G~h(v)是圖G的頂點(diǎn)v的分?jǐn)?shù)度,若h滿足對(duì)任意的v∈V(G)有g(shù)(v)≤d_G~h(v)≤f(v),則稱h為圖G的一個(gè)分?jǐn)?shù)(g,f)表示函數(shù),令E~h={e：e∈E(G)且h(e)≠0},設(shè)G_h是圖G的一