具有n-4個(gè)懸掛點(diǎn)的三圈圖補(bǔ)圖的最小特征值

劇宏娟 雷英杰

摘 要：為了討論給定階數(shù)為n且具有n-4個(gè)懸掛點(diǎn)的三圈圖補(bǔ)圖圖類中鄰接矩陣的最小特征值，刻畫其最小特征值達(dá)到極小的唯一圖。在只考慮簡單無向連通圖的基礎(chǔ)上，從補(bǔ)圖的結(jié)構(gòu)出發(fā)研究圖的最小特征值，通過運(yùn)用相關(guān)知識點(diǎn)分析論證了當(dāng)值為λ（G（（n-4）/2，（n-4）/2）C）時(shí)，給定階數(shù)為n且具有n-4個(gè)懸掛點(diǎn)的三圈圖補(bǔ)圖圖類中鄰接矩陣的最小特征值達(dá)到極小的唯一圖。結(jié)果表明：結(jié)合圖鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣，它的最小特征值為圖的最小特征值，較好地刻畫圖的本質(zhì)性質(zhì)。研究得出的具有n-4個(gè)懸掛點(diǎn)的三圈圖補(bǔ)圖的最小特征值達(dá)到極小的唯一圖，為后續(xù)進(jìn)一步研究補(bǔ)圖圖類中鄰接矩陣的最小特征值提供了一定的借鑒價(jià)值。

關(guān)鍵詞：圖論;三圈圖;鄰接矩陣;最小特征值;懸掛點(diǎn);補(bǔ)圖

中圖分類號：O157.5 ? 文獻(xiàn)標(biāo)志碼：A ? doi：10.7535/hbkd.2019yx06004

Abstract：In order to discuss the minimum eigenvalue of adjacency matrix in the class of complementary graphs of the tricyclic graph with a given order of n and n-4 pendent vertexes， the unique graph whose minimum eigenvalue reaches the minimum is characterized. Based on the simple undirected connected graph，the minimum eigenvalue of the graph is studied from the structure of the complement graph， and the minimum eigenvalue of the adjacency matrix in the complement graph class of the tricyclic graph with a given order of n and n-4 pendent vertexes reaches the minimum unique graph when the value is λ（G（（n-4）/2，（n-4）/2）C）. The result shows that the associative graph adjacency matrix is a matrix which represents the adjacency between vertices， and its minimum eigenvalue is the minimum eigenvalue of graph， which can describe the essential properties of graph well. The conclusion from this research shows that the minimum eigenvalue of the complement graph of the tricyclic graph with a given order of n and n-4 pendent vertexes reaches the minimum eigenvalue， which provides certain reference for further study of the minimum eigenvalue of the adjacency matrix in the complement graph class.

Keywords：graph theory; tricyclic graph; adjacency matrix; the minimum eigenvalue; pendent vertexes; complement graph

3 結(jié) 論

本文討論了給定階數(shù)為n且具有n-4個(gè)懸掛點(diǎn)三圈圖補(bǔ)圖圖類中鄰接矩陣的最小特征值，在只考慮簡單無向連通圖的基礎(chǔ)上，從補(bǔ)圖的結(jié)構(gòu)出發(fā)研究圖的最小特征值，從而刻畫了當(dāng)給定階數(shù)為n且具有n-4個(gè)懸掛點(diǎn)的三圈圖補(bǔ)圖圖類中鄰接矩陣的最小特征值為λ（G（（n-4）/2，（n-4）/2）C）時(shí)，其鄰接矩陣的最小特征值達(dá)到極小的唯一圖，并為研究此類圖最小特征值達(dá)到極小的唯一圖和后續(xù)補(bǔ)圖圖類中鄰接矩陣的最小特征征值提供了一定的理論依據(jù)。

參考文獻(xiàn)/References：

[1] BELL F K， CVETKOVIC D， ROWLINSON P， et al. Graphs for which the least eigenvalues is minimal， I[J]. Linear Algebra and Its Applications， 2008， 429（2）： 234-241.

[2] BELL F K， CVETKOVIC D， ROWLINSON P， et al. Graphs for which the least eigenvalues is minimal， II [J]. Linear Algebra and Its Applications， 2008， 429（8/9）： 2168-2176.

[3] FAN Yizheng， WANG Yi， GAO Yubin. Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread[J]. Linear Algebra and Its Applications， 2008， 429： 577-588.

[4] HAEMERS W H. Interlacing eigenvalues and graphs[J]. Linear Algebra and Its Applications， 1995， 226（95）： 593-616.

[5] TAN Yingying， FAN Yizheng. The vertex（edge） independence number， vertex（edge） cover number and the least eigenvalue of a graph[J]. Linear Algebra and Its Applications， 2010， 433 （4）： 790-795.

[6] FAN Yizheng，ZHANG Feifei，WANG Yi.The least eigenvalue of the complements of trees[J]. Linear Algebra and Its Applications， 2011， 435（9）：2150-2155.

[7] WANG Yi， FAN Yizheng， LI Xixin， et al. The least eigenvalue of graphs whose complements are unicyclic[J]. Discussiones Mathematics Graph Theory， 2013， 35（2）：1375-1379.

[8] YU Guidong， FAN Yizheng， WANG Yi. The least eigenvalue of graphs[J]. Journal of Mathematical Research with Applications， 2012， 32（6）： 659-665.

[9] HOU Xiaohua， QU Hui. The least eigenvalue for unicyclic graphs with given independence number[J]. Acta Scientiarum Naturalium Universitatis Nankaiensis， 2015， 48（4）： 73-79.

[10] FAN Dandan， CHEN Ya， MAMATABDULLA A，et al. Tricyclic graph whose least eigenvalue is minimum[J]. Journal of Qufu Normal University， 2018， 44（1）： 11-16.

[11] YE Miaolin， FAN Yizheng， LIANG Dong. The least eigenvalue of graphs with given connectivity[J]. Linear Algebra and Its Applications， 2009， 430（4）： 1375-1379.

[12] ?YU Guidong， FAN Yizheng， WANG Yi. Quadratic forms on graphs with application to minimizing the least eigenvalue of signless Laplacian over bicyclic graphs[J]. Electronic Journal of Linear Algebra， 2014， 27（2）： 213-236.

[13] ?YU Guidong， FAN Yizheng. The least eigenvalue of graphs whose complements are 2-vertex or 2-edge connected[J]. Operations Research Transactions， 2013， 17（2）：81-88.

[14] ?YU Guidong， FAN Yizheng， YE Miaolin. The least signless Laplacian eigenvalue of the complements of unicyclic graphs[J]. Applied Mathematics and Computation， 2017， 306（1）：13-21.

[15] ?LI Shuchao， WANG Shujing. The least eigenvalue of the signless Laplacian of the complements of trees[J]. Linear Algebra and Its Applications， 2012， 436（7）： 2398-2405.

[16] ?PETROVIC M， BOROVICANIN B， ALEKSIC T. Bicyclic graphs for which the least eigenvalue is minimum[J]. Linear Algebra and Its Applications， 2009， 430（4）：1328-1335.

[17] ?李雨，薛婷婷，孫威，等. 一種特殊補(bǔ)圖的最小特征值研究[J].廊坊師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2017，17（2）：5-12.

LI Yu， XUE Tingting， SUN Wei，et al. Study on the minimum eigenvalue of a special complement graph[J]. Journal of Langfang Teachers University （Natural Science Edition）， 2017， 17（2）： 5-12.

[18] 王禮想，蘆興庭.具有n-3個(gè)懸掛點(diǎn)的單圈圖補(bǔ)圖的最小特征值[J].安慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，23（4）：22-24.

WANG Lixiang， LU Xingting. Least eigenvalue of the complement of unicyclic graphs with n-3 pendent vertexes[J]. Journal of Anqing Normal University （Natural Science Edition）， 2017， 23（4）： 22-24.

[19] 蘆興庭，余桂東，嚴(yán)亞偉，等.補(bǔ)圖是獨(dú)立數(shù)為n-2的雙圈圖的最小特征值[J].安慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，24（1）：8-11.

LU Xingting， YU Guidong， YAN Yawei， et al. Least eignvalue of graphs whose complements are bicyclic graphs with independence number n-2 [J].Journal of Anqing Normal University （Natural Science Edition）， 2018，24（1）： 8-11.

[20] ?孫威，余桂東，蘆興庭，等.一類特殊圖的最小特征值[J].安慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，23（3）：32-34.

SUN Wei， YU Guidong， LU Xingting， et al. The least eignvalue of the special graphs[J]. Journal of Anqing Normal University （Natural Science Edition）， 2017， 23（3）： 32-34.

[21] 余桂東，孫威，蘆興庭.補(bǔ)圖具有懸掛點(diǎn)且連通的圖的最小特征值[J].運(yùn)籌學(xué)學(xué)學(xué)報(bào)，2019，23（1）：90-96.

YU Guidong， SUN Wei， LU Xingting. The least eigenvalue of the graphs whose complement are connected and have pendant vertices[J]. Operations Research Transactions， 2019， 23（1）： 90-96.