彭?xiàng)睢」@亞　朱娜

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

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

[中圖分類號(hào)]O157.6?? [文獻(xiàn)標(biāo)志碼]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ù)研究源自于上世紀(jì)量子化學(xué)中E.Hu··ckel發(fā)現(xiàn)的重要現(xiàn)象——E.Hu··ckel理論.該理論表明，不飽和碳?xì)浠衔锏姆肿踊钴S性與其分子圖對(duì)應(yīng)的零度及正慣性指數(shù)有密切關(guān)系.[1-2]1957年圖論學(xué)家提出要刻畫所有的奇異圖這一公開問題[3]——刻畫所有零度大于零的圖的問題——對(duì)圖的慣性指數(shù)的刻畫成為圖譜理論的熱點(diǎn)問題之一.很多學(xué)者得到了一些有意義的結(jié)果[4-7]，但正慣性指數(shù)為2的圖的刻畫仍是未解決的問題，故筆者刻畫了正慣性指數(shù)為2的樹、單圈以及雙圈圖.

1 主要引理

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

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

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

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

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

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

引理4[5] 圖G包含兩個(gè)頂點(diǎn)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）對(duì)Pn，有

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

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

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

2.1 對(duì)于樹

定理1 對(duì)于樹G，p（G）=2當(dāng)且僅當(dāng)G=G1或G=G2.

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

2.2 對(duì)于單圈圖

定理2 對(duì)于單圈圖G，p（G）=2當(dāng)且僅當(dāng)G=G5，G=G6，或G=G7.

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

2.2.1 對(duì)包含三圈的單圈圖

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

2.2.2 對(duì)包含四圈的單圈圖

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

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

2.3 對(duì)于雙圈圖

定理3 對(duì)于雙圈圖，若p（G）=2，當(dāng)且僅當(dāng)G=G16，或G=G17，或G=G18，或G=G21，或G=G24，或G=G27.

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

2.3.1 G包含兩個(gè)三圈

（1）兩個(gè)三圈之間有一條公共邊，如圖G12所示.因?yàn)镹G12（v1）=NG12（v3），所以當(dāng)i=1，3時(shí)至少

有一個(gè)dG（vi）≥3.又因?yàn)閜（G13）=p（G14）=p（G15）=3，所以GΔ/G13，GΔ/G14，GΔ/G15.因此得出

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

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

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

2.3.2 G是包含一個(gè)三圈和一個(gè)四圈的雙圈圖

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

（2）如果三圈和四圈之間只有一個(gè)公共點(diǎn)，如圖G29.因?yàn)镹G29（v4）=NG29（v6），故dG（v4）≥3和dG（v6）≥3至少有一個(gè)成立.因?yàn)橛梢?得p（G30）=3，所以GΔ/G30.因此，在這種情況下沒有滿足條件的簡(jiǎn)約圖.

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

2.3.3 G是包含兩個(gè)四圈的雙圈圖

（1）兩個(gè)四圈之間有兩條公共邊（如圖G31所示）.因?yàn)閳DG31中NG31（v2）=NG31（v3）=NG31（v4），要使圖G中沒有孿生點(diǎn)，則dG（v2）≥3，dG（v3）≥3，dG（v4）≥3中至少要有兩個(gè)成立.因?yàn)橛梢?得p（G32）=3，所以GΔ/G32.故在這種情況下沒有滿足條件的簡(jiǎn)約圖.

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

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

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

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

參考文獻(xiàn)

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

[2]方國斌，李萍.基于馬爾可夫鏈的國內(nèi)廢水排放量預(yù)測(cè)[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，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]劉英偉，張洋.任意螺旋線拓?fù)鋽?shù)值解法[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，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

基金項(xiàng)目：安徽省自然科學(xué)基金項(xiàng)目（2008085MA01）

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