王 兵, 翟明清

1 刻畫零度和奇異性

設G=(V,E)是一個頂點集為V,邊集為E的圖.A(G)是圖G的鄰接矩陣,R(G)是矩陣A(G)的秩. 對某個非零向量X∈Rn,若存在數(shù)λ使得A(G)X=λX, 則稱λ為A(G)的一個特征值,X為對應λ的特征向量. 圖G的譜是由A(G)的所有特征值(某些特征值可能會重復出現(xiàn))構成的集合.A(G)中的零特征值的個數(shù)稱為圖G的零度, 記為η(G). 當η(G)>0時,稱圖G為奇異圖,否則稱G為非奇異圖.

刻畫零度和奇異性的問題有很好的化學背景[1-3],如 Longuet-Higgins指出,一個二部圖(相當于交替烴)如果是奇異的,則該圖所表示的分子式不穩(wěn)定,并且這個問題對非二部圖也有意義.Collatz 和 Sinogowit提出了刻畫所有奇異圖的問題,該問題至今還沒有得到完全解決.基于這樣的背景,眾多學者開始專門對奇異圖進行研究[4-7],Ashraf 和 Bamdad 研究了圖的奇異性與圖的邊數(shù)之間的關系.后來,Huang 和 Meng[8]將非奇異圖的概念推廣到擬非奇異圖: 如果η(G)≤1, 則G為擬非奇異圖.I. Sciriha 和 I. Gutman 證明了樹的線圖是擬非奇異圖.然而,刻畫非奇異圖(或擬非奇異圖)是一個非常困難的問題,甚至對于樹的線圖,我們?nèi)晕茨芡耆坍嬈浞瞧娈惖淖宇?該問題在文獻[6]中也被作為公開問題提出.

一個圖被稱為區(qū)間圖,如果它的頂點能對應一個實軸上區(qū)間,使得任意兩個頂點鄰接當且僅當它們對應區(qū)間的交非空.k-樹是這樣一個圖類,它可以按如下方式定義:(1)完全圖Kk是最小的k-樹;(2)若G=(V,E)是一個k-樹,G1?G是G的k階完全子圖,取頂點x?V,則H=(V∪{x},E∪{ux|u∈G1})也是k-樹. 圖G被稱為k-路, 如果它既是區(qū)間圖也是一個k-樹. 等價地, 圖G是一個n階k-路,當且僅當G存在一個頂點生成序列v1,v2,…,vn使得E(G)={vivj|0<|i-j|≤k;i,j=1,…,n}.

定理1.1 設t,k為兩個正整數(shù),r=(t+1,k)為t+1和k的最大公約數(shù).則

2 預備知識

首先給出文中將出現(xiàn)的部分符號說明.設Am×n表示一個m×n矩陣,當m=n時,我們用An代替An×n.特別地,分別記0m×n,Jm×n和In為m×n零矩陣,m×n全一陣和n×n單位陣. 矩陣A的轉(zhuǎn)置記為AT,A的(i,j)元記為Aij, 在不引起混淆時,Aij也常表示分塊陣A的(i,j)塊.

X={X1,X2,…,Xt}T∈Rt(k+1)

根據(jù)η(G)的定義, 我們有如下的性質(zhì)：

性質(zhì)2.1 對任意的n階圖G,有

η(G)=n-R(A(G))

證明設C是t(k+1)階方陣, 它的第(i,j)塊記為

其中

為了方便,定義

f(i,j)=xt-i,j+(-1)t-ix1,(j-1)(modk)+

(-1)t-i+1x1,(j-2)(modk)+…+

(-1)tx1,(j-i-1)(modk)

特別地約定f(i,-1)=f(i,k-1), 這里i=0,…,t-1;j=0,1,…,k.

引理2.3 設B,X定義同上. 若BX=0,則xi,0=xi,k,i=1,…,t. 更一般地有

f(i,j)=0,i=0,…,t-1;j=0,…,k

(1)

證明注意到此時BX=0對應的方程組為

(2)

及

(3)

由方程組(3)可以得到

xt,j=-(xt-1,j-xt,j-1)

=(-1)2(xt-2,j-xt-1,j-1)

=…

=(-1)t-1(x1,j-x2,j-1)

=(-1)t-1x1,j-1

(4)

其中j=1,…,k.

將(4)式對j求和,再結(jié)合方程組(2)可得

下面對i進行歸納來證明引理后半部分.注意到方程組(4)暗示著xt,j+(-1)tx1,j-1=0,j=1,…,k.也即i=0時,(1)式成立.由歸納假設可知

xt-(i-1),j=(-1)t-ix1,(j-1)(modk)+

(-1)t-i+1x1,(j-2)(modk)+…+

(-1)t-1x1,[j-(i-1)-1](modk)

其中j=0,1…,k.進一步地,

xt-(i-1),j-1+xt-(i-2),j-1=[(-1)t-ix1,[(j-1)-1](modk)+

(-1)t-i+1x1,[(j-1)-2](modk)+…+

(-1)t-1x1,[j-1-(i-1)-1](modk)]+

[(-1)t-i+1x1,[(j-1)-1](modk)+

(-1)t-i+2x1,[(j-1)-2](modk)+…+

(-1)t-1x1,[j-1-(i-2)-1](modk)]

=(-1)t-1x1,(j-i-1)(modk)

這里i=2,3,…,t-2;j=1,2,…,k. 進一步地,由方程組(3)的最后一組方程可得:

xt-i,j=xt-(i-1),j-1+xt-(i-2),j-1-xt-(i-1),j

=(-1)t-i-1x1,(j-1)(modk)+

(-1)t-ix1,(j-2)(modk)+…+

(-1)t-1x1,(j-i-1)(modk)

則(1)式對i也成立,其中i=1,…,t-1;j=0,1,…,k.(1)式既證.

引理2.4 設B,X定義同上,則方程組BX=0等價于

下面我們將重點考慮分量x1,0,x1,1,…,x1,k-1之間的線性關系.

令r=(t+1,k),由代數(shù)學知識可知,存在一個正整數(shù)a和正奇數(shù)b使得ak-b(t+1)=r.由r的定義,存在兩個正整數(shù)p,q滿足t+1=rp,k=rq并且(p,q)=1.

令g(j)=f(t-1,j-1)+f(t-1,j),則有

g(j)=x1,j-(-1)t+1x1,[j-(t+1)](modk),這里j=0,1,…,k-1.

引理2.5 設B,X定義同上,且BX=0成立.則當t+1是奇數(shù)時,x1,j=(-1)i+1x1,[(i+1)r+j](modk);當t+1是偶數(shù)時,x1,j=x1,[(i+1)r+j](modk).這里i=0,1,…,q-1;j=0,1,…,r-1.

證明由(1)可知對任意的j=0,1,…,k-1, 都有f(t-1,j)=0, 從而g(j)=0, 即x1,j=(-1)t+1x1,[j-(t+1)](modk), 將該等式迭代b次可得

x1,j=(-1)b(t+1)x1,[j-b(t+1)](modk)

(6)

這里j=0,1,…,k-1.

特別地,如果t+1為奇數(shù),則r也是奇數(shù). 由(6)式可得

x1,j=-x1,[r-ak+j](modk)=-x1,(r+j)(modk)

這里j=0,1,…,k-1.

對任意的i=0,1,…,q-1;j=0,1,…,r-1,利用上式迭代i次可得

x1,j=(-1)i+1x1,[(i+1)r+j](modk).

(7)

類似地,如果t+1為偶數(shù),則由(6)式可得x1,j=x1,(r+j)(modk),迭代i次得到

x1,j=x1,[(i+1)r+j](modk)

(8)

其中i=0,1,…,q-1;j=0,1,…,r-1.結(jié)論得證.

同時,引理2.5意味著X1中的k個分量x1,0,x1,1,…,x1,k-1能夠等分成r個集合,每個集合中恰有q個分量(當t+1是奇數(shù)時,集合中相鄰分量互為相反數(shù);當t+1是偶數(shù)時,集合中的分量相等).我們用矩陣X*來表示X1中這些分量的劃分情形,其中X*的每一列對應一個集合,也即

引理2.6 設B,X定義同上,且BX=0成立. 則當t+1為奇(或偶)數(shù)時,若下面k+2個方程構成的方程組

(9)

(9′)

中線性無關的方程的個數(shù)為k+2-l,則

證明首先考慮t+1為奇數(shù)的情形. 此時,容易驗證方程組

與

(10)

是等價的. 進一步可以驗證方程組

g(j)=0,j=0,1,…,k-1

與

x1,j=(-1)i+1x1,[(i+1)r+j](modk)

其中i=1,…,q-1;j=0,1,…,r-1

也是等價的.也即方程組(9)與(10)等價.

注意到方程組(5)為方程組(10)與

(11)

的聯(lián)立方程組. 而由f(i,j)的定義可知,方程組(11)和方程組(10)彼此獨立,同時(11)中的方程也是線性無關的.從而(5)中的聯(lián)立方程組恰好比方程組(10)多(t-1)(k+1)+1個線性無關方程. 因此,當方程組(9)中線性無關的方程的個數(shù)為k+2-l時,由性質(zhì)2.1,引理2.2和2.4就有

η(Pkt(k+1))=t(k+1)-R(B)

=t(k+1)-(t-1)(k+1)-1-(k+2-l)

=l-2.

t+1為偶數(shù)時的情形類似可證,不再贅述.

3 定理的證明

定理1.1的證明我們先假定t+1為奇數(shù).

當k為奇數(shù)時,q也為奇數(shù).在(7)式中取i=q-1可得

x1,j=(-1)q-1+1x1,[(q-1+1)r+j](mod k)=-x1,j

當k為偶數(shù)時,則q也為偶數(shù).由(7)式可知x1,ir+j=(-1)ix1,j對i=1,…,q-1成立.則

(12)

現(xiàn)在假設t+1是偶數(shù).

首先注意到方程組(9′)中包含r個恒等方程x1,j=x1,[(q-1+1)r+j](modk)=x1,j,j=0,1,…,r-1. 同時,類似于(12)式的推導可得

(13)

當k為偶數(shù)時,r也為偶數(shù).由(8)式和(13)式分別可得

為了證明定理1.2,我們先給出下面的引理.

證明首先令n=t(k+1).則

這里

類似于引理2.2的證明,設

其中C定義同前文.注意到C*為非奇異陣且

引理后面部分的證明類似于前面,這里省略了.

[參 考 文 獻]

[1] L.Collatz,U.Sinogowitz. Spektren endlicher Grafen[J]. Abh Math Sem Univ Hamburg,1957 (21): 63-77.

[2] C.Longuet-Higgins. Resonance structures and MO in unsaturated hydrocarbons[J].Journal of Chemistry and Physics,1950(18): 265-274.

[3] D. M.Cvetlpvoc,I.Gutman,N.rinajstic. Graph theory and molecular orbitals [J].Chem Acta,1972(44): 365-374.

[4] I. Gutman, J.W. Kennedy, B.Servatius. Tree singularity and a chemical background to singular graphs[J]. Graph Theory Notes New York. 1994 (27): 33-41.

[5] I.Sciriha. The two classes of singular line graphs of trees[J].Rend Sem Mat Messina,Ser II,1999(5):167-180.

[6] I. Sciriha, I. Gutman. On the nullity of line graphs of trees[J]. Discrete Math,2001(232): 35-45.

[7] F. Ashraf, H. Bamdad. A note on graphs with zero nullity[J].Match Commun Math Comput Chem,2008(60): 15-19.

[8] Q.X. Huang, J.X. Meng. The nullity of quasi-nonsingular graph[J]. Discrete Math,to appear.