侯政

（無(wú)錫機(jī)電高等職業(yè)技術(shù)學(xué)校本科部，江蘇無(wú)錫214028）

最小極大唯一哈密頓圖存在2度點(diǎn)的證明

侯政

（無(wú)錫機(jī)電高等職業(yè)技術(shù)學(xué)校本科部，江蘇無(wú)錫214028）

給出了最小極大唯一哈密頓圖的定義和性質(zhì)，研究了p( p≥3)階最小極大唯一哈密頓圖存在2度點(diǎn)的猜想，并利用輔助定理證明了p=8和p=10時(shí)，p( p≥3)階最小極大唯一哈密頓圖存在2度點(diǎn)。

哈密頓圖；哈密頓圈；2度點(diǎn)

C.A.Barefoot等［1］首次提出了最小極大唯一哈密頓圖的概念，同時(shí)提出了p( p≥3)階最小極大唯一哈密頓圖有2度點(diǎn)的猜想。A.D.Nhu等［2］對(duì)最小極大唯一哈密頓圖做了研究，但并沒能證明該猜想。在本文中，筆者也研究了該猜想，并證明了p=8和p=10時(shí)，p( p≥3)階最小極大唯一哈密頓圖存在2度點(diǎn)。

1　最小極大唯一哈密頓圖及其性質(zhì)

定義1：稱p階簡(jiǎn)單圖G為最小極大唯一哈密頓圖是指G滿足以下條件：1）G中有且僅有一個(gè)哈密頓圖；2）任加一條G中沒有的線，能使G中哈密頓圈數(shù)增加；3）G中有最少的線。

C.A.Barefoot和R.C.Entringer證明了以下定理1。

定理1：設(shè)q（p）為p( p≥3)階最小極大唯一哈密頓圖的線數(shù)，則有以下結(jié)論成立：當(dāng)3≤p≤7時(shí)，q( p)=2p?3，且p階最小極大唯一哈密頓圖是唯一的；當(dāng)p≥8時(shí)，

在以下證明過(guò)程中，用G表示p( p≥8)階最小極大唯一哈密頓圖，C表示G中僅有的哈密頓圖。用分別表示G中的點(diǎn)x、y在子圖S中相鄰、不相鄰。

定義2［3］：設(shè)，若存在vs、vt，且使得vs和vt相鄰，vs+1和vt+1不相鄰，則稱G中存在θ-鄰接。

顯然，p( p≥8)階最小極大唯一哈密頓圖中不存在θ-鄰接。

定理2［4］：在階數(shù)至少為3的多重圖H中，若除u、v外的所有點(diǎn)的度均為奇數(shù)，則H中有偶數(shù)（可能為零）條哈密頓路聯(lián)結(jié)u和v。

定理2也稱為Thomason定理。

2　輔助定理及其證明

根據(jù)以上定義和定理，可以得到下面幾個(gè)輔助定理。

定理3：若δ(G)>2，則有以下結(jié)論成立：1）δ(G)=3，?(G)=4；2）當(dāng)p為偶數(shù)時(shí)，G中有且僅有兩個(gè)度為4的點(diǎn)u和v，且u和v不相鄰；3）p為奇數(shù)時(shí)，G中有且僅有三個(gè)度為4的點(diǎn)u、v和w，且這些點(diǎn)在子圖G-C中獨(dú)立。

根據(jù)以上推導(dǎo)，有

且有：當(dāng)p為偶數(shù)時(shí)，2q（p）的值為3p+2；當(dāng)p為奇數(shù)時(shí)，2q（p）的值為3p+3。

綜上所述，有

又由于δ(G)>2，因此有δ(G)=3。

由（1）式可得如下結(jié)論：當(dāng)p為偶數(shù)時(shí)，δ(G)≤?(G)≤δ(G)+2=5；當(dāng)p為奇數(shù)時(shí)，δ(G)≤?(G) ≤δ(G)+3=6。在以上推導(dǎo)中，有?(G)≠5。若?(G)=5，則G中至多有一個(gè)點(diǎn)u的度為偶數(shù)。若令v∈V( G)，且有uadjv ，則u和v間有一條哈密頓路，于是由定理2

C可知u和v間至少有兩條哈密頓路，從而可知G中至少有一個(gè)不同于C的哈密頓圈［5］，這與G的唯一性矛盾，故有?(G)≠5。同理可證，?(G)≠6。綜上所述，可知?(G)=4。

2）由式（1）及?(G)=4可知，當(dāng)p為偶數(shù)時(shí)，G中有且僅有兩個(gè)度為4的點(diǎn)u和v。

下面用反證法證明u和v不相鄰。

假設(shè)u和v相鄰，則存在以下兩種情形。

無(wú)論以上哪一種情況，p為偶數(shù)時(shí)，G中有且僅有兩個(gè)度為4的點(diǎn)u和v，且u和v是不相鄰的。

3）由式（1）和?(G)=4可得，p為奇數(shù)時(shí)，G中有且僅有三個(gè)度為4的點(diǎn)u、v和w。

下面用反證法證明u、v和w在子圖G-C中獨(dú)立。

定理4：當(dāng)p為偶數(shù)，且δ(G)>2時(shí)，有以下結(jié)論成立：1）N( u)∩N( v)中至多有一個(gè)點(diǎn)x，若這樣的x存在，x和u及x和v則在子圖C中相鄰；2）對(duì)任意的y∈N( u)，且，對(duì)任意的z∈N( v)，且，則有y和z不相鄰。其中：u和v為G中僅有的兩個(gè)4度點(diǎn)，N（u）和N（v）分別表示u和v的鄰域。

證明：1）若存在y∈V( G)，且y∈N( u)∩N( v )，則存在以下三種情形：

對(duì)于情形1，可以得出與deg y=3矛盾的結(jié)論。

對(duì)于情形2，由定理2可知，G-yv中至少有兩條哈密頓路［6］聯(lián)結(jié)y和u，由此可得G中至少存在一不同于C的哈密頓圈，這與G的唯一性矛盾。

綜合以上證明過(guò)程，情形1和情形2可以排除，由此可知情形3是成立的。由于p≥8，故N( u)∩N( v)中至多有一個(gè)點(diǎn)x。

2）若y和z相鄰，則需要分成兩種情形討論。

3　主要結(jié)論

定理5：在p=8或p=10時(shí)，最小極大哈密頓圖G 有2度點(diǎn)。

證明：設(shè)u、v∈V( G)，及degu=degv=4，下面用反證法證明定理5。

1）若p=8時(shí)結(jié)論不成立，可設(shè)C=v0v1…v7v0， v0=u，且，其中i

2）若p=10時(shí)結(jié)論不成立，則由定理3和定理4可知，G中所有點(diǎn)在C上的分布情況只能有以下兩種情形：情形1是存在x∈V( G)，且有。此時(shí)的N（u）和N（v）如圖1所示，由圖1可以看出，x與u、v相鄰。情形2是N( u)∩N( v)=?。此時(shí)N（u）和N（v）只能如圖2所示，這樣的x是不存在的。

圖1　x與u、v相鄰的情形

圖2　x不存在的情形

對(duì)于以上兩種情形，各點(diǎn)的鄰接情況可以描述為以下三種類型。

圖1（a）中各點(diǎn)的鄰接關(guān)系只能表示為圖3的形式，但該圖中有一個(gè)不同于C的哈密頓圈

圖1（b）中各點(diǎn)的鄰接關(guān)系只能表示為圖4的形式，但該圖中有一個(gè)不同于C的哈密頓圈

圖2中各點(diǎn)的鄰接關(guān)系只能表示為圖5的形式，但該圖中也有一個(gè)不同于C的哈密頓圈

由以上證明過(guò)程可知，無(wú)論G中所有點(diǎn)的鄰接情況如何，G中總存在一個(gè)與C不相同的哈密頓圈C′，這與G的唯一性相矛盾，因此G中必有2度點(diǎn)。

圖3　鄰接關(guān)系1

圖4　鄰接關(guān)系2

圖5　鄰接關(guān)系3

4　結(jié)束語(yǔ)

在本文中，筆者證明了p=8和p=10時(shí)，p( p≥3)階最小極大唯一哈密頓圖存在2度點(diǎn)，但沒有證明p取其他值的情形，這也是需要進(jìn)一步研究的問(wèn)題。

［1］BAREFOOT C A，ENTRIGER R C.Extremal Maximal Uniquely Hamiltonian Graphs［J］.Journal of Graph Theory，1980，4（1）:93-100.

［2］NHU AD，DINH H V.Necessary and Sufficient Condition for Maximal Uniquely Hamiltonian Graphs［J］. International Journal of Advanced Research in Computer Science，2012，3（5）:114-116.

［3］THOMASON A G.Hamiltonian Cycles and Uniquely Edge Colourable Graphs［J］.Annals of Discrete Mathematics，1978，3:259-268.

［4］李修睦.圖論導(dǎo)引［M］.武漢：華中工學(xué)院出版社，1982：203-244.

［5］周秀君.一類獨(dú)立數(shù)為4圖的結(jié)構(gòu)研究［J］.長(zhǎng)江大學(xué)學(xué)報(bào)（自然科學(xué)版），2011（3）：1-3.

［6］HARARY F.圖論［M］.李慰萱，譯.上海：上?？茖W(xué)技術(shù)出版社，2008：75-98.

［7］張先迪，李正良.圖論及其應(yīng)用［M］.北京：高等教育出版社，2005：78-89.

【責(zé)任編輯王云鵬】

Proof of the Existence of a 2-degree Vertex for the Minimum Maximal Unique Hamilton Graph

HOU Zheng
（Department of Undergraduate，Wuxi Electromechanical Higher Vocational and Technical School，Wuxi 214028，China）

The definition and properties of the minimal maximal unique Hamilton graph were given in this paper.The conjecture of the existence of 2-degree vertex for the minimum maximal unique Hamilton graph was studied.According to the auxiliary theorem，there was a proof thatp( p≥3)order of the minimum maximal unique Hamilton graph had a 2-degree vertex，when p was equal to 8 and 10.

Hamilton graph；Hamilton cycle；2-degree vertex

O157.5

A

2095-7726（2016）03-0010-03

2015-12-31

侯政（1976-），男，江蘇無(wú)錫人，講師，碩士，研究方向：圖論、概率統(tǒng)計(jì)和數(shù)學(xué)教學(xué)。