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

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

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

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

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