第二大符號距離特征值屬于[-1,(17-)/2] 的符號圖?

楊博遠，李丹

(新疆大學數學與系統科學學院，新疆烏魯木齊 830017)

0 引言

符號圖Σ=(G,σ) 是由它的底圖G=(V,E) 與符號函數σ:E→{-1,1} 組成. 在符號圖中, 用±1 來表示邊的符號. 設M=M(Σ) 為符號圖Σ=(G,σ) 的實矩陣, 且PM(λ)=det(λI-M) 是M-多項式. 一個矩陣的全部特征值(包括重數) 集合稱為該矩陣的譜, 稱M的譜為符號圖Σ 的M-譜. 一般的, 將M的譜表示為λ1(M)≥λ2(M)≥···≥λn(M). 矩陣M特征值模的最大值稱為矩陣M的譜半徑. 用u～v表示頂點u與v相鄰, 用u?v表示頂點u與v不相鄰. 定義Σ 中路徑P的符號為σ(P)=Πe∈E(P)σ(e). 設P(u,v)是頂點u與v之間的最短路徑, 令P(u,v)={P(u,v)|{u,v}?V(G)}. 頂點u與v之間最短路徑的長度定義為u與v之間的距離, 用duv表示. 圖G的直徑是圖G中所有頂點間距離的最大值, 記作diam(G). 符號圖Σ 的直徑即為其底圖G的直徑. 鄰接矩陣A=A(Σ)=(aij) 是n×n階矩陣, 其中若vi～vj, 則aij=σ(vivj), 否則等于0. 符號圖最初是由Harary[1]用于研究社交網絡模型而引入. 隨后Zaslavsky[2]應用了符號圖的一種等價性. Chaiken[3]和Zaslavsky[2]分別得出了符號圖的矩陣-樹定理. Harary[1]也給出了符號圖平衡性的概念. 如果符號圈包含偶(奇)數條負邊, 則稱其是正(負) 圈. 若符號圖的所有圈均為正, 則稱其為平衡的; 否則稱其為非平衡的. 一般圖可以看作是(平衡的) 符號圖, 其中所有邊均為正. Koledin 等[4]在給定階數、邊數以及負邊個數的符號圖類中研究了最大鄰接特征值達到最大的連通符號圖. 設Un(或Bn)分別表示非平衡的n階單(或雙) 圈符號圖的集合.Akbari 等[5]在Un中研究了最大鄰接特征值達到最大的符號極圖. Souri 等[6]在給定圍長的符號單圈圖類中刻畫了最大鄰接特征值達到最大的符號圖. 當n≥36 時, He 等[7]在Bn中研究了最大鄰接特征值前五大的符號圖.Belardo 等[8]在Un和Bn中分別考慮了譜半徑達到最大和最小的符號圖.

令σmax(u,v)=max{σ(P(u,v))|P(u,v)∈P(u,v)},σmin(u,v)=min{σ(P(u,v))|P(u,v)∈P(u,v)} 及dmax(u,v)=σmax(u,v)d(u,v),dmin(u,v)=σmin(u,v)d(u,v). Hameed 等[9]給出了符號圖的兩類距離矩陣的定義:

與

設u,v∈V(Σ), 若dmax(u,v)=dmin(u,v), 則稱u和v是距離-可兼容的(簡稱為可兼容的). 如果Σ 中任意兩個頂點都是可兼容的,則稱Σ 是可兼容的,此時令Dmax(Σ)=Dmin(Σ):=D±(Σ). 設D(G)=(duv)n×n是連通圖G的距離矩陣. 如果Σ 的所有邊都是正的, 顯然Dmax(Σ)=Dmin(Σ)=D(G). Shijin 等[10]利用因子圖的符號距離矩陣研究了符號圖乘積的符號距離矩陣, 如Cartesian 積和Lexicographic 積, 此外還討論了一些特殊符號圖乘積的距離譜. 對應符號圖的兩類符號距離矩陣, Roy 等[11]定義了兩類符號距離Laplacian 矩陣, 利用這些矩陣刻畫了符號圖的平衡性,并且得到了一些非平衡符號圖類的符號距離Laplacian 譜.最近, Li 等[12]給出了關于直徑至少為2 的符號圖最小距離特征值的上界.

距離特征值的研究可以追溯到Graham 等[13]關于負的距離特征值個數與處理數據通訊系統問題之間關系的研究. 生成路和生成圈分別稱為Hamilton 路和Hamilton 圈. Lin 等[14]在不含Hamilton 圈的n階連通圖類中, 刻畫了距離譜半徑達到最小的圖. 用Sn表示n階星圖. 圖G的獨立數α(G) 是指G中最大獨立集的頂點數. Fajtlowicz[15]提出了關于距離特征值和圖不變量的猜想: 設圖G是獨立數α(G) ≤2 的連通圖, 那么λ2(D(G))≤tr(G), 其中tr(G) 表示圖G中三圈的個數. Lin[16]證明了該猜想. 圖Sn,p+1是在星圖Sp+1和星圖Sn-p-1的最大度點之間加一條邊得到的n階雙星圖, 其中1 ≤p≤?(n-2)/2」. 在圖G每對距離至多為k的頂點之間加一條邊得到的(簡單) 圖稱為圖G的k次冪, 記作Gk. Xing 等[17]刻畫了的樹, 并且給出了連通圖k次冪的第二大距離特征值的下界. Lin[18]得到了與直徑有關的λ2(D(G)) 的上界. Xue等[19]給出了第二大距離特征值不超過-(1/2) 的所有塊圖. Xing 等[20]刻畫了的所有n階連通圖. Liu 等[21]刻畫了的所有n階連通圖. 受以上研究的啟發,本文主要考慮以下問題.

問題1第二大距離特征值屬于的全部連通符號圖有哪些?

1 準備知識

除非另有說明, 否則本文中符號圖的底圖均簡單且連通.

引理1[9]符號圖的下列性質是等價的.

(1) Σ 是平衡的;

引理2(Cauchy 交錯定理) 設A是n階Hermitian 矩陣,B是A的m階主子陣. 如果λ1(A)≥λ2(A)≥···≥λn(A) 是A的特征值,μ1(B)≥μ2(B)≥···≥μm(B) 是B的特征值, 那么λn-m+i(A)≤μi(B)≤λi(A), 其中i=1,···,m.

2 主要結論

設Kn,Pn和Cn分別表示n階的完全圖, 路以及圈. 設Σ = (G,σ) 是符號圖. 若G不包含H作為其導出子圖, 則稱H是G的禁用子圖. 頂點u在V(G) 中的鄰點集用NG(u) 表示. 頂點u的閉鄰點集是N[u]=N(u)∪{u}. 對于頂點子集S?V(G), 頂點v在頂點集S中的鄰點集用NS(v) 表示. 用G[S] 來表示由S導出的G的子圖. 若G[S] 是完全圖, 則稱S為團. 設dG(u)=|NG(u)| 是u在G中的度. 為了證明的方便,令

圖1 和

定理1設Σ 是n≥2 階連通符號圖. 如果那么Σ 是平衡的或者是平衡的或者是平衡的

證明將通過以下斷言來證明結論.

斷言1所有的三圈都是平衡的.

否則,存在一個非平衡的三圈(見圖2)作為Σ 的導出子圖,那么Σ 的第二大距離特征值一定大于或等于非平衡三圈的第二大距離特征值. 注意到非平衡三圈的第二大距離特征值等于1. 由引理2 可知及產生矛盾.

圖2 P5, C3 ～C5, H1 ～H3

斷言2Σ 的每一個符號完全子圖都是平衡的.

設(Ks,σ) 是Σ 的一個符號完全子圖. 如果s=1 或2, 那么結論顯然成立. 如果s=3, 那么由斷言1 可知(K3,σ) 平衡. 下面只需考慮s≥4. 若(Ks,σ) 是Σ 的非平衡符號完全子圖, 則首先斷言(Ks,σ) 的最短負圈必為(C3,σ). 否則, 假設(Cl,σ) 是(Ks,σ) 的最短負圈, 其中Cl=v1v2v3v4···vlv1且l≥4. 注意到(Ks,σ) 是可兼容的, 故而如果σ12σ23=-1, 那么σ13=-1, 這表明C′=v1v3v4···vlv1是長度為l-1 的負圈, 產生矛盾. 如果σ12σ23=1, 那么σ13=1, 這表明C′′=v1v3v4···vlv1是長度為l-1 的負圈, 產生矛盾. 這與斷言1 矛盾.因此, Σ 的每一個符號完全子圖都是平衡的.

斷言3(C4,σ), (C5,σ), (H1,σ), (H2,σ) 和(H3,σ) 是Σ 的禁用子圖.

Ci,Hj如圖2 所示, 其中i=4,5;j=1,2,3. 假設(C4,σ)?Σ, 令V(C4)={v1,v2,v3,v4}, 可得A1和B1分別是的主子陣, 其中對于A1的元素, 注意到如果σ12σ23= 1 或σ14σ34= 1, 那么σ13= 1, 如果σ23σ34= 1 或σ12σ14= 1, 那么σ24= 1. 對于矩陣B1, 如果但通過Matlab可得因此由引理2 可得及產生矛盾. 因此, (C4,σ) 是Σ 的禁用子圖.

假設(C5,σ) ?Σ, 令V(C5) = {v1,v2,v3,v4,v5}, 于是可得A2和B2分別是的主子陣, 其中的元素, 注意到如果σ12σ23=σ23σ34=σ34σ45=1, 那么σ13=σ24=σ35=1. 對于矩陣B2, 如果但通過Matlab可得因此由引理2 可得及產生矛盾. 因此, (C5,σ) 是Σ 的禁用子圖.

[45]張賢明：《從本土訴求到全球視野：當代中國政治學繁榮與發展的思考》，《貴州社會科學》2012年第3期。

假設(H1,σ)?Σ. 令V(P3)={v1,v2,v3}并且N(v1)∩N(v2)∩N(v3)={v4},可得A3和B3分別是和的主子陣, 其中 但通過Matlab 可得及因此由引理2 可得產生矛盾. 因此, (H1,σ) 是Σ 的禁用子圖.

假設(H2,σ)?Σ,令V(P4)={v1,v2,v3,v4},v5與v2相鄰. 可得A4和B4分別是的主子陣, 其中對于A4的元素, 注意到如果σ12σ23=σ23σ34=σ12σ25=σ23σ25=1,那么σ13=σ24=σ15=σ35= 1, 如果σ12σ23σ34=σ25σ23σ34= 1, 那么σ14=σ45= 1. 對于矩陣B4, 如果么但通過Matlab 可得因此由引理2 可得產生矛盾. 因此, (H2,σ) 是Σ 的禁用子圖.

同理可得(H3,σ) 是Σ 的禁用子圖.

斷言4diam(G)≤3.

否則, 假設diam(G) ≥4, 那么(P5,σ) ?Σ, 并且令V(P5) = {v1,v2,v3,v4,v5}. 可得A5和B5分別是的主子陣, 其中對于A5的元素, 注意到如果σ12σ23=σ23σ34=σ34σ45=1, 那么σ13=σ24=σ35=1, 如果σ12σ23σ34=σ23σ34σ45=1, 那么σ14=σ25=1, 并且如果σ12σ23σ34σ45=1,那么σ15=1. 對于矩陣B5,如果那么如果那么并且如果那么但通過Matlab可得因此根據引理2 可得及產生矛盾.

情形1diam(G)=1. 顯然, Σ 為符號完全圖. 由斷言2 可知Σ 平衡.

情形2diam(G)=2. 設G的直徑路為P=v1v2v3.

斷言5對于任意頂點u∈V(Σ){v1,v2,v3} 有u∈N(v1)∪N(v2)∪N(v3).

否則, 存在一點v4使得d(vk,v4)=2, 其中1 ≤k≤3. 從而存在一點w, 使得w～v4且可得A6是的主子陣, 其中d(w,vk)=1 或2, 1 ≤k≤3, 并且注意到d(w,vk) 中至少有一個為1,aij=±1,1 ≤i≤4,2 ≤j≤5. 但通過Matlab 可得因此由引理2 可得及產生矛盾.

斷言5 表明圖G的任意一個頂點至少與v1,v2和v3中的一個相鄰.

斷言6N(v2)=V(Σ){v2}.

假設存在頂點u∈V(Σ){v2} 使得d(u,v2)=2. 如果u～v1且u～v3, 那么并有(C4,σ)?Σ, 這與斷言3 矛盾. 如果u～v1且u?v3, 則存在另一頂點w使得uwv3是u與v3之間的最短路, 即d(u,v3)=2. 若w?v1且w?v2, 則并有(C5,σ)?Σ, 這與斷言3 矛盾. 若w?v1且w～v2,則G[并有(C4,σ)?Σ,這與斷言3 矛盾. 若w～v1且w?v2,則并有(C4,σ)?Σ, 這與斷言3 矛盾. 若w～v1且w～v2, 則并有(H1,σ)?Σ, 這與斷言3 矛盾. 關于u?v1且u～v3的情況是類似的. 故而u?v1且u?v3, 但這與斷言5 矛盾.

令S1=(N(v1)∩N(v2))∪{v1,v2},S2=(N(v2)∩N(v3))∪{v2,v3}.

斷言7G[S1],G[S2] 是符號完全圖.

如果|S1| = 2 或3, 那么結論顯然成立. 下面假設|S1| ≥4 且G[S1] 不是符號完全圖. 設{u1,u2} ?N(v1)∩N(v2), 并且u1?u2, 那么并有(H1,σ) 是Σ 的導出子圖, 這與斷言3 矛盾. 因此G[S1] 是符號完全圖. 類似可得G[S2] 也是符號完全圖.

斷言8Σ-v2的每一個連通分支都是符號完全圖.

令Σ1,Σ2,···,Σk是Σ-v2的k個連通分支. 如果v1∈V(Σi) 或v3∈V(Σi), 那么根據斷言6 和斷言7,Σi(1 ≤i≤k) 一定是符號完全圖. 假設存在一個分支Σt使得v1,v3/∈V(Σt) 且Σt不是符號完全圖, 那么由Σt連通可知|V(Σt)|≥3. 因此在Σt中存在一個頂點x有兩個互不相鄰的鄰點y和z, 并且設P是y和z之間的一條二長路. 這表明(H1,σ)?Σ, 這與斷言3 矛盾.

結合斷言1～8, 如果diam(G)=2, 那么Σ 是平衡的

情形3diam(G)=3. 假設G的直徑路為P=v1v2v3v4.

斷言9dG(v1)=dG(v4)=1.

由對稱性不妨假設dG(v1)≥2, 那么存在另一頂點u使得u～v1. 首先斷言u?v4, 否則分為以下3 種情況討論. 若u?v2且u?v3, 則G[{u,v1,v2,v3,v4}]C5, 并有(C5,σ)?Σ, 產生矛盾; 若u?v2且u～v3(或u～v2且u?v3), 則G[{u,v1,v2,v3}]C4(或G[{u,v2,v3,v4}]C4), 并有(C4,σ)?Σ, 產生矛盾; 若u～v2且u～v3,則G[{u,v1,v2,v3}]H1,G[{u,v2,v3,v4}]H1, 并有(H1,σ)?Σ, 產生矛盾. 因此,u?v4. 如果u?v2且u?v3,那么G[{u,v1,v2,v3,v4}]P5, 并且(P5,σ)?Σ, 產生矛盾; 如果u?v2且u～v3, 那么G[{u,v1,v2,v3}]C4, 并有(C4,σ)?Σ, 產生矛盾; 如果u～v2且u?v3, 那么G[{u,v1,v2,v3,v4}]H3, 并有(H3,σ)?Σ, 產生矛盾; 如果u～v2且u～v3, 那么G[{u,v1,v2,v3}]H1, 并有(H1,σ)?Σ, 產生矛盾. 故而dG(v1)=1. 類似可得dG(v4)=1.

斷言10G[(N[v2]∪N[v3]){v1,v4}] 是符號完全圖.

如果N(v2)={v1,v3} 并且N(v3)={v2,v4}, 那么結論顯然成立. 如果|N(v2)|≥3 并且|N(v3)|=2, 那么存在另一頂點u使得u～v2且u?v3. 于是G[{u,v1,v2,v3,v4}]H2, 并有(H2,σ)?Σ, 產生矛盾. |N(v2)|=2且|N(v3)| ≥3 的情形是類似的. 接下來, 假設|N(v2)| ≥3 且|N(v3)| ≥3, 任取頂點u∈N(v2){v1,v3} 及w∈N(v3){v2,v4}. 若u=w, 則結論自然成立. 假設u/=w, 則斷言u～v3且w～v2. 否則, 若u?v3或w?v2, 則G[{u,v1,v2,v3,v4}]H2或G[{w,v1,v2,v3,v4}]H2, 并有(H2,σ) ?Σ, 產生矛盾. 若u?w, 則G[{u,w,v2,v3}]H1, 并有(H1,σ)?Σ, 產生矛盾. 于是u～w, 結論成立.

令T=V(Σ)(N[v2]∪N[v3]),S=(N(v2)∪N(v3)){v1,v4}. 如果T=?, 那么結論成立. 假設T/=?, 則以下斷言成立.

斷言11|T|≤|S|.

設u∈T, 首先斷言|NS(u)| ≥1. 否則, 存在頂點w∈T使得w與S中的任意頂點不相鄰. 因此w與v1或v4的距離至少為4, 產生矛盾. 其次斷言|NS(u)|=1. 否則, 存在頂點w∈T使得u1～w,u2～w, 其中u1,u2∈S, 因此由斷言10,u1～u2. 注意到, 根據斷言10,G[{u1,u2,v2}]K3且G[{u1,u2,v3}]K3. 從而G[{w,u1,u2,v2}]H1,G[{w,u1,u2,v3}]H1, 并有(H1,σ)?Σ, 產生矛盾. 最后可斷言NS(u1)∩NS(u2)=?, 其中{u1,u2}?T. 否則, 存在一頂點w∈S使得u1～w且u2～w, 其中u1,u2∈T. 根據斷言10,w～v2且w～v3. 如果u1～u2,那么G[{u1,u2,w,v1,v2}]～=H3且G[{u1,u2,w,v3,v4}]H3,并有(H3,σ)?Σ, 產生矛盾. 如果u1?u2,那么G[{u1,u2,w,v1,v2}]H2且G[{u1,u2,w,v3,v4}]H2, 并有(H2,σ)?Σ, 同樣產生矛盾.

斷言12T是獨立集.

如果|T|=|S|=1, 那么結論是平凡的. 假設|S|≥|T|≥2, 并設u1,u2∈T,w1,w2∈S使得u1u2,u1w1,u2w2∈E(Σ), 那么G[{u1,u2,w1,w2}]C4, 并有(C4,σ)?Σ, 產生矛盾.

結合斷言9～12, 如果diam(G)=3, 那么Σ 是平衡的其中2 ≤t≤s且s+t=n.

綜上所述, 定理1 得證.

3 結論

對于n≥2 階連通符號圖Σ, 當時,本文得到了Σ 是平衡的(Kn,σ) 或者是平衡的或者是平衡的其中2 ≤t≤s,s+t=n,并且k≥2. 在將來的研究中, 可以探討關于第二大符號距離特征值界的問題.