何博瑞，房明磊

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

零度問題的研究是圖論中一個(gè)熱門問題.20世紀(jì)50年代，Collatz和Sinogowitz提出關(guān)于刻畫所有奇異圖的問題.過去二十年，關(guān)于圖的零度問題吸引了眾多的圖論學(xué)家和化學(xué)家的注意力.在文獻(xiàn)[1-11]中，作者對(duì)單圈圖的零度關(guān)系進(jìn)行了廣泛研究.譚學(xué)忠和柳柏濂[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當(dāng)且僅當(dāng)G屬于圖類Gi(i=1,2,…,31)(見圖4).

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

情況1η(G)=n-6=n-2v(G)-1=η(G)，顯然2v(G)=5，因?yàn)槠ヅ鋽?shù)均為正整數(shù)，所以不成立.

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

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

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

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

b.考慮在圈長(zhǎng)為6的圖外加一個(gè)懸掛點(diǎn)成立，因此，圖G只能是圖4中的G8.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

b.當(dāng)考慮在圈外連接一個(gè)懸掛點(diǎn)時(shí)成立，因此，圖G只能為圖4中的G27.

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

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

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

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

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

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

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

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

(3)如果l=3，那么，有v(G-Cl)=2.說明在圈外將會(huì)連接一個(gè)匹配數(shù)為2的樹(如圖2所示)，或者連接兩個(gè)匹配數(shù)為1的樹(如圖3所示).同理，若在圈外再連接懸掛點(diǎn)，則會(huì)導(dǎo)致v(G)≠3，因此，僅有G=C7，此時(shí)圖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ù)，所以這類情況也不存在.證畢.