最小極大唯一哈密頓圖存在2度點的證明

侯政

（無錫機電高等職業技術學校本科部，江蘇無錫214028）

最小極大唯一哈密頓圖存在2度點的證明

侯政

（無錫機電高等職業技術學校本科部，江蘇無錫214028）

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

哈密頓圖；哈密頓圈；2度點

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

1　最小極大唯一哈密頓圖及其性質

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

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

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

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

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

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

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

定理2也稱為Thomason定理。

2　輔助定理及其證明

根據以上定義和定理，可以得到下面幾個輔助定理。

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

根據以上推導，有

且有：當p為偶數時，2q（p）的值為3p+2；當p為奇數時，2q（p）的值為3p+3。

綜上所述，有

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

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

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

2）由式（1）及?(G)=4可知，當p為偶數時，G中有且僅有兩個度為4的點u和v。

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

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

無論以上哪一種情況，p為偶數時，G中有且僅有兩個度為4的點u和v，且u和v是不相鄰的。

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

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

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

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

對于情形1，可以得出與deg y=3矛盾的結論。

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

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

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

3　主要結論

定理5：在p=8或p=10時，最小極大哈密頓圖G 有2度點。

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

1）若p=8時結論不成立，可設C=v0v1…v7v0， v0=u，且，其中i

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

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

圖2　x不存在的情形

對于以上兩種情形，各點的鄰接情況可以描述為以下三種類型。

圖1（a）中各點的鄰接關系只能表示為圖3的形式，但該圖中有一個不同于C的哈密頓圈

圖1（b）中各點的鄰接關系只能表示為圖4的形式，但該圖中有一個不同于C的哈密頓圈

圖2中各點的鄰接關系只能表示為圖5的形式，但該圖中也有一個不同于C的哈密頓圈

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

圖3　鄰接關系1

圖4　鄰接關系2

圖5　鄰接關系3

4　結束語

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

［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］李修睦.圖論導引［M］.武漢：華中工學院出版社，1982：203-244.

［5］周秀君.一類獨立數為4圖的結構研究［J］.長江大學學報（自然科學版），2011（3）：1-3.

［6］HARARY F.圖論［M］.李慰萱，譯.上海：上海科學技術出版社，2008：75-98.

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

【責任編輯王云鵬】

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-），男，江蘇無錫人，講師，碩士，研究方向：圖論、概率統計和數學教學。