斜秩等于圍長(zhǎng)的定向單圈圖的刻畫(huà)

王 震, 馬曉玢

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

記簡(jiǎn)單圖G=(V(G),E(G)).如果G是一個(gè)連通圖且|V(G)|=|E(G)|, 則稱(chēng)G是一個(gè)單圈圖.本文考慮基于單圈圖G的定向圖Gσ, 即對(duì)任意不同頂點(diǎn)對(duì)u,v, 弧(u,v)∈E(Gσ)與弧(v,u)∈E(Gσ)至多只有一個(gè)成立.定向圖Gσ的斜鄰接矩陣定義為一個(gè)n×n矩陣S(Gσ)=(suv), 其中suv=-svu=-1當(dāng)且僅當(dāng)(u,v)∈E(Gσ), 否則suv=0.任意定向圖的斜鄰接矩陣都是反對(duì)稱(chēng)的, 從而斜秩總是偶數(shù).如果圖Gσ中的一個(gè)頂點(diǎn)的度為1, 則稱(chēng)該頂點(diǎn)為懸掛點(diǎn), 與懸掛點(diǎn)鄰接的頂點(diǎn)稱(chēng)為擬懸掛點(diǎn).圖Hσ稱(chēng)為圖Gσ的導(dǎo)出子圖, 如果H是G的一個(gè)子圖, 并滿足: 對(duì)任意頂點(diǎn)對(duì)u、v∈V(Hσ), (u,v)∈E(Hσ)當(dāng)且僅當(dāng)(u,v)∈E(Gσ).本文中, 圖Gσ中的兩個(gè)頂點(diǎn)u和v之間的距離指它們?cè)诘讏DG中的距離, 記為d(u,v).若Hσ是Gσ的子圖且u∈V(G)V(H), 記d(u,H)=min{d(u,v),v∈V(H)}.定向圖Gσ的圍長(zhǎng)是其底圖G的圍長(zhǎng),即G中最短圈的長(zhǎng)度, 記為g(G).

圖1 單圈圖上的一個(gè)Ⅰ- 型懸掛星Figure 1 An unicyclic graph with a Ⅰ- type pendant star

圖2 單圈圖上的一個(gè)Ⅱ- 型懸掛星Figure 2 An unicyclic graph with a Ⅱ- type pendant star

對(duì)簡(jiǎn)單圖G, 圖G的秩r(G)與結(jié)構(gòu)參數(shù)的關(guān)系是近年來(lái)圖譜理論的熱點(diǎn)問(wèn)題之一.其中, Wong[1]等首次發(fā)現(xiàn)了r(G)與其直徑d(G)的關(guān)系, 即對(duì)任意圖G,總有r(G)≥d(G).他們還刻畫(huà)了r(G)=d(G)時(shí)的所有圖.Ma[2]等緊接著刻畫(huà)了r(G)=d(G)-1的所有圖.S.Gong[3]等研究了帶切點(diǎn)的圖的零度.Zhou[4]等得到了秩與圍長(zhǎng)g(G)的關(guān)系, 即r(G)≥g(G)-2, 并刻畫(huà)了滿足r(G)=g(G)-2,r(G)=g(G)-1或r(G)=g(G)的所有圖.針對(duì)定向圖, Adiga[5]等描述了有向圖的斜能量知識(shí).Y.Guo[6]等研究了具有小圍長(zhǎng)平面圖的強(qiáng)邊染色問(wèn)題.Luo[11]刻畫(huà)了|sr(Gσ)-r(G) |=2d(G)以及sr(Gσ)/r(G)=1+d(G) )的所有圖.Wong[12]等發(fā)現(xiàn)了定向圖的sr(Gσ)及其底圖的r(G)的關(guān)系, 即sr(Gσ)-r(G)≤2d(G), 并刻畫(huà)了sr(Gσ)-r(G)=2d(G)的所有圖.鄭連江[10]等運(yùn)用奇異值不等式，得到了有向圖斜能量和去邊后的有向子圖斜能量之間的若干性質(zhì).本文刻畫(huà)了斜秩等于圍長(zhǎng)的定向單圈圖, 即針對(duì)定向單圈圖給出了sr(Gσ)=g(G)的充要條件.

1 相關(guān)引理

引理1[7-10]

1) 設(shè)Hσ是圖Gσ的一個(gè)導(dǎo)出子圖, 則sr(Gσ)≥sr(Hσ).

3) 設(shè)Gσ是一個(gè)定向圖, 則sr(Gσ)=0當(dāng)且僅當(dāng)Gσ是一個(gè)無(wú)邊圖(空?qǐng)D).

引理4[9-10,14-15]設(shè)Gσ是一個(gè)定向圖,v是Gσ的懸掛頂點(diǎn)且u是懸掛頂點(diǎn)v的唯一鄰點(diǎn), 則

sr(Gσ)=sr(Gσ-v-u)+2.

2 主要結(jié)果

充分性證明: 依據(jù)Gσ滿足以上三個(gè)條件之一, 我們分別討論以下情形.

若k=1, 圈上的一個(gè)頂點(diǎn)vi1有Ⅰ- 型懸掛星.刪除該懸掛星后得到一條定向路, 記為Pσ.根據(jù)引理3和引理4, 可得sr(Gσ)=sr(Pσ)+2,sr(Pσ)=g-2, 從而sr(Gσ)=g.

情形1: 存在頂點(diǎn)x使得d(x,Cg)≥3, 此時(shí)必存在頂點(diǎn)x,y,u,v, 使得xyuv是G中Cg上頂點(diǎn)v的一條懸掛路.設(shè)Hσ是Gσ的由V(Cg)∪{u,x,y}導(dǎo)出的子圖.刪除Hσ中頂點(diǎn)x,y,u,v得到一條定向路, 記為Pσ.則根據(jù)引理1, 引理3與引理4分別有sr(Gσ)≥sr(Hσ),sr(Hσ)≥sr(Pσ)+4以及sr(Pσ)≥g-2.從而sr(Gσ)≥g+2, 此時(shí)與題意矛盾, 從而此情形不成立.

如果k=1, 刪除該懸掛星后得到一條定向路, 記為Pσ.根據(jù)引理4, 可得sr(Gσ)=sr(Pσ)+2.由于sr(Gσ)=g, 則sr(Pσ)=g-2.因此g是偶數(shù), 即g≡0 (mod2).