樹的零度與路覆蓋數(shù)的關(guān)系

陳 潔,王 龍

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

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

1 預備知識

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

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

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

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

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

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

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

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

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

操作A:對G中奇路上任意點與圖P的中心點a相連,其中在懸掛點與圖P相連時p≥1.

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

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

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

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

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

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

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

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

下面來證明n=k+1時的情況.設B是由路P2n+1經(jīng)過k次操作A得到,在B上經(jīng)過1次操作A得到G,此時ρ(G)=ρ(B)+ρ(P)=ρ(B)+p-1+r.若G′是在第(k+1)次操作A中的圖P(除去中心點a的相鄰點和懸掛點)上與P2n連接得到,則ρ(G′)=ρ(B)+ρ(P′)=ρ(B)+p+r.若G′是在B中某個圖P(除去中心點a的相鄰點和懸掛點)上與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)當且僅當G∈T.

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

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

n=1時,G是由路P2n+1經(jīng)過一次操作A后得到時,設x是圖P中p條懸掛路P2s+1上的一個懸掛點,y是與x相鄰唯一頂點,令H=G-x-y.根據(jù)引理1.2,η(H)=η(G),經(jīng)過(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).

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

下面來證明n=k+1時的情況.設B是由路P2n+1經(jīng)過k次操作A得到,在B上經(jīng)過1次操作A得到G.B中奇路上任意點與圖P相連后,設x是圖P中p條懸掛路P2s+1上的任意一個懸掛點,y是與x相鄰唯一頂點,令H=G-x-y.根據(jù)引理1.2,η(H)=η(G),經(jīng)過(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,對圖G,都有η(G)≤ρ(G).假設G?T,證明其都滿足η(G)<ρ(G)即可.設x是G的一個垂點,y是與x相鄰的唯一頂點,令H=G-x-y,要證明η(G)<ρ(G).此時H可分為兩種情況:

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

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

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

證畢.