幾類正慣性指數(shù)為2的圖的刻畫

彭楊　耿顯亞　朱娜

摘 要：圖G的正慣性指數(shù)p（G）定義為圖G的鄰接矩陣A（G）中正特征值的個數(shù).正慣性指數(shù)為2的圖的刻畫仍是未解決的問題.本文刻畫正慣性指數(shù)p（G）=2的樹、單圈以及雙圈圖.

關(guān)鍵詞：鄰接矩陣; 圖的正慣性指數(shù); 圖的秩

[中圖分類號]O157.6?? [文獻標志碼]A

Several Types of Graphs with Positive Inertia Index 2

PENG Yang，GENG Xianya，ZHU Na

（School of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001，China）

Abstract：The positive inertia index of a graph G is p（G），which is defined as the number of positive eigenvalues of adjacency matrix A（G）.The characterization of a graph with a positive inertia index of 2 remains a unresolved problem.This paper characterizes trees，unicyclic and bicyclic graphs with positive inertia index p（G）=2.

Keywords： Adjacency matrix; Positive inertia index of graphs; Rank of graphs

Key words：adjacency matrix;positive inertia index of graphs;rank of graphs

圖的慣性指數(shù)研究源自于上世紀量子化學中E.Hu··ckel發(fā)現(xiàn)的重要現(xiàn)象——E.Hu··ckel理論.該理論表明，不飽和碳氫化合物的分子活躍性與其分子圖對應(yīng)的零度及正慣性指數(shù)有密切關(guān)系.[1-2]1957年圖論學家提出要刻畫所有的奇異圖這一公開問題[3]——刻畫所有零度大于零的圖的問題——對圖的慣性指數(shù)的刻畫成為圖譜理論的熱點問題之一.很多學者得到了一些有意義的結(jié)果[4-7]，但正慣性指數(shù)為2的圖的刻畫仍是未解決的問題，故筆者刻畫了正慣性指數(shù)為2的樹、單圈以及雙圈圖.

1 主要引理

本文考慮的是簡單、連通、無序的圖.令G=（V，E），其中V=v1，v2，…，vn是非空的頂點集，E=e1，e2，……，em是邊集.圖G的鄰接矩陣A（G）=（aij）是對稱矩陣，定義為：如果vi和vj相鄰，則aij=1，否則aij=0.假設(shè)V′是V的一個非空子集，以V′為頂點集，以兩端點均在V′中的邊的全體為邊集所組成的子圖，稱為G的由V′導(dǎo)出的子圖，記為G[V′].G[V′]稱為G的導(dǎo)出子圖，簡記為GΔG[V′].四個鄰接矩陣的譜參數(shù)：圖G的正慣性指數(shù)p（G）就是圖G的鄰接矩陣A（G）的正特征值的數(shù)目.圖G的負慣性指數(shù)n（G）就是圖G的鄰接矩陣A（G）的負特征值的數(shù)目.圖G的零度η（G）就是圖G的鄰接矩陣A（G）的零特征值的重數(shù).圖G秩r（G）就是圖G的鄰接矩陣A（G）的秩.顯然，對于以上四個參數(shù)，有以下兩個自然得到的等式.

p（G）+n（G）+η（G）=|V|， p（G）+n（G）=r（G）.

在本文中用uv表示在頂點u和頂點v之間添加的邊.頂點v的鄰域記為NG（v）={u|uv∈E（G）}.并且圖G的頂點v的度dG（v）是G中與v關(guān)聯(lián)的邊的數(shù)目，即dG（v）=|NG（v）|.若NG（u）=NG（v），稱頂點u和頂點v是一對孿生點; 若圖G中沒有孿生點，稱G是簡約的.

引理1[1] 如果圖G是樹，μ（G）是G的匹配數(shù)，則r（G）=2μ（G）.

引理2[4] 如果圖G是樹，μ（G）是G的匹配數(shù)，則p（G）=n（G）=μ（G）.

引理3[4] 如果G是包含一個懸掛點的圖，H是G刪去懸掛點以及與懸掛點相鄰的頂點所得到的導(dǎo)出子圖，則p（G）=p（H）+1，n（G）=n（H）+1，η（G）=η（H）.

引理4[5] 圖G包含兩個頂點u，w，如果≠NG（u）NG（w），H=G-{wv|v∈NG（u）}，則r（H）=r（G），p（H）=p（G）.特殊地，若NG（u）=NG（w），則r（G）=r（G-w），p（G）=p（G-w）.

引理5[1] 記Pn與Cn分別為階數(shù)為n的路與圈.

（1）對Pn，有

引理6[7] 若圖H是圖G的一個導(dǎo)出子圖，則r（H）≤r（G），η（H）≤η（G），p（H）≤p（G），n（H）≤n（G）.

2 刻畫三類正慣性指數(shù)恰為2的簡單連通圖

由引理4可知，若已知G是滿足p（G）=2的圖，則在G上添加任意多的孿生點，得到的新圖的正慣性指數(shù)仍保持為2.故而只考慮p（G）=2的簡約圖.

2.1 對于樹

定理1 對于樹G，p（G）=2當且僅當G=G1或G=G2.

證明 由引理2，可得p（G）=n（G）=μ（G）.所以，當p（G）=2時，μ（G）=2.可知該樹的秩為4.因只考慮G是簡約圖的情形，由參考文獻[5]可知， 樹中秩為4的簡約圖只有G1和G2，所以G=G1或G=G2.

2.2 對于單圈圖

定理2 對于單圈圖G，p（G）=2當且僅當G=G5，G=G6，或G=G7.

證明 若圖G包含五圈或更長的圈，則該圈是此單圈圖中的導(dǎo)出子圖，由引理5可知，此導(dǎo)出子圖的正慣性指數(shù)嚴格大于2.又根據(jù)引理6，p（G）≥3.因此，圖G只能包含三圈或四圈.

2.2.1 對包含三圈的單圈圖

對于圖G3和G4，應(yīng)用引理3計算可知，p（G3）=p（G4）=3，要求p（G）=2，故GΔG3且GΔG4.因要求圖G是簡約的，故而包含三圈的單圈圖只可能是圖G5，G6，G7，G8和G9中的某些.由引理3得，p（G5）=p（G6）=p（G7）=2，而p（G8）=p（G9）=3.因此，滿足要求的圖只有G5，G6和G7.

2.2.2 對包含四圈的單圈圖

對G10，因為NG10（v1）=NG10（v3），NG10=（v2）=NG10（v4），所以在G10上只添加不超過一個懸掛點，或者懸掛點只掛在相對的頂點上（v1和v3，或v2和v4）時，所得的圖都不是簡約圖.故必存i∈{1，2，3，4}使得d（vi）≥3.因此圖GΔG11.但是p（G11）>2， 從而GΔ/G11.得出矛盾，即p（G）=2的單圈簡約圖不能包含四圈.

綜上所述，滿p（G）=2足的單圈圖只有G5，G6，G7.

2.3 對于雙圈圖

定理3 對于雙圈圖，若p（G）=2，當且僅當G=G16，或G=G17，或G=G18，或G=G21，或G=G24，或G=G27.

證明 對于雙圈圖G，如果G包含五圈或更長的圈作為導(dǎo)出子圖，由引理5可知，此導(dǎo)出子圖的正慣性指數(shù)嚴格大于2.又根據(jù)引理6，p（G）≥3.因此，G只能是兩個三圈、一個三圈和一個四圈，或兩個四圈組成的雙圈圖.

2.3.1 G包含兩個三圈

（1）兩個三圈之間有一條公共邊，如圖G12所示.因為NG12（v1）=NG12（v3），所以當i=1，3時至少

有一個dG（vi）≥3.又因為p（G13）=p（G14）=p（G15）=3，所以GΔ/G13，GΔ/G14，GΔ/G15.因此得出

G16和G17可能滿足， 由引理3可得p（G16）=p（G17）=2，故G16和G17滿足要求.

（2） 如果兩個三圈之間只有一個公共頂點，如圖G18所示.因為p（G19）=p（G20）=3， 所以GΔ/G19，GΔ/G20.因此在這種情況下只有G18可能滿足.經(jīng)計算p（G18）=2，只有圖G18滿足.

（3） 如果兩個三圈之間沒有公共頂點，那么兩個三圈之間至少有一條邊.設(shè)兩個三圈之間的路的長度為k，當k≥2時，圖G會包含G3作為導(dǎo)出子圖.由定理2可知GΔ/G3.因此，k只能為1.當k=1（如圖G21）時，經(jīng)計算p（G21）=2滿足.如果對圖G21加懸掛點，如圖G22和G23，由引理3可得p（G22）=p（G23）=3，故GΔ/G22，GΔ/G23.因此，在這種情況下只有G21滿足.

2.3.2 G是包含一個三圈和一個四圈的雙圈圖

（1） 如果三圈和四圈之間有一條公共邊，如圖G24.由引理3可得，p（G25）=p（G26）=p（G28）=3，故GΔ/G25，GΔ/G26，GΔ/G28.因此，只有圖G24和G27可能滿足.經(jīng)計算p（G24）=p（G27）=2.故在這種情況下只有G24和G27滿足.

（2）如果三圈和四圈之間只有一個公共點，如圖G29.因為NG29（v4）=NG29（v6），故dG（v4）≥3和dG（v6）≥3至少有一個成立.因為由引理3得p（G30）=3，所以GΔ/G30.因此，在這種情況下沒有滿足條件的簡約圖.

（3）如果三圈和四圈之間沒有公共點，則三圈和四圈之間至少有一條邊.那么GΔ/G3. 由定理2可得GΔ/G3，矛盾.因此沒有滿足條件的簡約圖.

2.3.3 G是包含兩個四圈的雙圈圖

（1）兩個四圈之間有兩條公共邊（如圖G31所示）.因為圖G31中NG31（v2）=NG31（v3）=NG31（v4），要使圖G中沒有孿生點，則dG（v2）≥3，dG（v3）≥3，dG（v4）≥3中至少要有兩個成立.因為由引理3得p（G32）=3，所以GΔ/G32.故在這種情況下沒有滿足條件的簡約圖.

（2）兩個四圈之間只有一條公共邊（如圖G33）.由引理3和引理4可得p（G33）=3，故GΔ/G33.因此，在這種情況下沒有滿足要求的簡約圖.

（3）兩個四圈之間只有一個公共頂點（如圖G34）.因為NG34（v2）=NG34（v7），NG34（v4）=NG34（v6），所以要使圖G中沒有孿生點，則dG（v2）≥3和dG（vi）≥3（i=4，6），或者dG（v7）≥3和dG（vi）≥3（i=4，6）.如果滿足這個條件，經(jīng)計算p（G）≥3不滿足，因此，在這種情況下沒有滿足要求的簡約圖.

（4） 兩個四圈之間沒有公共頂點， 那么兩個四圈之間至少有一條邊.因此，圖G包含P6作為導(dǎo)出子圖.由引理3得p（P6）=3，故p（G）≥3.因此，在這種情況下沒有滿足條件的簡約圖.

綜上所述，對于滿足p（G）=2的雙圈圖，只有圖G16，G17，G18，G21，G24，G27.

參考文獻

[1]D.Cvetkovic′，M.Doob，H.Sachs.Spectra of Graphs[M].New York：Academic Press，1980.123-136.

[2]方國斌，李萍.基于馬爾可夫鏈的國內(nèi)廢水排放量預(yù)測[J].牡丹江師范學院學報：自然科學版，2020 （1）：6-10.

[3]E.Hu··ckel.Quantentheoretische Beitra··ge zum Benzolproblem[J].Z.Phys.，1931，70：204-286.

[4]X.Li，G.Yu.The skew-rank of graphs[J].Scientia Sinica Math，2015，45：93-104.

[5]J.H.Smith.Some properties of the spectrum of a graph[J].Combinat.Structures and their appl.，Gordon and Breach，1970：403-406.

[6]劉英偉，張洋.任意螺旋線拓撲數(shù)值解法[J].牡丹江師范學院學報：自然科學版，2019（3）：13-17.

[7]L.Wang，Y.Fan，Y.Wang.The Triangle-Free Graphs with Rank 6[J].Journal of Mathemtical Research with Applications.，2014，34（5）：517-528.

編輯：琳莉

收稿日期：2020-09-27

基金項目：安徽省自然科學基金項目（2008085MA01）

作者簡介：彭楊（1996-），女，安徽淮南人.碩士研究生，主要從事圖論及其應(yīng)用的研究;耿顯亞（1981-），男，安徽淮南人.教授，博士，主要從事圖論及其應(yīng)用的研究;朱娜（1995-），女，安徽淮南人.碩士研究生，主要從事圖論及其應(yīng)用的研究.