符號(hào)圖的特征多項(xiàng)式系數(shù)定理及其應(yīng)用

譚學(xué)忠，譚學(xué)功

(1．廣東商學(xué)院數(shù)學(xué)學(xué)院，廣東廣州510320;2．暨南大學(xué)華文學(xué)院，廣東廣州510610)

COLLATZ 和 SINOGOWITZ［3］首次提出了如下問(wèn)題:刻劃滿足條件η(G)＞0的簡(jiǎn)單圖．這個(gè)問(wèn)題在化學(xué)中有重要應(yīng)用，正如文獻(xiàn)［4］所指，一個(gè)二部圖G(對(duì)應(yīng)于一個(gè)化學(xué)分子)如果滿足條件η(G)＞0，那么表明這個(gè)圖所代表的分子是不穩(wěn)定的．后來(lái)其他特殊類(lèi)型的簡(jiǎn)單圖的零度也被廣泛研究，但是符號(hào)圖的零度問(wèn)題卻研究得很少，F(xiàn)AN等［5］首次考慮了符號(hào)圖的零度問(wèn)題，得到了單圈符號(hào)圖的若干結(jié)論．本文將經(jīng)典的簡(jiǎn)單圖的特征多項(xiàng)式的系數(shù)定理做了推廣，使其對(duì)符號(hào)圖成立，并用它對(duì)單圈符號(hào)圖的零度進(jìn)行研究;定義了零指數(shù)集合的概念，得到單圈符號(hào)圖的零指數(shù)集合，同時(shí)，對(duì)于文獻(xiàn)［5］中的部分結(jié)論給出了不同的證明．

引理1［6］設(shè)是一個(gè)符號(hào)圖．則是平衡的，當(dāng)且僅當(dāng)

這個(gè)引理表明，平衡的符號(hào)圖與簡(jiǎn)單圖是切換等價(jià)的．下面的引理則表明，非平衡的單圈符號(hào)圖與一個(gè)底圖相同，且圈中恰含一條負(fù)號(hào)邊的單圈符號(hào)圖切換等價(jià)．

引理2［7］設(shè)是一個(gè)非平衡的n階單圈符號(hào)圖．則 ^U切換等價(jià)于底圖為U且圈中恰含一條負(fù)號(hào)邊的單圈符號(hào)圖．

本文推廣了簡(jiǎn)單圖的系數(shù)定理，并用它對(duì)符號(hào)樹(shù)圖和符號(hào)圈圖的零度進(jìn)行研究．同時(shí)，研究了單圈符號(hào)圖的零指數(shù)集，并且確定零度為n-2、n-3和n-4的單圈符號(hào)圖．

1 符號(hào)圖系數(shù)定理及應(yīng)用

對(duì)于簡(jiǎn)單圖G而言，因?yàn)閳DG的零度等于其鄰接矩陣A(G)的零特征值的代數(shù)重?cái)?shù)，亦即A(G)的特征多項(xiàng)式中特征值0的重?cái)?shù)，所以處理這個(gè)問(wèn)題的重要工具是圖譜理論中用以確定圖G的特征多項(xiàng)式系數(shù)的著名定理——系數(shù)定理［8］．只要將這個(gè)定理稍作修改就可以得到相應(yīng)的符號(hào)圖的系數(shù)定理(見(jiàn)下面的定理1)．

證明 由文獻(xiàn)［8］的等式(1．35)″，有

這里

根據(jù)符號(hào)圖鄰接矩陣的定義，初等圖形 ^Cq中的一條負(fù)號(hào)邊對(duì))的貢獻(xiàn)為-1，而則貢獻(xiàn)2個(gè)1或2個(gè)-1(由的符號(hào)決定)，2種情況都等于(-1)2(這就是規(guī)定m()=2的道理)．所以結(jié)論成立． □

推論 1［5，8］設(shè)=(T，σ)，T 中的最大對(duì)集所含邊數(shù)為q．那么η(^T)=n-2q．

應(yīng)用定理1，可以得到底圖為圈圖的符號(hào)圖的特征多項(xiàng)式的系數(shù)公式．

推論2 設(shè)

證明 由文獻(xiàn)［8］的式(4．4)和定理1不難證明上述結(jié)論． □

推論2表明符號(hào)圈圖的零度是0或者2，等價(jià)地說(shuō)，符號(hào)圈圖的秩為n或者n-2(見(jiàn)推論3)．

推論3［5］設(shè)是n階符號(hào)圈圖．那么

2 單圈符號(hào)圖的零度與零指數(shù)集合

由于單圈符號(hào)圖的底圖是單圈簡(jiǎn)單圖，所以其中包含一個(gè)符號(hào)圈圖作為導(dǎo)出子圖．下面用記號(hào)表示n(n≥3)階單圈符號(hào)圖的集合．本節(jié)考慮單圈符號(hào)圖的零度和零指數(shù)集合問(wèn)題．給出了零度等于n-2，n-3，n-4的圖的刻畫(huà)以及零指數(shù)集合，得到了當(dāng)n≥4時(shí)的單圈符號(hào)圖的零度上界為n-4．定理2的(1)、(2)以及定理4在文獻(xiàn)［5］已經(jīng)得到，我們?cè)谶@里給出另一種證明方法．

接下來(lái)的證明要用到下面的引理:

引理3［5］如果符號(hào)圖含有一個(gè)1度點(diǎn)，刪去這個(gè)頂點(diǎn)及其鄰接的頂點(diǎn)后導(dǎo)出的圖設(shè)為 ^H，那么有)成立．

定理2［5］設(shè)是一個(gè)n階單圈符號(hào)圖，則

證明 由于(1)與(2)的證明是類(lèi)似的，我們只證明(1)成立．首先，斷言中不存在懸掛點(diǎn)．否則，設(shè)v)且 d(v)=1，N(v)=u．令{v，u}．那么，由引理3，=n-2．又因?yàn)棣?n-2-r)，所以，r)=0，這說(shuō)明是空?qǐng)D，從而，這與是單圈符號(hào)圖矛盾．所以由推論3及條件n≥3知，n-2=2即n=4，所以同構(gòu)于平衡的

定理3 n(n≥3)階符號(hào)單圈圖的零指數(shù)集為

當(dāng)n≥5時(shí)，只需證明對(duì)于每一個(gè)0≤k≤n-4，都有一個(gè)單圈符號(hào)圖滿足

圖1 零度等于k的圖Figure 1 Graphswith nullity k

定理 4［5］設(shè)(n≥4)．那么-4當(dāng)且僅當(dāng)屬于集合{非平衡的，非平衡的，其中是平衡的，而對(duì)和平衡性無(wú)限制．的底圖見(jiàn)圖2．

圖2 零度等于n-4的單圈符號(hào)圖Figure 2 Unicyclic signed graphswith nullity n-4

情形1:^G11的最小度為1．設(shè)v是中的1度點(diǎn)，且N(v)=w．刪除v和w，設(shè)得到的圖為記∪(n-n1-2)K1．由引理 3，有)=n-4．另外=n-4．這說(shuō)明是空?qǐng)D．所以=(n1-2)K1．為了得到，恢復(fù)v，w到那么必為星圖且∪ (n-n1-2)K1．最后將x和y恢復(fù)給需要將y和中的n-n1-2個(gè)孤立點(diǎn)中的每一個(gè)點(diǎn)連一條邊．這得到另一個(gè)星圖(n2=n-n1)．為了得到中的圈，需要在y和的某2個(gè)頂點(diǎn)之間各添加一條邊．如果在y和的中心以及在y和的某個(gè)1度點(diǎn)各連一邊，那么如果在中2個(gè)端點(diǎn)都選擇1度點(diǎn)，那么上述證明過(guò)程表明，的平衡性對(duì)結(jié)論的成立沒(méi)有影響．

［1］HARARY F．On the notion of balanced in a signed graph［J］．Michigan Math J，1953，2(1):143-146．

［2］GUTMAN I，LEE L S，SHEU JH，et al．Preicting the nodal properties ofmolecular orbitals by means of signed graphs［J］．Bull Inst Chem Acad Sinica，1955，42:25-32．

［3］COLLATZ L V，SINOGOWITZ U．Spektren endlicher grafen［J］．Abh Math Sem Univ Hamburg，1957，21:63-77．

［4］LONGUET H C．Resonance structures and MO in unsaturated hydrocarbons［J］．JChem Phys，1950，18:265-274．

［5］FAN Y Z，WANG Y，WANG Y．A note on the nullity of unicyclic signed graphs［J］．Linear Algebra Appl，2013，438:1193-1200．

［6］HOU Y P，LIJS．On the Laplacian eigenvalues of signed graphs［J］．Linear Multilinear A，2003，51:21-30．

［7］FAN Y Z，GONG SC，WANG Y，etal．Firsteigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph［J］．Discrete Math，2009，309:2479-2487．

［8］CVETKOVIC D，DOOBM，SACHSH．Spectra of graphs［M］．New York:Academic Press，1980．