牛兆宏，喬娟娟

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

0 引言

本文考慮的圖均為有限無向無環(huán)的圖，允許有重邊。 空?qǐng)D是指沒有任何邊的圖。 文中未定義的術(shù)語和符號(hào)參見文獻(xiàn)［1］。

圖G的線圖，記為L(zhǎng)(G)，是指以G的邊集為頂點(diǎn)集，且兩個(gè)頂點(diǎn)鄰接當(dāng)且僅當(dāng)它們?cè)贕中（作為邊）是鄰接的。 設(shè)T是圖G中的一條跡，當(dāng)T的起點(diǎn)和終點(diǎn)重合時(shí)，稱T是閉跡。 若G的每條邊至少關(guān)聯(lián)T的一個(gè)頂點(diǎn)時(shí)，稱T是控制的。 Harary 和Nash?Williams 在文獻(xiàn)［2］中給出了線圖L(G)是哈密爾頓的，原圖G的一個(gè)特征刻畫。

定 理1［2］設(shè) 圖G是 一 個(gè) 邊 數(shù) 大 于 等 于3 的 連通圖。 線圖L(G)是哈密爾頓的當(dāng)且僅當(dāng)G有一條控制閉跡。

對(duì)于整數(shù)n≥1，圖G的n次迭代線圖Ln(G)遞歸地定義為L(zhǎng)(Ln-1(G))，其中L0(G)=G且L1(G)=L(G)。 Chartrand 在 文 獻(xiàn)［3］中 研 究 了Ln(G)的哈密爾頓性，并引入了哈密爾頓指數(shù)，記作h(G)，是使得Ln(G)是哈密爾頓的最小整數(shù)n。他證明了對(duì)于除去路之外的所有的圖，哈密爾頓指數(shù)總是存在的。 此后，人們對(duì)于圖的哈密爾頓指數(shù)進(jìn)行了大量的研究。 Chartrand 和Wall 在文獻(xiàn)［4］中研究了樹（除路外）的哈密爾頓指數(shù)。Ryjá?ek 等在文獻(xiàn)［5］中證明了確定一個(gè)圖的哈密爾頓指數(shù)小于或等于一個(gè)給定常數(shù)的問題是NP-完全的。 在文獻(xiàn)［6］和［7］中，Misra 等和Philip 等分別研究了哈密爾頓指數(shù)的算法，并且討論了算法的時(shí)間復(fù)雜度。 劉霞和熊黎明在文獻(xiàn)［8］中研究了哈密爾頓指數(shù)h(G)≤k時(shí)的禁用子圖集。 其他關(guān)于哈密爾頓指數(shù)的相關(guān)結(jié)果，參見綜述文獻(xiàn)［9］。

記Vi(G)={v∈V(G)：dG(v)=i} 和W(G)=V(G)V2(G)。G的枝是一條非平凡的路，它的端點(diǎn)在W(G) 中且內(nèi)部頂點(diǎn)（如果有的話）在V2(G)中。 用B(G)表示G中所有的枝構(gòu)成的集合，并且記

B1(G)={b∈B(G)：V(b)∩V1(G)≠?}。在圖G中，我們用O(G)表示G中的奇度頂點(diǎn)的集合。 熊黎明和劉展鴻在文獻(xiàn)［10］中定義了下面的集合EUk(G)，并且給出了迭代線圖Ln(G)是哈密爾頓的，原圖G的一個(gè)特征刻畫。

設(shè)EUk(G)是圖G中滿足如下條件的子圖H構(gòu)成的集合：

（I）|O(H)|=0；

（III）對(duì)于H的任意子圖H1，有dG(H1，H-H1)≤k-1；

（IV）對(duì)于每個(gè)枝b∈B(G)且E(b)∩E(H)=?，有|E(b)| ≤k+1；

（V）對(duì)于每個(gè)枝b∈B1(G)，有|E(b)| ≤k。

定理2［10］設(shè)圖G是一個(gè)邊數(shù)大于等于3 的連通圖，n≥2。 那么Ln(G)是哈密爾頓的當(dāng)且僅當(dāng)EUn(G)≠?。

牛兆宏等在文獻(xiàn)［14］中，研究了迭代線圖Ln(G)的可跡性問題，并且證明了如下的定理3。使得Ln(G)可跡的最小整數(shù)n稱為圖G的哈密爾頓路指數(shù)，記作hp(G)。 令EUPk(G)是圖G中滿足（II）-（IV）和如下條件（I）′和（V）′的子圖H構(gòu)成的集合。 顯然，EUk(G)?EUPk(G)。

（I）′|O(H)| ≤2；

（V）′ 對(duì)于每個(gè)枝b∈B1(G)且E(b)∩E(H)=?，有|E(b)| ≤k。

定理3［14］設(shè)圖G是一個(gè)邊數(shù)大于等于3 的連通 圖，n≥2。 那 么Ln(G) 是 可 跡 的 當(dāng) 且 僅 當(dāng)EUPn(G)≠?。

顯 然hp(G)≤h(G)。 文 獻(xiàn)［14］中 說 明 了hp(G)的這個(gè)平凡上界是最好可能的，并且給出了一些基于其他條件的最好可能的上界。

在定理2 的基礎(chǔ)上，人們給出了許多哈密爾頓指數(shù)的準(zhǔn)確值和上界。 在這些結(jié)果中，枝鍵、圈塊作為有效的研究工具被廣泛使用。 本文中，我們借助于定理3 中給出的特征刻畫，將之前若干哈密爾頓指數(shù)的準(zhǔn)確值和上界推廣到了哈密爾頓路指數(shù)上，給出了一些新的結(jié)果。

1 哈密爾頓路指數(shù)的準(zhǔn)確值

這一節(jié)我們主要給出幾個(gè)有關(guān)哈密爾頓路指數(shù)的準(zhǔn)確值。 首先我們給出一些必要的定義，以及Chartrand 和Wall 證明的關(guān)于樹的哈密爾頓指數(shù)的一個(gè)結(jié)果。

定義CB(G)={b∈B(G)：b的每一條邊都是G的割邊}，和CB1(G)=B1(G)。

設(shè)G是一個(gè)圖。 如果G是2-連通的，規(guī)定k(G)=0；如果G不是2-連通的并且CB(G)=?，規(guī)定k(G)=1；否則的話，

Chartrand 和Wall 在文獻(xiàn)［4］中確定了樹的哈密爾頓指數(shù)。

定理4［4］設(shè)T是一棵樹。 那么h(T)=k(T)。

在定理4 的基礎(chǔ)上，我們首先討論樹的哈密爾頓路指數(shù)。設(shè)T是一棵樹，P是T中的一條極長(zhǎng)的路。 那么由CB(T)和CB1(T)的定義可知，如果b∈CB(T)（ 或 者 ，b∈CB1(T)）并 且E(b)∩E(P)≠?，那么b?P。所以，我們?cè)谘芯抗軤栴D路指數(shù)時(shí)，只需要討論CB(T)（或者，CB1(T)）中滿足E(b)∩E(P)=?的枝b。定義

且E(b)∩E(P)=?}}，并且k*(T)=min{k*(T，P)：P是樹T的一條極長(zhǎng)的路}。如果T本身就是一條路，那么我們規(guī)定k*(T)=0。下面我們給出樹的哈密爾頓路指數(shù)。

定理5 設(shè)T是一棵樹，那么hp(T)=k*(T)。

證明 首先我們證明hp(T)≤k*(T)。根據(jù)定理3，只需證明EUPk*(T)(T)≠?。設(shè)P是樹T的一條極長(zhǎng)的路，使得k*(T)=k*(T，P)。令

下面證明H∈EUPk*(T)(T)。顯然H滿足（I）′和（II）。由H的定義可知，H中的分支只能通過樹T中屬于CB(T)CB1(T)的枝來連結(jié)。由k*(T)的定義，我們知道對(duì)于H的每一個(gè)子圖H1，有dT(H1，H-H1)≤k*(T)-1，從 而（III）成 立。 由 于B(T)=CB(T)和B1(T)=CB1(T)，以及k*(T)和H的定義可知，對(duì)于每一個(gè)b∈B(T)且E(b)∩E(H)=?，有|E(b) |≤k*(T)-1＜k*(T)+1；對(duì) 于 每 一 個(gè)b∈B1(T) 且E(b)∩E(H)=?， 有 |E(b) |≤k*(T)。 即H滿 足（IV）和（V）′。 這 就 證 明 了H∈EUPk*(T)(T)。

下面我們證明hp(T)＞k*(T)-1。根據(jù)定理3，只需證明EUPk*(T)-1(T)=?。 用反證法，設(shè)EUPk*(T)-1(T)≠?，并且H∈EUPk*(T)-1(T)。如果H不連通，對(duì)于H的分支H1，我們可以找一條最短路P1使 得dT(H1，H-H1)=|E(P1)|（≤k*(T)-2）且c(H∪P1)=c(H)-1。顯然，P1∈B(T)。重復(fù)這個(gè)過程，直到得到的圖H～：=H∪P1∪P2∪…是連通的。如果H連通，那么令H～：=H。下面我們斷言如果一個(gè)枝滿足b∈B(T)B1(T)和E(b)∩E(H)=?，那么b?H～：否則的話，b∪H～將會(huì)產(chǎn)生一個(gè)圈，這與T是一棵樹矛盾。注意到B(T)=CB(T)和B1(T)=CB1(T)，當(dāng) 一 個(gè) 枝b滿 足b∈CB(T)CB1(T)且E(b)∩E(P)=?時(shí)，| |E(b) ≤k*(T)-2；當(dāng)一個(gè)枝b滿足b∈CB1(T)且E(b)∩E(P)=?時(shí)，|E(b)| ≤k*(T)-1。由k*(T，P)和k*(T)的定義可知，k*(T)≤k*(T，P)≤k*(T)-1，矛盾。

因此，hp(T)=k*(T)。

Catlin 在文獻(xiàn)［15］中給出了確定一個(gè)圖G是否包含一個(gè)生成閉跡的約化方法。運(yùn)用這個(gè)方法和定理1，人們給出了h(G)的一些很好的上界（參見文獻(xiàn)［16］-［19］）。文獻(xiàn)［10］中給出了一個(gè)類似的約化方法，用來確定一個(gè)圖G的哈密爾頓指數(shù)h(G)。

設(shè){b1，b2，…，bm}?B(G) 且|E(bi)|≥2。 對(duì)于i∈{1，2，…，m}，定 義 圖G的 收 縮 圖，記 為G//{b1，b2，…，bm}，是指由G通過收縮bi的一條邊得到的圖，也就是說，將bi(1≤i≤m)替換為一個(gè)長(zhǎng)度為|E(bi)|-1 的新的枝所得到的圖。

熊黎明和劉展鴻在文獻(xiàn)［10］中確定了h(G)≥4 的圖G的哈密爾頓指數(shù)。

定理6［10］設(shè)G是一個(gè)連通圖，b1，b2，…，bm是G中所有長(zhǎng)度至少是2 的枝。如果h(G)≥4，那么h(G)=h(G//{b1，b2，…，bm})+1。

在定理6 的基礎(chǔ)上，下面我們討論類似的哈密爾頓路指數(shù)問題。在此之前，先給出兩個(gè)引理，其中第一個(gè)引理是線圖可跡性的一個(gè)特征刻畫，與定理1 相類似；第二個(gè)引理可由EUPhp(G)(G)的定義很容易得到，所以我們略去它的證明。

引 理7［12，20］圖G是 一 個(gè) 邊 數(shù) 大 于 等 于3 的 連通圖，則線圖L(G)是可跡的當(dāng)且僅當(dāng)圖G有一條控制跡。

引 理8 設(shè)G是 一 個(gè) 圖，hp(G)≥2，并 且H∈EUPhp(G)(G)。對(duì)于H1?H，如果P是一條從H1到H-H1的 路，滿 足|E(P)|≥2 且P的 內(nèi) 部 頂點(diǎn)都不在V(H)中，那么P∈B(G)。

我們給出下面的結(jié)果。

定理9 設(shè)G是一個(gè)連通圖，b1，b2，…，bm是G中所有長(zhǎng)度至少是2 的枝。如果hp(G)≥4，那么hp(G)=hp(G//{b1，b2，…，bm})+1。

證 明 令G′=G//{b1，b2，…，bm}。由 定 理3可知，h p(G′)≤hp(G)顯然成立。如果hp(G′)≤1，那么由引理7 可知，G′中存在一條控制跡H′。令b′1，b′2，…，b′m是G′ 中 的 枝，分 別 與G中 的 枝b1，b2，…，bm相對(duì)應(yīng)。令H′′是G的一個(gè)子圖，它是由H′通 過 將b′1，b′2，…，b′m分 別 替 換 為b1，b2，…，bm得到的圖。定義H=(V(H)，E(H))，其中

那么H∈EUP3(G)：（I）′，（II），（IV）和（V）′顯然成立，對(duì)于每個(gè)H中的孤立頂點(diǎn)u，設(shè)b′是一個(gè)以u(píng)為端點(diǎn)的枝 ，那 么|E(b′)|=1，從 而dG(u，H-u)=|E(b′)|+1=2，（III）也成立。所以，根據(jù)定理3可知，hp(G)≤3，這 與 假 設(shè)hp(G)≥4 矛 盾。 因 此，hp(G)≥hp(G′)≥2。由定理3 可知，

EUPhp(G)(G)≠?和EUPhp(G′)(G′)≠?。

設(shè)H∈EUPhp(G)(G)，H′是G′中的對(duì)應(yīng)于H的子 圖。 由 引 理 8 和G′ 的 定 義 可 知，H′∈EUPhp(G)-1(G′)。 從 而 由 定 理 3 知，hp(G′)≤hp(G)-1。

同理，設(shè)H′∈EUPhp(G′)(G′)，H是G中的對(duì)應(yīng)于H′的子圖。 由引理8 和G′的定義可知，H∈EUPhp(G′)+1(G)。 從 而 由 定 理3 知，hp(G)≤hp(G′)+1。

綜上所述，hp(G)=hp(G//{b1，b2，…，bm})+1。

定理9 中的條件hp(G)≥4 是最好可能的：我們下面構(gòu)造一類圖G0，它滿足hp(G0)=3，但是hp(G0)≠hp(G0//{b1，b2，…，bm})。 設(shè)P=u1u2…u3s…ut是 一 條 長(zhǎng) 度 為t的 路，其 中t≥3s+3 ≥15，w，v1，v2，v3是4 個(gè)不屬于V(P)的頂點(diǎn)。定義G0=(V(G0)，E(G0))，其中

E(G0)=E(P)∪{wv1，wv2，wv3，v1us，v2u2s，v3u3s}。容易驗(yàn)證hp(G0)=3，但是它的收縮圖的哈密爾頓路指數(shù)為1。

2 哈密爾頓路指數(shù)的上界

本節(jié)中討論哈密爾頓路指數(shù)的上界。

圖G的一個(gè)沒有割點(diǎn)的極大連通子圖稱為塊。 如果G的一個(gè)塊只含有一條邊，則稱它為無圈塊，否則稱為圈塊。 Sara?in 在文獻(xiàn)［21］中將定理4 推廣到了每個(gè)圈塊都是哈密爾頓的圖。

定理10［21］如果連通圖G的每個(gè)圈塊都是哈密爾頓的，那么h(G)=k(G)。

在定理10 的基礎(chǔ)上，我們討論這類圖的哈密爾頓路指數(shù)。 在圖G中，所有的圈塊分別記作G1，G2，…，Gs。P是G中的一條極長(zhǎng)的路。我們用P將G1，G2，…，Gs分 成 兩 類：與P沒 有 公 共 邊 的 圈塊Gi：E(P)∩E(Gi)=?和與P有公共邊的圈塊Gj：E(P)∩E(Gj)≠?。由P的極長(zhǎng)性可知，如果b∈CB1(G)且E(b)∩E(P)≠?，那么b?P。

設(shè)G是一個(gè)圖。 如果G有一條哈密爾頓路，規(guī)定k*(G)=0；如果G沒有哈密爾頓路，但是有一條控制跡，規(guī)定k*(G)=1；否則的話，我們按照如下方式定義k*(G)。

并且k*(G)=min {k*(G，P)：P是G中的一條極長(zhǎng)的路}。如果G?T是一棵樹，它沒有圈塊，此時(shí)令k*3(G，P)=0。從而k*(G)和我們?cè)诙ɡ? 之前針對(duì)樹定義的k*(T)是相等的。 我們?cè)谖闹腥员Ａ鬹*(T)的定義，是因?yàn)橛蒶(G)的定義引出k*(T)的定義更自然一些。

下面我們研究定理10 中所涉及圖類的哈密爾頓路指數(shù)。 首先給出下面的引理，它研究了迭代線圖中圈塊的哈密爾頓性。

引理11［21］如果圖G的每個(gè)圈塊都是哈密爾頓的，那么n次迭代線圖Ln(G)的每個(gè)圈塊也都是哈密爾頓的。

接下來我們給出hp(G)的一個(gè)上界。

定理12 如果連通圖G的每個(gè)圈塊都是哈密爾頓的，那么hp(G)≤k*(G)。

證明 如果hp(G)=0，那么G有一條哈密爾頓路。 由k*(G)的定義可知，k*(G)=0。 定理12成立。 如果hp(G)=1，那么由引理7 可知，G有一條控制跡。 此時(shí)k*(G)=1，定理12 亦成立。 下面我們假設(shè)hp(G)≥2。 根據(jù)定理3，只需證明EUPk*(G)(G)≠?。

因?yàn)镠包含G中所有度大于等于3 的頂點(diǎn)，所以H中的分支在G中只能通過B(G)B1(G)中的枝 來 連 結(jié)。 設(shè)H1是H的 一 個(gè) 子 圖，b∈B(G)B1(G) 是 連 結(jié)H1和H-H1的 枝，并 且 滿 足dG(H1，H-H1)=|E(b)|。 顯 然E(b)∩E(P)=?。 如果b∈CB(G)，那么由k*2(G，P)的定義可知 ， |E(b)| ≤k*2(G，P)-1≤k*(G，P)-1=k*(G)-1。 如果b?CB(G)，那么b一定包含在某個(gè)與P有公共邊的圈塊（設(shè)為Gj）中：否則的話，b的兩個(gè)端點(diǎn)位于H的某個(gè)圈Ci中，這與b的選取矛盾。 由k*(G)的定義，我們有

因 此，我 們 總 有dG(H1，H-H1)=|E(b)| ≤k*(G)-1，這就證明了H滿足（III）。

因此，我們總有|E(b)| ≤k*(G)+1，這就證明了H滿足（IV）。

如 果b∈B1(G) 且E(b)∩E(H)=?，那 么b∈CB1(G)，從而|E(b)| ≤(G，P)≤k*(G，P)=k*(G)。所以H滿足（V）′。

這就證明了H∈EUPk*(G)(G)。因此，定理12成立。

定理12 只給出了hp(G)的上界。 針對(duì)這類圖，我們猜想hp(G)=k*(G)。

猜想13 如果連通圖G的每個(gè)圈塊都是哈密爾頓的，那么hp(G)=k*(G)。

下面我們考慮熊黎明和劉展鴻在文獻(xiàn)［10］中給出的哈密爾頓指數(shù)的一個(gè)上界。 設(shè)圖G是一個(gè)Δ(G)≥3 的 連 通 圖。 定 義B0(G)={b∈B(G)：G[V(b)] 是G的 一 個(gè) 圈}，k=max {|E(b)|：b∈B(G)B0(G)}。

定理14［10］設(shè)圖G是一個(gè)連通圖，并且不是一條路。那么

h(G)≤max {|E(b)|：b∈B(G)B0(G)}+1。在定理14 的基礎(chǔ)上，我們討論類似的哈密爾頓路指數(shù)的上界。 設(shè)圖G是一個(gè)Δ(G)≥3 的連通圖，P是G中的一條極長(zhǎng)的路，記B0(G)={b1，b2，…，bs}。 我們用P將B0(G)分成兩類：

和

由P的 極 長(zhǎng) 性 可 知 ，bi?P當(dāng) 且 僅 當(dāng)E(bi)∩E(P)≠?。因此，B0(G)=B′0(G)∪B″0(G)

定義

且

k**(G)=min {k**(G，P)：P是G中一條極長(zhǎng)的路}。

定理15 設(shè)G是一個(gè)連通圖。 那么hp(G)≤k**(G)+1。

證 明 根 據(jù) 定 理 3， 我 們 只 需 證 明EUPk**(G)+1(G)≠?。 設(shè)P是圖G的一條極長(zhǎng)的路 ， 使 得k**(G)=k**(G，P)。 對(duì) 于 每 個(gè)b∈B0(G)，用C(b) 表 示 由V(b) 誘 導(dǎo) 出 來 的圈。 令

下 面 證 明H∈EUPk**(G)+1(G)。（I）′和（II）顯然成立。由k**(G，P)和H的定義可知，任給H的子圖H1，dG(H1，H-H1)≤k**(G，P)=k**(G)=(k**(G)+1)-1，（III）成 立。 當(dāng)b∈B(G)，且E(b)∩E(H)=? 時(shí) ， |E(b)| ≤k**(G)＜(k**(G)+1)+1，（IV）成 立。 當(dāng)b∈B1(G)，且E(b)∩E(H)=?時(shí)，| |E(b) ≤k**(G)＜k**(G)+1，（V）′成立。這就證明了H∈EUPk**(G)+1(G)。 因此，hp(G)≤k**(G)+1。

定理15 中的上界是最好可能的。 我們構(gòu)造如下 的 圖G0：k≥1，l＞k+1 均 為 整 數(shù)，P=v1v2…v2l+1是一條長(zhǎng)為2l的路，P′=u1u2…uk+1是一條長(zhǎng)為k的路，C是一個(gè)圈。G0是由P，P′和C通過分別等同頂點(diǎn)vl+1和u1，以及uk+1和C上任意一個(gè)頂點(diǎn)得到的圖。 此時(shí)，k=k**(G0)。 由定理3 可知，Lk+1(G0)是可跡的，但Lk(G0)不可跡。