双圈图的最大Estrada指数

运筹学学报 ›› 2014, Vol. 18 ›› Issue (2): 111-118.

双圈图的最大Estrada指数

徐薇薇¹, 王文环^1,*

1. 上海大学理学院数学系, 上海 200444

出版日期:2014-06-15 发布日期:2014-06-15
通讯作者: 王文环 E-mail:whwang@shu.edu.cn
基金资助:
国家自然科学基金 (No. 11001166), 上海市重点学科建设基金 (No. S30104)

Bicyclic graph with the maximal Estrada indices

XU Weiwei¹, WANG Wenhuan^1,*

2. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Online:2014-06-15 Published:2014-06-15

摘要/Abstract

摘要： 令\mathcal{B}_n^+表示顶点个数为n的双圈二部图的集合. 考虑了\mathcal{B}_n^+中图依 Estrada指数从大到小的排序问题. 利用二部图的Estrada指数和最大特征值之间的关系, 当n\geq 8时, 得到了\mathcal{B}_n^+中具有最大和次大Estrada指数的图.

关键词: 双圈图, Estrada指数, 图的特征值, 二部图

Abstract: Let \mathcal{B}^+_{n} be the set of bipartite bicyclic graphs with n vertices. In \mathcal{B}^+_{n}, ordering the graphs in terms of their maximal Estrada indices was considered. With the aid of a relationship between the Estrada index and the largest eigenvalue of the bipartite graphs, we deduce the graphs with the largest and the second largest Estrada indices in \mathcal{B}^+_{n} for n\geq 8.

Key words: bicyclic graph, Estrada indices, eigenvalues of graph, bipartite

中图分类号:

O157.6

徐薇薇, 王文环. 双圈图的最大Estrada指数[J]. 运筹学学报, 2014, 18(2): 111-118.

XU Weiwei, WANG Wenhuan. Bicyclic graph with the maximal Estrada indices[J]. Operations Research Transactions, 2014, 18(2): 111-118.

参考文献

Cvetkovic D M, Doob M, Sachs H. Spectra of Graphs Theory and Application [M]. New York: Academic Press, 1980.
Estrada E. Characterization of 3D molecular structure [J]. Chemical Physics Letters, 2000, 319(5-6): 713-718.
Estrada E, Rodriguez-Velazquez J A. Subgraph centrality in complex networks [J]. Physical Review E, 2005, 71(5): 056103.
Estrada E. Topological structural classes of complex networks [J]. Physical Review E, 2007, 75: 016103.
Estrada E, Rodriguez-Velazquez J A. Spectral measures of bipartivity in complex networks [J]. Physical Review E, 2005, 72(4): 046105.
Estrada E, Rodriguez-Velazquez J A, Randic M. Atomic branching in molecules [J]. International Journal of Quantum Chemistry, 2006, 106(4): 823-832.
de la Pena J A, Gutman I, Rada J. Estimating the Estrada index [J]. Linear Algebra and its Applications, 2007, 427(1): 70-76.
Bamdad H, Ashraf F, Gutman I. Lower bounds for Estrada index and Laplacian Estrada index [J]. Applied Mathematics Letters, 2010, 23(7): 739-742.
Fath-Tabar G H, Ashrafi A R. New upper bounds for Estrada index of bipartite graphs [J]. Linear Algebra and its Applications, 2011, 435(10): 2607-2611.
Ashrafi A R, Fath-Tabar G H. Bounds on the Estrada index of ISR (4,6)-fullerenes [J]. Applied Mathematics Letters, 2011, 24(3): 337-339.
Deng H Y. A proof of a conjecture on the Estrada index [J]. Match-Communications in Mathematical and in Computer Chemistry, 2009, 62(3): 599-606.
Deng H Y. A note on the Estrada index of trees [J]. Match-Communications in Mathematical and in Computer Chemistry, 2009, 62(3): 607-610.
Ilic A, Stevanovic D. The Estrada index of chemical trees [J]. Journal of Mathematical Chemistry, 2010, 47(1): 305-314.
Li J, Li X L, Wang L S. The minimal Estrada index of trees with two maximum degree vertices [J]. Match-Communications in Mathematical and in Computer Chemistry, 2010, 64(3): 799-810.
Zhang J B, Zhou B, Li J P. On Estrada index of trees [J]. Linear Algebra and its Applications, 2011, 434(1): 215-223.
Du Z B, Zhou B. The Estrada index of trees [J]. Linear Algebra and its Applications, 2011, 435(10): 2462-2467.
Du Z B, Zhou B. On the Estrada index of graphs with given number of cut edges [J]. Electronic Journal of Linear Algebra, 2011, 22: 586-592.
Du Z B, Zhou B, Xing R. On maximum Estrada indices of graphs with given parameters [J]. Linear Algebra and its Applications, 2012, \bf 436(9): 3767-3772.
Du Z B, Zhou B. The Estrada index of unicyclic graphs [J]. Linear Algebra and its Applications, 2012, 436(9): 3149-3159.
Wang W H. The unicyclic graph with the maximal Estrada indices [J]. Match-Communications in Mathematical and in Computer Chemistry, 2012, 68(3): 939-955.
Hou Y P, Li J S. Bounds on the largest eigenvalues of trees with a given size of matching [J]. Linear Algebra and its Applications, 2002, 342: 203-217.
李乔, 冯克勤. 论图的最大特征根 [J]. 应用数学学报, 1979, 2(2): 167-175.
Guo S G. The spectral radius of unicyclic and bicyclic graphs with n vertices and k pendant vertices [J]. Linear Algebra and its Applications, 2005, 408: 78-85.
Liu H Q, Lu M, Tian F. On the spectral radius of graphs with cut edges [J]. Linear Algebra and its Applications, 2004, 389: 139-145.
Wu B F, Xiao E L, Hong Y. The spectral radius of trees on k pendant vertices [J]. Linear Algebra and its Applications, 2005, 395: 343-349.
Guo S G. On the spectral radius of bicyclic graphs with n vertices and diameter d [J]. Linear Algebra and its Applications, 2007, 422: 119-132.

[1]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[2]	刘岩, 雷梦霞, 黄晓娴. 最大匹配的路变换图[J]. 运筹学学报, 2019, 23(2): 104-112.
[3]	翟若男, 王力工, 董占鹏, 王展青, 梅若星. 几类多圈图的拉普拉斯谱刻画[J]. 运筹学学报, 2016, 20(2): 59-68.
[4]	简相国,袁西英,张曼. 单圈图和双圈图的最大无符号拉普拉斯分离度[J]. 运筹学学报, 2015, 19(2): 99-104.
[5]	肖毛, 王文环. 不含偶圈双圈图的极小斜能量[J]. 运筹学学报, 2014, 18(4): 85-95.
[6]	欧阳章东, 黄元秋. 完全二部图K_{3,3}与星S_n的积图的交叉数[J]. 运筹学学报, 2014, 18(2): 69-76.
[7]	赵伟良, 赵衍才, 梁作松. 两类广义控制问题的NP-完全性[J]. 运筹学学报, 2012, 16(3): 139-144.