給定零維數(shù)的單圈圖研究

何博瑞，房明磊

(安徽理工大學 數(shù)學與大數(shù)據(jù)學院，安徽 淮南 232001)

零度問題的研究是圖論中一個熱門問題.20世紀50年代，Collatz和Sinogowitz提出關(guān)于刻畫所有奇異圖的問題.過去二十年，關(guān)于圖的零度問題吸引了眾多的圖論學家和化學家的注意力.在文獻[1-11]中，作者對單圈圖的零度關(guān)系進行了廣泛研究.譚學忠和柳柏濂[1]刻畫了η(G)=n-4所有圖.郭繼明[2]刻畫了η(G)=n-5所有圖.本文考慮η(G)=n-6和η(G)=n-7的所有n階單圈圖，并刻畫了所有的滿足條件的圖.

1 基本理論

2 主要結(jié)果

定理1設(shè)G是n(n≥6)階單圈圖，則η(G)=n-6當且僅當G屬于圖類Gi(i=1,2,…,31)(見圖4).

證明假設(shè)G的圈長為l，根據(jù)引理1、引理2和引理3，可以得到以下情況.

情況1η(G)=n-6=n-2v(G)-1=η(G)，顯然2v(G)=5，因為匹配數(shù)均為正整數(shù)，所以不成立.

a.考慮在圈C4={v1,v2,v3,v4}頂點v1連接一條匹配數(shù)為1的樹，顯然匹配數(shù)為1的樹僅有一類情況，如圖1所示.考慮在圈上其中一個頂點處外接一個懸掛點，有三種連接方式，如v1,v2,v3或v1,v3,v4，均成立，此時圖G僅可能是圖4中的G1,G2,G3,G4.

圖1 匹配數(shù)為1的樹

b.當在圈C4的頂點處外接兩個懸掛點和一個匹配數(shù)為1的樹，此時有三種方式，分別是v1v2,v1v3,v2v3或v1v3,v1v4,v2v3，但其中兩個懸掛點連接方式為v1v2或v1v4時，圖G的匹配數(shù)為4，所以不成立，其余情況成立，此時，圖G只能是圖4中的G5,G6.

a.G=C6顯然成立，因此，圖G只能是圖4中的G7.

b.考慮在圈長為6的圖外加一個懸掛點成立，因此，圖G只能是圖4中的G8.

c.考慮在圈長為6的圖外加兩個懸掛點，當連接方式間隔點為偶數(shù)時導致v(G)=4矛盾，間隔奇數(shù)點時成立，因此，圖G只能是圖4中的G9.

d.考慮在圈長為6的圖外加三個懸掛點，僅有連接在間隔奇數(shù)的頂點上成立，否則圖G的匹配數(shù)是4，不成立，因此，圖G只能是圖4中的G10.

a.匹配數(shù)為2的樹僅有三種情況，如圖2所示的K1,K2和K3.

圖2 圈連接匹配數(shù)為2的樹

連接方式為K1時，在圈C4上連接一個懸掛點有三種方式，連接的頂點分別是v1,v2,v3或v1,v3,v4.因為樹的匹配數(shù)為2已固定，此時相當于在圈長為4的頂點v1上固定一個懸掛點，接著在頂點v1,v2,v3或v1,v3,v4上再加一個懸掛點.加了兩個懸掛點，圖的匹配數(shù)依舊是2，情況成立.當懸掛點連接個數(shù)超過兩個時，相當于是在圈C4上連接三個懸掛點，此時圈C4連接三個懸掛點使得它的匹配數(shù)為3，因此，圖G的匹配數(shù)超過了3，所以懸掛點超過兩個，均不成立，此時圖G只能為圖4中的G11,G12,G13,G14.

連接方式為K2時，在圈上連接一個懸掛點有三種，分別連接v1,v2,v3或v1,v3,v4.在v1處連接懸掛點時由于不滿足引理3的條件E1∩M=φ，不成立.其余情況同K1連接情況一樣，因此，圖G只能為圖4中的G15,G16,G17.

連接方式為K3時，不滿足引理3的條件E1∩M=φ，不成立.

b.當連接兩個匹配數(shù)為1的樹時，根據(jù)圖1所示，連接在圈長為4的圖上有三種連接方式.如圖3所示K4,K5和K6.

圖3 圈長為4的圖連接兩個匹配數(shù)為1的樹

連接方式為K4時，在圈上連接一個懸掛點有三種情況，分別連接頂點v1,v2,v3或v1,v3,v4，同K1連接情況一樣，因此，圖G只能為圖4中的G18,G19,G20,G21.

連接方式為K5時，連接一個懸掛點有兩種情況，分別是連接兩個頂點v1v2,v2v3，但連接在樹與圈的頂點v1v2與條件E1∩M=φ矛盾，不成立，此時圖G只能為圖4中的G22,G23.

連接方式為K6時，連接一個懸掛點有兩種情況，但連接在樹與圈的頂點上v1或v3時與條件E1∩M=φ矛盾，不成立，此時圖G只能為圖4中的G24,G25.

圖4 零維數(shù)為n-6的單圈圖

圖4(續(xù)) 零維數(shù)為n-6的單圈圖

(2)當l=6時，由于條件有l(wèi)=0(mod4)，不滿足，所以沒有圈長為6的圖.

a.G=C8顯然成立，因此，圖G只能為圖4中的G26.

b.當考慮在圈外連接一個懸掛點時成立，因此，圖G只能為圖4中的G27.

c.考慮在圈長為8的圖外連接兩個懸掛點，當間隔點為偶數(shù)時導致v(G)≠4，矛盾.間隔奇數(shù)點時成立，有兩種連接方式，因此，圖G只能為圖4中的G28,G29.

d.考慮在圈長為8的圖外連接三個懸掛點，當間隔點為偶數(shù)時導致v(G)≠4，矛盾.間隔奇數(shù)點時成立，僅有一種連接方式，因此，圖G只能為圖4中的G30.

e.考慮在圈長為8的圖外連接四個懸掛點，當間隔點為偶數(shù)時導致v(G)≠4，矛盾.間隔奇數(shù)點時成立，僅有一種連接方式，因此，圖G只能為圖4中的G31.證畢.

定理2設(shè)G是n(n≥7)階的單圈圖，則η(G)=n-7，當且僅當G屬于圖類Ui(1,2,…,7)(見圖5).

圖5 零維數(shù)為n-7的單圈圖

證明假設(shè)圖G的圈長為l，通過引理1、引理2和引理3有以下情況：

(1)如果l=7，那么，有v(G-Cl)=0，v(G)=3，若在圈外增加懸掛點則會導致圖G的匹配數(shù)增加，因此，僅有G=C7，此時圖G只能是圖5中的U1.

(2)如果l=5，那么，有v(G-Cl)=1，因此，在圈長為5的圖外面連接一個匹配數(shù)為1的樹(如圖1所示).若在圈外再連接懸掛點，那么，導致v(G)≠3，只有一種連接方式，因此，僅有G=C7，此時圖G只能是圖5中的U4.

(3)如果l=3，那么，有v(G-Cl)=2.說明在圈外將會連接一個匹配數(shù)為2的樹(如圖2所示)，或者連接兩個匹配數(shù)為1的樹(如圖3所示).同理，若在圈外再連接懸掛點，則會導致v(G)≠3，因此，僅有G=C7，此時圖G只能是圖5中的U2,U3,U5,U6,U7.

情況2有η(G)=n-7=n-2v(G)=η(G)，那么，2v(G)=7，由于匹配數(shù)為整數(shù)，所以這類情況不存在.

情況3有η(G)=n-7=n-2v(G)+2=η(G)，那么，2v(G)=9，由于匹配數(shù)為整數(shù)，所以這類情況也不存在.證畢.