錢(qián)克仕，李小新

（池州學(xué)院 數(shù)學(xué)計(jì)算機(jī)科學(xué)系，安徽 池州 247000）

含割邊的圖的零維數(shù)

錢(qián)克仕，李小新

（池州學(xué)院 數(shù)學(xué)計(jì)算機(jī)科學(xué)系，安徽 池州 247000）

圖的零維數(shù)定義為圖的零特征值的重?cái)?shù).本文討論含割邊的圖的零維數(shù),給出了該類(lèi)圖的零維數(shù)集,并刻畫(huà)了零維數(shù)達(dá)到極大時(shí)的圖結(jié)構(gòu).

圖;鄰接矩陣;譜;零維數(shù);割邊

1 引言

設(shè)G是n階簡(jiǎn)單圖,圖G的鄰接矩陣A(G)是一個(gè)n×n階對(duì)稱矩陣[aij],其中當(dāng)頂點(diǎn)與頂點(diǎn)相鄰時(shí),aij= 1當(dāng)頂點(diǎn)vi與頂點(diǎn)vj不相鄰時(shí),aij=0.稱A(G)的特征值為圖G的特征值.圖G的所有特征值構(gòu)成的集合(多重集)稱為圖G的譜.在圖G的譜中零特征值的重?cái)?shù)稱為G的零維數(shù),記為η(G).如果η(G)=0,則稱圖G非奇異.令Gn為具有特定性質(zhì)的n階簡(jiǎn)單圖構(gòu)成的集合,我們稱數(shù)集為的零維數(shù)集。

1957年,Collatz和Sinogowitz[1]在考慮分子結(jié)構(gòu)穩(wěn)定性的問(wèn)題時(shí)首先提出關(guān)于圖的奇異性刻畫(huà)問(wèn)題.這個(gè)問(wèn)題無(wú)論在化學(xué)中還是在數(shù)學(xué)中都有很重要的意義.對(duì)于一個(gè)二部圖G(對(duì)應(yīng)于一個(gè)碳?xì)浠衔锏姆肿訄D)來(lái)說(shuō),η(G)＞0意味著這種圖所代表的分子是不穩(wěn)定的.而由矩陣知識(shí)易見(jiàn)η(G)＞0當(dāng)且僅A(G)當(dāng)奇異,這對(duì)數(shù)學(xué)本身的研究也很有意義.

目前,關(guān)于圖的奇異性刻畫(huà)問(wèn)題尚未完全解決,僅局限于一些簡(jiǎn)單的情形,如樹(shù),單圈圖,雙圈圖,含懸掛點(diǎn)的圖,以及具有極端零維數(shù)的圖刻畫(huà)等.在文獻(xiàn)[2]中樹(shù)的零維數(shù)可通過(guò)極大匹配獲得.譚學(xué)忠和柳伯鐮[5]給出了n(≥5)階單圈圖的零維數(shù)集,即為并刻畫(huà)了η(G)=n-4時(shí)的單圈圖G,提出了關(guān)于非奇異單圈圖的一個(gè)公開(kāi)問(wèn)題.李薇和常安在文獻(xiàn)[6]中解決了這一問(wèn)題.扈生彪[7]等給出了n(≥6)階雙圈圖的零維數(shù)集,即為并刻畫(huà)了極值情形.另外,文獻(xiàn)[9]給出零維數(shù)為1的圖的構(gòu)造方法,文獻(xiàn)[10]給出了非奇異無(wú)圈圖及單圈圖的另一種刻畫(huà).在近期的文獻(xiàn)中,程波,柳伯濂[8]討論了一般n階圖G的零維數(shù)達(dá)到n-2及n-3的情形,并探討了給定頂點(diǎn)數(shù)與邊數(shù)時(shí)圖的零維數(shù)達(dá)到極大值的情形.進(jìn)一步地,李書(shū)超[4]刻畫(huà)了含懸掛點(diǎn)的階圖的零維數(shù)達(dá)到n-4與n-5的情形.

本文主要研究了含割邊的圖的零維數(shù)情況,給出了該類(lèi)圖的零維數(shù)集,并刻畫(huà)了零維數(shù)達(dá)到極大時(shí)的圖結(jié)構(gòu).

2 定義和引理

設(shè)G=(V,E)為簡(jiǎn)單圖.對(duì)G中任一頂點(diǎn)v,dG(v)t和NG(v)分別表示v在G中的度與鄰點(diǎn)集.用ω (G)來(lái)表示圖G的連通分支數(shù).設(shè)F是E(G)的一個(gè)子集,用G-F表示G在圖中刪去F中的邊后所得到的圖.設(shè)W是E(G)的一個(gè)子集,G-W表示在圖G中刪去W中的頂點(diǎn)以及所有與W中點(diǎn)關(guān)聯(lián)的邊所得到的圖.若G中的一邊e滿足ω(G-e)＞ω(G)則稱e是G的割邊.若dG(v)=1,則v稱為G的一個(gè)懸掛點(diǎn),與v關(guān)聯(lián)的邊稱為G的一條懸掛邊.若圖G不含邊,則G稱為空?qǐng)D.若G不是空?qǐng)D,顯然有η(G)≤n-2.更多圖的術(shù)語(yǔ)參看文獻(xiàn)[3].

圖1 引理2.1中的圖G和H

引理2.1設(shè)圖G為一個(gè)含有割邊e=uw的簡(jiǎn)單圖.刪除點(diǎn)u,w以及它們關(guān)聯(lián)的邊,并把NG-e(u)中的每個(gè)頂點(diǎn)NG-e(w)和中的每個(gè)頂點(diǎn)連接,得到一個(gè)新圖H,則η(G)=η(H).

證明:不失一般性,假設(shè)圖G連通.則G的結(jié)構(gòu)如圖1(1)所示,其中,NG-e(u)=:U,NG-e(w)=:W.設(shè)x為G對(duì)應(yīng)零特征值的一個(gè)特征向量,并設(shè)x(u)=α,x(w)=β,則根據(jù)特征向量方程

顯然,懸掛邊也是一條割邊,因此,我們有引理2.2[2]設(shè)G為n階簡(jiǎn)單圖,u∈V(G)為中G的一個(gè)懸掛點(diǎn),uv∈E(G)為對(duì)應(yīng)的懸掛邊,則η(G-u,｛ ｝v).

3 主要結(jié)果

引理3.1[2]設(shè)為階簡(jiǎn)單圖,G=G1+G2+…+Gt,其中G1、G2、Gt為G的t個(gè)連通分支.則(G);從而η(G)=n當(dāng)且僅當(dāng)為空?qǐng)D.

定理 3.2 設(shè)G為一個(gè)n階含割邊的連通圖.則η(G)=n-2當(dāng)且僅當(dāng)G是一個(gè)星圖.若不是星圖,則η(G)≤n-4.

證明:設(shè)e為G的一條割邊.由引理2.1,η(G) =η(H),其中H是通過(guò)刪除割邊e的兩個(gè)端點(diǎn)并將中的頂點(diǎn)與中的頂點(diǎn)連接所得到的一個(gè)n-2階圖.由引理3.1,η(H)=n-2當(dāng)且僅當(dāng)是一個(gè)空?qǐng)D,當(dāng)且僅當(dāng)G是一個(gè)星圖.若G不是星圖,則H不是空?qǐng)D,從而η(G)=η(H)≤n-2-2=n-4.得證.

用Qn表示n所有階含割邊的圖的集合.

定理5 Qn的零維數(shù)集為 ｛n-2,n-4,n-5…｝.

證明:對(duì)于Qn中任一含割邊的圖G,由定理4知 η(G)∈ ｛n-2,n-4,n-5…,,0｝對(duì)任意,n-k∈ ｛n-2,n-4,n-5…,,0｝, k∈ ｛n,n-1,5,4,2 ｝考慮圖2中的含割邊的圖.當(dāng)k為偶數(shù)時(shí),由引理2.2,連續(xù)刪去路的懸掛點(diǎn)及其關(guān)聯(lián)的邊（當(dāng)k=2時(shí)不刪）,其零維數(shù)不變,最終得到一個(gè)n-k-2階的星圖,其零維數(shù)為n-k.當(dāng)k為奇數(shù)時(shí)（注意到k≠3）,由引理2.2連續(xù)刪去路的懸掛點(diǎn)及其關(guān)聯(lián)的邊,其零維數(shù)不變,最終得到一個(gè)三角形和n-k個(gè)孤立點(diǎn)構(gòu)成的圖,由引理3.1其零維數(shù)為. n-k得證。

圖2兩類(lèi)含割邊的圖,其中K為K≥2偶數(shù)時(shí),K為奇數(shù)時(shí)K≥5

[1]Collatz L,Sinogowitz U.Spektren endlicher grafen[J].Abh. Math.Sere.Univ.Hamburg.1957,21：70-75．

[2]Cvetkovic D,Doob M,Sachs H.Spectra of Graphs[M].New York:Academic Press,1980.

[3]Bondy J A,Murty U S R.Graph Theory with Applications [M].London and Basingstoke:The Mac Millan Press,1976.

[4]Li S Ch.On the nullity of graphs with pendent vertices[J]. Linear Algebra Appl.,2008,429:1619-1628.

[5]Tan X Zh,Liu B L.On the nullity of unicyclic graphs[J]. Linear Algebra Appl.,2003,408:12-220.

[6]Li W,Chang An.Describing the nonsingular unicyclic graph [J].Jounal of Mathematical Study,2007,4:442-445.

[7]Hu S,Liu B L,Tan X Zh.On the nullity of bicyclic graphs [J].Linear Algebra Appl.,2008,429:1387-1391.

[8]Chen B,Liu B L.On the nullity of graphs[J].Electronic Journal of Linear Algebra,2007,16:60-67.

[9]Sciriha I.On the construction of graphs of nullity one[J]. Discret Math.,1998,181:193-211.

[10]Nath M,Sarma B K.On the null-spaces of acyclic and unicyclic singular graphs[J].Linear Algebra Appl.,2007,427:42-54.

[責(zé)任編輯：曹懷火]

0157

A

1674-1102（2010）03-0005-02

2010-03-30

安徽省教育廳自然科學(xué)研究項(xiàng)目(KJ2010B136)；池州學(xué)院引進(jìn)研究生科研啟動(dòng)項(xiàng)目(2009RC011)。

錢(qián)克仕(1984—),男,安徽六安人,池州學(xué)院數(shù)學(xué)計(jì)算機(jī)科學(xué)系教師,碩士,研究方向?yàn)樽V圖理論及應(yīng)用；李小新(1976—),男,安徽懷寧人,池州學(xué)院數(shù)學(xué)計(jì)算機(jī)科學(xué)系副教授,碩士,研究方向?yàn)榇鷶?shù)圖論。