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

彭楊　耿顯亞　朱娜

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

關鍵詞：鄰接矩陣; 圖的正慣性指數(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理論.該理論表明，不飽和碳氫化合物的分子活躍性與其分子圖對應的零度及正慣性指數(shù)有密切關系.[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.假設V′是V的一個非空子集，以V′為頂點集，以兩端點均在V′中的邊的全體為邊集所組成的子圖，稱為G的由V′導出的子圖，記為G[V′].G[V′]稱為G的導出子圖，簡記為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關聯(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刪去懸掛點以及與懸掛點相鄰的頂點所得到的導出子圖，則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的一個導出子圖，則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包含五圈或更長的圈，則該圈是此單圈圖中的導出子圖，由引理5可知，此導出子圖的正慣性指數(shù)嚴格大于2.又根據(jù)引理6，p（G）≥3.因此，圖G只能包含三圈或四圈.

2.2.1 對包含三圈的單圈圖

對于圖G3和G4，應用引理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包含五圈或更長的圈作為導出子圖，由引理5可知，此導出子圖的正慣性指數(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） 如果兩個三圈之間沒有公共頂點，那么兩個三圈之間至少有一條邊.設兩個三圈之間的路的長度為k，當k≥2時，圖G會包含G3作為導出子圖.由定理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作為導出子圖.由引理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)廢水排放量預測[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-），女，安徽淮南人.碩士研究生，主要從事圖論及其應用的研究;耿顯亞（1981-），男，安徽淮南人.教授，博士，主要從事圖論及其應用的研究;朱娜（1995-），女，安徽淮南人.碩士研究生，主要從事圖論及其應用的研究.