楊博遠(yuǎn)，李丹

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆烏魯木齊 830017)

0 引言

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

令σ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]給出了符號圖的兩類距離矩陣的定義:

與

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

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

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

1 準(zhǔn)備知識

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

引理1[9]符號圖的下列性質(zhì)是等價(jià)的.

(1) Σ 是平衡的;

引理2(Cauchy 交錯(cuò)定理) 設(shè)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 主要結(jié)論

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

圖1 和

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

證明將通過以下斷言來證明結(jié)論.

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

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

圖2 P5, C3 ～C5, H1 ～H3

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

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

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

Ci,Hj如圖2 所示, 其中i=4,5;j=1,2,3. 假設(shè)(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 可得及產(chǎn)生矛盾. 因此, (C4,σ) 是Σ 的禁用子圖.

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

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

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

假設(shè)(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 可得產(chǎn)生矛盾. 因此, (H2,σ) 是Σ 的禁用子圖.

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

斷言4diam(G)≤3.

否則, 假設(shè)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可得因此根據(jù)引理2 可得及產(chǎn)生矛盾.

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

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

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

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

斷言5 表明圖G的任意一個(gè)頂點(diǎn)至少與v1,v2和v3中的一個(gè)相鄰.

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

假設(shè)存在頂點(diǎn)u∈V(Σ){v2} 使得d(u,v2)=2. 如果u～v1且u～v3, 那么并有(C4,σ)?Σ, 這與斷言3 矛盾. 如果u～v1且u?v3, 則存在另一頂點(diǎn)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 矛盾. 關(guān)于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, 那么結(jié)論顯然成立. 下面假設(shè)|S1| ≥4 且G[S1] 不是符號完全圖. 設(shè){u1,u2} ?N(v1)∩N(v2), 并且u1?u2, 那么并有(H1,σ) 是Σ 的導(dǎo)出子圖, 這與斷言3 矛盾. 因此G[S1] 是符號完全圖. 類似可得G[S2] 也是符號完全圖.

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

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

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

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

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

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

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

如果N(v2)={v1,v3} 并且N(v3)={v2,v4}, 那么結(jié)論顯然成立. 如果|N(v2)|≥3 并且|N(v3)|=2, 那么存在另一頂點(diǎn)u使得u～v2且u?v3. 于是G[{u,v1,v2,v3,v4}]H2, 并有(H2,σ)?Σ, 產(chǎn)生矛盾. |N(v2)|=2且|N(v3)| ≥3 的情形是類似的. 接下來, 假設(shè)|N(v2)| ≥3 且|N(v3)| ≥3, 任取頂點(diǎn)u∈N(v2){v1,v3} 及w∈N(v3){v2,v4}. 若u=w, 則結(jié)論自然成立. 假設(shè)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,σ) ?Σ, 產(chǎn)生矛盾. 若u?w, 則G[{u,w,v2,v3}]H1, 并有(H1,σ)?Σ, 產(chǎn)生矛盾. 于是u～w, 結(jié)論成立.

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

斷言11|T|≤|S|.

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

斷言12T是獨(dú)立集.

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

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

綜上所述, 定理1 得證.

3 結(jié)論

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