Jianming Zhu

Show more
Department of Applied Mathematics, Shanghai University of International Business and Economics, Shanghai, China.
Show less

Abstract: In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let w_i be a non-isolated vertex of graph G_i where i=1, 2, …, k. We use G_u(k) (respectively, H_v(k)) to denote the graph which is the coalescence of G (respectively, H) and G₁, G₂,…, G_k by identifying the vertices u (respectively, v) and w₁, w₂,…, w_k. In this paper, we first present a new technique of directly comparing the matching energies of G_u(k) and H_v(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.

Keywords: Matching Energy, Unicyclic Graph, Perfect Matching

Cite this paper: Zhu, J. (2019) Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Matching Energies. Open Journal of Discrete Mathematics, 9, 17-32. doi: 10.4236/ojdm.2019.91004.

References

[1]   Gutman, I. (1978) The Energy of a Graph. Berichte Mathematisch-statistische Sektion Forschungszentrum Graz, 103, 1-22.

[2]   Gutman, I. (1977) Acyclic Systems with Extremal Hukel-Electron Energy. Theoretica Chimica Acta, 45, 79-87.
https://doi.org/10.1007/BF00552542

[3]   Li, N. and Li, S. (2008) On the Extremal Energy of Trees. MATCH Communications in Mathematical and in Computer Chemistry, 59, 291-314.

[4]   Gutman, I., Radenkovic, S., Li, N. and Li, S. (2008) Extremal Energy of Trees. MATCH Communications in Mathematical and in Computer Chemistry, 59, 315-320.

[5]   Wang, W. and Kang, L. (2010) Ordering of the Trees by Minimal Energy. Journal of Mathematical Chemistry, 47, 937-958.
https://doi.org/10.1007/s10910-009-9616-3

[6]   Shan, H. and Shao, J. (2010) Graph Energy Change Due to Edge Grafting Operations and Its Applications. MATCH Communications in Mathematical and in Computer Chemistry, 64, 25-40.

[7]   Huo, B., Ji, S., Li, X. and Shi, Y. (2011) Complete Solution to a Conjecture on the Fourth Maximal Energy Tree. MATCH Communications in Mathematical and in Computer Chemistry, 66, 903-912.

[8]   Shan, H. and Shao, J. (2012) The Proof of a Conjecture on the Comparison of the Energies of Trees. Journal of Mathematical Chemistry, 50, 2637-2647.
https://doi.org/10.1007/s10910-012-0052-4

[9]   Andriantiana, E.O.D. (2012) More Trees with Large Energy. MATCH Communications in Mathematical and in Computer Chemistry, 68, 675-695.

[10]   Shan, H., Shao, J., Zhang, L. and He, C. (2012) A New Method of Comparing the Energies of Subdivision Bipartite Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 68, 721-740.

[11]   Shan, H., Shao, J., Zhang, L. and He, C. (2012) Proof of a Conjecture on Trees with Lagre Energy. MATCH Communications in Mathematical and in Computer Chemistry, 68, 703-720.

[12]   Gutman, I., Furtula, B., Andriantiana, E.O.D. and Cvetic, M. (2012) More Trees with Large Energy and Small Size. MATCH Communications in Mathematical and in Computer Chemistry, 68, 697-702.

[13]   MArn, C., Monsalve, J. and Rada, J. (2015) Maximum and Minimum Energy Trees with Two and Three Branched Vertices. MATCH Communications in Mathematical and in Computer Chemistry, 74, 285-306.

[14]   He, C., Lei, L., Shan, H. and Peng, A. (2017) Two Subgraph Grafting Theoerms on the Energy of Bipartite Graphs. Linear Algebra and its Applications, 515, 96-110.
https://doi.org/10.1016/j.laa.2016.11.010

[15]   Zhu, J. and Yang, J. (2018) Minimal Energies of Trees with Three Branched Vertices. MATCH Communications in Mathematical and in Computer Chemistry, 79, 263-274.

[16]   Hou, Y. (2001) Unicyclic Graphs with Minimal Energy. Journal of Mathematical Chemistry, 29, 163-168.
https://doi.org/10.1023/A:1010935321906

[17]   Hou, Y., Gutman, I. and Woo, C. (2002) Unicyclic Graphs with Maximal Energy. Linear Algebra and Its Applications, 356, 27-36.
https://doi.org/10.1016/S0024-3795(01)00609-7

[18]   Andriantiana, E.O.D. (2011) Unicylic Bipartite Graphs with Maximum Energy. MATCH Communications in Mathematical and in Computer Chemistry, 66, 913-926.

[19]   Huo, B., Li, X. and Shi, Y. (2011) Complete Solution to a Conjecture on the Maximal Energy of Unicyclic Graphs. European Journal of Combinatorics, 32, 662-673.
https://doi.org/10.1016/j.ejc.2011.02.011

[20]   Wang, W. (2011) Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Energies. MATCH Communications in Mathematical and in Computer Chemistry, 66, 927-942.

[21]   Zhu, J. (2013) On Minimal Energies of Unicyclic Graphs with Perfect Mathching. MATCH Communications in Mathematical and in Computer Chemistry, 70, 97-118.

[22]   Zhang, J. and Zhou, B. (2005) On Bicyclic Graphs with Minimal Energies. Journal of Mathematical Chemistry, 37, 423-431.
https://doi.org/10.1007/s10910-004-1108-x

[23]   Li, X. and Zhang, J. (2007) On Bicyclic Graphs with Maximal Energy. Linear Algebra and Its Applications, 427, 87-98.
https://doi.org/10.1016/j.laa.2007.06.022

[24]   Huo, B., Ji, S., Li, X. and Shi, Y. (2011) Solution to a Conjecture on the Maximal Energy of Bipartite Bicyclic Graphs. Linear Algebra and Its Applications, 435, 804-810.
https://doi.org/10.1016/j.laa.2011.02.001

[25]   Ji, S. and Li, J. (2012) An Approach to the Problem of the Maximal Energy of Bicyclic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 68, 741-762.

[26]   Li, S., Li, X. and Zhu, Z. (2008) On Tricyclic Graphs with Minimal Energy. MATCH Communications in Mathematical and in Computer Chemistry, 59, 397-419.

[27]   Li, X., Shi, Y. and Wei, M. (2014) On a Conjecture about Tricyclic Graphs with Maximal Energy. MATCH Communications in Mathematical and in Computer Chemistry, 72, 183-214.

[28]   Li, X., Mao, Y. and Liu, M. (2015) More on a Conjecture about Tricyclic Graphs with Maximal Energy. MATCH Communications in Mathematical and in Computer Chemistry, 73, 11-26.
https://doi.org/10.1016/j.comcom.2015.07.003

[29]   Li, X., Shi, Y. and Gutman, I. (2012) Graph Energy. Springer, New York.
https://doi.org/10.1007/978-1-4614-4220-2

[30]   Gutman, I. (2001) The Energy of a Graph: Old and New Results, Algebraic Combinatorics and Applications. Springer-Verlag, Berlin, 196-211.

[31]   Gutman, I. and Wagner, S. (2012) The Matching Energy of a Graph. Discrete Applied Mathematics, 160, 2177-2187.
https://doi.org/10.1016/j.dam.2012.06.001

[32]   Aihara, J. (1976) A New Definition of Dewar-Type Resonance Energies. Journal of the American Chemical Society, 98, 2750-2758.
https://doi.org/10.1021/ja00426a013

[33]   Gutman, I., Milun, M. and Trinajstic, N. (1975) Topological Definition of Delocalisation Energy. MATCH Communications in Mathematical and in Computer Chemistry, 1, 171-175.

[34]   Gutman, I., Milun, M. and Trinajstic, N. (1977) Graph Theory and Molecular Orbitals 19. Nonparametric Resonance Energies of Arbitrary Conjugated Systems. Journal of the American Chemical Society, 99, 1692-1704.
https://doi.org/10.1021/ja00448a002

[35]   Zhu, J. and Yang, J. (2018) On the Minimal Matching Energies of Unicyclic Graphs. Discrete Applied Mathematics.
https://doi.org/10.1016/j.dam.2018.06.013

[36]   Chen, L. and Liu, J. (2015) The Bipartite Unicyclic Graphs with the First Largest Matching Energies. Applied Mathematics and Computation, 268, 644-656.
https://doi.org/10.1016/j.amc.2015.06.115

[37]   Chen, L., Liu, J. and Shi, Y. (2016) Bounds on the Matching Energy of Unicyclic Odd-Cycle Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 75, 315-330.

[38]   Ji, S., Li, X. and Shi, Y. (2013) Extremal Matching Energy of Bicyclic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 70, 697-706.

[39]   Liu, X., Wang, L. and Xiao, P. (2018) Ordering of Bicyclic Graphs by Matching Energy. MATCH Communications in Mathematical and in Computer Chemistry, 79, 341-365.

[40]   Chen, L. and Shi, Y. (2015) The Maximal Matching Energy of Tricyclic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 73, 105-119.

[41]   Ji, S. and Ma, H. (2014) The Extremal Matching Energy of Graphs. Ars Combinatoria, 115, 343-355.

[42]   Li, S. and Yan, W. (2014) The Matching Energy of Graphs with Given Parameters. Discrete Applied Mathematics, 162, 415-420.
https://doi.org/10.1016/j.dam.2013.09.014

[43]   Li, H., Zhou, Y. and Su, L. (2014) Graphs with Extremal Matching Energies and Prescribed Paramaters. MATCH Communications in Mathematical and in Computer Chemistry, 72, 239-248.

[44]   Wang, W. and So, W. (2015) On Minimum Matching Energy of Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 74, 399-410.

[45]   Xu, K., Das, K.C. and Zheng, Z. (2015) The Minimal Matching Energy of -Graphs with a Given Matching Number. MATCH Communications in Mathematical and in Computer Chemistry, 73, 93-104.

[46]   Chen, L., Liu, J. and Shi, Y. (2015) Matching Energy of Unicyclic and Bicyclic Graphs with a Given Diameter. Complexity, 21, 224-238.
https://doi.org/10.1002/cplx.21599

[47]   Zou, L. and Li, H. (2016) The Minimum Matching Energy of Bicyclic Graphs with Given Girth. Rocky Mountain Journal of Mathematics, 46, 1275-1291.
https://doi.org/10.1216/RMJ-2016-46-4-1275

[48]   Shang, Y.L. (2015) The Estrada Index of Evolving Graphs. Applied Mathematics and Computation, 250, 415-423.
https://doi.org/10.1016/j.amc.2014.10.129

[49]   Shang, Y.L. (2015) Laplacian Estrada and Normalized Laplacian Estrada Indices of Evolving Graphs. PLoS ONE, 10, e0123426.
https://doi.org/10.1371/journal.pone.0123426