The minimum matching energy of bicyclic graphs with given girth. (English) Zbl 1347.05116

Li, Hong-Hai; Zou, Li

Rocky Mt. J. Math. 46, No. 4, 1275-1291 (2016); corrigendum ibid. 48, No. 6, 1983-1992 (2018).

Summary: The matching energy of a graph was introduced by I. Gutman and S. Wagner [Discrete Appl. Math. 160, No. 15, 2177–2187 (2012; Zbl 1252.05120)] and defined as the sum of the absolute values of zeros of its matching polynomial. Let \(\theta (r,s,t)\) be the graph obtained by fusing two triples of pendant vertices of three paths \(P_{r+2}\), \(P_{s+2}\) and \(P_{t+2}\) to two vertices. The graph obtained by identifying the center of the star \(S_{n-g}\) with the degree 3 vertex \(u\) of \(\theta (1,g-3,1)\) is denoted by \(S_{n-g}(u)\theta (1,g-3,1)\). In this paper, we show that, \(S_{n-g}(u)\theta (1,g-3,1)\) has minimum matching energy among all bicyclic graphs with order \(n\) and girth \(g\).

MSC:

05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35	Extremal problems in graph theory
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

bicyclic graph; matching energy; girth

Citations:

Zbl 1252.05120

References:

[1]	L. Chen, J. Liu and Y. Shi, Matching energy of unicyclic and bicyclic graphs with a given diameter , Complexity 21 (2015), 224-238. · doi:10.1002/cplx.21599
[2]	L. Chen and Y. Shi, The maximal matching energy of tricyclic graphs , MATCH Comm. Math. Comp. Chem. 73 (2015), 105-120. · Zbl 1464.05230
[3]	D.M. Cvetković, M. Doob, I. Gutman and A. Torgašev, Recent results in the theory of graph spectra , North-Holland, Amsterdam, 1988. · Zbl 0634.05054
[4]	H. Deng, The smallest Hosoya index in \((n, n+ 1)\)-graphs , J. Math. Chem. 43 (2008), 119-133. · Zbl 1143.05063 · doi:10.1007/s10910-006-9186-6
[5]	I. Gutman, The matching polynomial , MATCH Comm. Math. Comp. Chem. 6 (1979), 75-91. · Zbl 0436.05053
[6]	I. Gutman and D.M. Cvetković, Finding tricyclic graphs with a maximal number of matchings-Another example of computer aided research in graph theory , Publ. Inst. Math. Nouv. 35 (1984), 33-40. · Zbl 0561.05043
[7]	I. Gutman and S. Wagner, The matching energy of a graph , Discr. Appl. Math. 160 (2012), 2177-2187. · Zbl 1252.05120 · doi:10.1016/j.dam.2012.06.001
[8]	I. Gutman and F. Zhang, On the ordering of graphs with respect to their matching numbers , Discr. Appl. Math. 15 (1986), 25-33. · Zbl 0646.05049 · doi:10.1016/0166-218X(86)90015-6
[9]	G. Huang, M. Kuang and H. Deng, Extremal graph with respect to matching energy for a random polyphenyl chain , MATCH Comm. Math. Comp. Chem. 73 (2015), 121-131. · Zbl 1464.05208
[10]	S. Ji, X. Li and Y. Shi, Extremal matching energy of bicyclic graphs , MATCH Comm. Math. Comp. Chem. 70 (2013), 697-706. · Zbl 1299.05220
[11]	S. Ji and H. Ma, The extremal matching energy of graphs , Ars Combin. 115 (2014), 343-355. · Zbl 1340.05167
[12]	S. Ji, H. Ma and G. Ma, The matching energy of graphs with given edge connectivity , J. Inequal. Appl. 1 (2015), 1-9. · Zbl 1329.05190 · doi:10.1186/s13660-015-0938-3
[13]	X. Li, Y. Shi and I. Gutman, Graph energy , Springer, New York, 2012.
[14]	X. Li, Y. Shi, M. Wei and J. Li, On a conjecture about tricyclic graphs with maximal energy , MATCH Comm. Math. Comp. Chem. 72 (2014), 183-214. · Zbl 1464.05241
[15]	H. Li, B. Tan and L. Su, On the signless Laplacian coefficients of unicyclic graphs , Linear Alg. Appl. 439 (2013), 2008-2009. · Zbl 1282.05129 · doi:10.1016/j.laa.2013.05.030
[16]	S. Li and W. Yan, The matching energy of graphs with given parameters , Discr. Appl. Math. 162 (2014), 415-420. · Zbl 1300.05162 · doi:10.1016/j.dam.2013.09.014
[17]	H. Li, Y. Zhou and L. Su, Graphs with extremal matching energies and prescribed parameters , MATCH Comm. Math. Comp. Chem. 72 (2014), 239-248. · Zbl 1464.05239
[18]	R. Sun, Z. Zhu and L. Tan, On the Merrifield-Simmons index and Hosoya index of bicyclic graphs with a given girth , Ars Combin. 103 (2012), 465-478. · Zbl 1265.05472
[19]	K. Xu, K.C. Das and Z. Zheng, The minimal matching energy of \((n,m)\)-graphs with a given matching number , MATCH Comm. Math. Comp. Chem. 73 (2015), 93-104. · Zbl 1464.05255