陳 潔,王 龍

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

本文主要研究的是樹的零度與路徑覆蓋數(shù)之間的關(guān)系,刻畫了所有滿足η(G)=ρ(G)的樹.與Wang在文獻(xiàn)[15]中描述的區(qū)別在于其刻畫的是塊都是圈和團(tuán)組成的圖,本文研究的是連通的無(wú)圈圖的零度與路覆蓋數(shù)之間的關(guān)系.

1 預(yù)備知識(shí)

本文研究的是無(wú)向的樹,樹是指任意兩個(gè)頂點(diǎn)之間有且只有一條路徑的無(wú)圈圖.記簡(jiǎn)單無(wú)向圖G的頂點(diǎn)集為V(G),邊集為E(G).圖G的鄰接矩陣A(G)=(aij)n′n,其中若vi與vj相鄰,則aij=1;否則aij=0.圖G的秩定義為其鄰接矩陣A(G)的秩,零度定義為其鄰接矩陣A(G)零特征值的重?cái)?shù),分別用r(G),η(G)表示,兩者之間存在等式r(G)+η(G)=|V(G)|.圖的路覆蓋是指圖G中一組頂點(diǎn)不相交的誘導(dǎo)路(單個(gè)頂點(diǎn)的路徑長(zhǎng)為0)的集合,使G的每個(gè)頂點(diǎn)都是其中一條路的頂點(diǎn),G的路覆蓋數(shù)是指G的最小路覆蓋,用ρ(G)表示.圖G中點(diǎn)x的度表示與x相鄰的邊的數(shù)目,記作dG(x).若dG(x)=1,則點(diǎn)x表示圖G的一個(gè)懸掛點(diǎn).G中一條路P只有一個(gè)頂點(diǎn)與G中其他部分相連接,則稱路P是圖G的一個(gè)懸掛路.用G-U表示從圖G中刪去U的頂點(diǎn)及其相關(guān)聯(lián)的邊,其中U?V(G),若H是圖G的誘導(dǎo)子圖,直接用符號(hào)G-H表示.對(duì)于誘導(dǎo)子圖H和H外一點(diǎn)x,頂點(diǎn)集V(H)∪{x}的G的誘導(dǎo)子圖可記為H+x.用Pn表示有n個(gè)頂點(diǎn)的路.

下面給出本文結(jié)論證明中需要用到的一些重要引理.

引理1.1[14]:對(duì)一條路Pn,若n是奇數(shù),則η(Pn)=1;若n是偶數(shù),則η(Pn)=0.

引理1.2[14]:設(shè)G是包含一個(gè)懸掛點(diǎn)的圖,圖H是由G刪去這個(gè)懸掛點(diǎn)及其相鄰的點(diǎn)得到的誘導(dǎo)子圖,則η(G)=η(H).

引理1.3[15]:設(shè)G是包含一個(gè)懸掛點(diǎn)的圖,圖H是由G刪去這個(gè)懸掛點(diǎn)及其相鄰的點(diǎn)得到的誘導(dǎo)子圖,則ρ(H)≤ρ(G).

引理1.4[15]:若G是連通圖,則η(G)≤ρ(G).

2 主要結(jié)果及證明

Wang[15]給出并證明了連通圖G的零度與路覆蓋數(shù)之間存在η(G)≤ρ(G)的關(guān)系,因此當(dāng)G是樹時(shí),其零度和路徑覆蓋數(shù)之間也存在關(guān)系式η(G)≤ρ(G).下面我們來(lái)討論在樹中η(G)=ρ(G)成立的充分必要條件.首先給出了一些相關(guān)圖、操作以及集合的定義.

圖P:中心點(diǎn)a的度為p+r,有p+r條懸掛路P2s+1,其中r條懸掛路P2s+1上與中心點(diǎn)a相鄰的頂點(diǎn)與一條P2s的懸掛點(diǎn)相連接(p≥2,r≥0).

操作A:對(duì)G中奇路上任意點(diǎn)與圖P的中心點(diǎn)a相連,其中在懸掛點(diǎn)與圖P相連時(shí)p≥1.

定義集合T:1)奇路P2n+1∈T;2)若圖G∈T,對(duì)G進(jìn)行操作A得到G′,則G′∈T.

在證明樹中η(G)=ρ(G)成立的充分必要條件之前我們先給出一個(gè)引理及其證明.

引理2.1:若圖G∈T,在G的非懸掛點(diǎn)上與P2n的一個(gè)懸掛點(diǎn)相連后得到G′,G′?T則ρ(G′)=ρ(G)+1.

證明：G是路P2n+1時(shí),ρ(G)=1.在P2n+1非懸掛點(diǎn)上與P2n的一個(gè)懸掛點(diǎn)相連得到G′,G′?T,ρ(G′)=2.有ρ(G′)=ρ(G)+1.

若P′是圖P中心點(diǎn)a的相鄰點(diǎn)與P2n的一個(gè)懸掛點(diǎn)連接時(shí)得到的圖,此時(shí),P′∈T,則是在圖P(除去中心點(diǎn)a的相鄰點(diǎn)和懸掛點(diǎn))上與P2n的一個(gè)懸掛點(diǎn)相連得到,則ρ(P′)=p-1+r+1=p+r.

若G是由路P2n+1經(jīng)過(guò)n次操作A得到,G′是在圖G的非懸掛點(diǎn)上與P2n的一個(gè)懸掛點(diǎn)相連得到,G′?T.用歸納法來(lái)證明.

n=1時(shí),ρ(G)=1+ρ(P)=1+p-1+r=p+r,ρ(G′)=1+ρ(P′)=1+p+r.有ρ(G′)=ρ(G)+1.

假設(shè)n=k時(shí),ρ(G′)=ρ(G)+1成立.

下面來(lái)證明n=k+1時(shí)的情況.設(shè)B是由路P2n+1經(jīng)過(guò)k次操作A得到,在B上經(jīng)過(guò)1次操作A得到G,此時(shí)ρ(G)=ρ(B)+ρ(P)=ρ(B)+p-1+r.若G′是在第(k+1)次操作A中的圖P(除去中心點(diǎn)a的相鄰點(diǎn)和懸掛點(diǎn))上與P2n連接得到,則ρ(G′)=ρ(B)+ρ(P′)=ρ(B)+p+r.若G′是在B中某個(gè)圖P(除去中心點(diǎn)a的相鄰點(diǎn)和懸掛點(diǎn))上與P2n連接得到,則ρ(G′)=ρ(B+P2n)+ρ(P).又ρ(B+P2n)=ρ(B)+1,則ρ(G′)=ρ(B+P2n)+ρ(P)=ρ(B)+1+p-1+r=ρ(B)+p+r.有ρ(G′)=ρ(G)+1.

證畢.

定理2.2:若G是樹,η(H)=ρ(G)當(dāng)且僅當(dāng)G∈T.

證明：首先證明充分性.若G是路P2n+1,η(G)=1,ρ(G)=1.則η(G)=ρ(G).

若G是由路P2n+1經(jīng)過(guò)n次操作A得到,用歸納法來(lái)證明.

n=1時(shí),G是由路P2n+1經(jīng)過(guò)一次操作A后得到時(shí),設(shè)x是圖P中p條懸掛路P2s+1上的一個(gè)懸掛點(diǎn),y是與x相鄰唯一頂點(diǎn),令H=G-x-y.根據(jù)引理1.2,η(H)=η(G),經(jīng)過(guò)(s+1)次操作后,得到一條奇路P2n+1,p-1條路P2s+1和r條奇路,則η(G)=η(P2n+1)+(p-1)η(P2s+1)+r=p+r.又ρ(G)=1+p-1+r=p+r,則η(G)=ρ(G).

假設(shè)n=k時(shí),η(G)=ρ(G)成立.

下面來(lái)證明n=k+1時(shí)的情況.設(shè)B是由路P2n+1經(jīng)過(guò)k次操作A得到,在B上經(jīng)過(guò)1次操作A得到G.B中奇路上任意點(diǎn)與圖P相連后,設(shè)x是圖P中p條懸掛路P2s+1上的任意一個(gè)懸掛點(diǎn),y是與x相鄰唯一頂點(diǎn),令H=G-x-y.根據(jù)引理1.2,η(H)=η(G),經(jīng)過(guò)(s+1)次操作后,得到圖B和(p-1)條路P2s+1和r條奇路,則

η(G)=η(B)+(p-1)η(P2s+1)+r=η(B)+p-1+r

又ρ(G)=ρ(B)+p-1+r,且η(B)=ρ(B),則η(G)=ρ(G).

必要性:根據(jù)引理1.4,對(duì)圖G,都有η(G)≤ρ(G).假設(shè)G?T,證明其都滿足η(G)<ρ(G)即可.設(shè)x是G的一個(gè)垂點(diǎn),y是與x相鄰的唯一頂點(diǎn),令H=G-x-y,要證明η(G)<ρ(G).此時(shí)H可分為兩種情況:

情況1:H?T,由引理1.2,得到η(H)=η(G),由引理1.3得到ρ(H)≤ρ(G).對(duì)G的頂點(diǎn)進(jìn)行歸納,K2?T,利用數(shù)學(xué)歸納法,由于H=G-K2是G的子圖,假設(shè)η(H)<ρ(H),則

η(G)=η(H)<ρ(H)≤ρ(G)

情況2:H∈T,則G是在H中除了懸掛點(diǎn)的任意頂點(diǎn)上連接一個(gè)路P2得到的圖,設(shè)x是路P2與H相連后的路P2上的懸掛點(diǎn),y是與x相鄰唯一頂點(diǎn),令H=G-x-y,根據(jù)引理1.2,η(H)=η(G).又根據(jù)充分性中證明有η(H)=ρ(H),則η(G)=ρ(H).根據(jù)引理2.1,此時(shí)ρ(G)=ρ(H)+1,則η(G)<ρ(G).

證畢.