| Peer-Reviewed

The Matching Energy of Random Multipartite Graphs

Received: 22 September 2019     Accepted: 2 December 2019     Published: 7 December 2019
Views:       Downloads:
Abstract

Let Gn be a simple graph with n vertices. Gutman and Wagner founded the theory of random graphs, they introduced the matching energy of the graph Gn, which was defined as the sum of the absolute values of the eigenvalues of the matching polynomial of the graph Gn. For the Erdös-Rényi type random graph Gn,p of order n with a fixed probability p, where p is a real number greater than zero and less than 1, that is, the graph G on n vertices by connecting two vertices with probability p(e), and each edge is independent of other one. Chen, Li and Lian solved a conjecture proposed by Gutman and Wagner, that is, the expectation of the matching energy of Gn,p converges to a certain number associated with n and p almost surely. But they only did the result for random bipartite graphs. In this paper, we give some lower bounds for the matching energy of random bipartite graphs. And then we will use Chen et al’s method to generalize this conclusion to any random multipartite graphs.

Published in American Journal of Mathematical and Computer Modelling (Volume 4, Issue 4)
DOI 10.11648/j.ajmcm.20190404.12
Page(s) 94-98
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2019. Published by Science Publishing Group

Keywords

Random Graphs, Matching Energy, Multipartite Graphs

References
[1] J. A. Bondy, U. S. R. Murty, Graph Theory, GTM 244, Springer, 2008.
[2] X. Chen, X. Li, H. Lian, The matching energy of random graphs, Discrete Applied Mathematics 193 (2015), 102–109.
[3] P. Erdös, A. Rényi, On random graphs I, Publ. Math. Debrecen 6 (1959), 290–297.
[4] E. J. Farrell, An introduction to matching polynomial, J. Combin. Theory Ser. B 27 (1979), 75–86.
[5] I. Gutman, S. Wagner, The matching energy of a graph, Discr. Appl. Math. 160 (2012), 2177–2187.
[6] I. Gutman, Acyclic systems with extremal H¨uckel π-electron energy, Theor. Chim. Acta. 45 (1977), 79–87.
[7] I. Gutman, Partial ordering of forests according to their characteristic polynomials, in: A. Hajnal, V. T. Sos (Eds.), Combinatorics, North-Holland, Amsterdam, 1978, pp. 429–436.
[8] I. Gutman, X. Li, Energies of Graphs – Theory and Applications, Math. Chem. Monogr. Vol. 17 (2016). ISBN 978-86-6009-033-3, Kragujevac, Serbia.
[9] I. Gutman, M. Milun, N. Trinajstić, Graph theory and molecular orbitals 19, non-parametric resonance energies of arbitrary conjugated systems, J. Amer. Chem. Soc. 99 (1977), 1692–1704.
[10] I. Gutman, The matching polynomial, MATCH Commun. Math. Comput. Chem. 6 (1979), 75–91.
[11] C. Godsil, Matchings and walks in graphs, J. Graph Theory 5 (1981), 285–297.
[12] C. Godsil, I. Gutman, On the theory of the matching polynomial, J. Graph Theory 5 (1981), 137–144.
[13] C. Godsil, Algebraic Combinatorics, Chapman Hall, New York, 1993.
[14] O. J. Heilman, E. H. Lieb, Theory of monomerCdimer systems, Comm. Math. Phys. 25 (1972).
[15] I. Gutman, Graphs with greatest number of matchings, Publ. Inst. Math. (Beagrad) 27 (1980) 581-586.
[16] I. Gutman, Correction of the paper “Graphs with greatest number of matchings”, Publ. Inst. Math. (Beagrad) 32 (1982) 61-63.
[17] I. Gutman, D. Cvetkovic, Finding tricyclic graphs with a maximal number of matchins-another example of computer aided research aided research in graph theory, Publ. Inst. Math. (Beagrad) 35 (1984) 33-40.
[18] I. Gutman, F. Zhang, On a quasiordering of bipartite graphs, Publ. Inst. Math. (Beagrad) 35 (1984) 33-40.
[19] I. Gutman, F. Zhang, On the ordering of graphs with respect to their matching numbers, Discr. Appl. Math. 15 (1986) 25-33.
Cite This Article
  • APA Style

    Caibing Chang, Bo Deng, Haizhen Ren, Feng Fu. (2019). The Matching Energy of Random Multipartite Graphs. American Journal of Mathematical and Computer Modelling, 4(4), 94-98. https://doi.org/10.11648/j.ajmcm.20190404.12

    Copy | Download

    ACS Style

    Caibing Chang; Bo Deng; Haizhen Ren; Feng Fu. The Matching Energy of Random Multipartite Graphs. Am. J. Math. Comput. Model. 2019, 4(4), 94-98. doi: 10.11648/j.ajmcm.20190404.12

    Copy | Download

    AMA Style

    Caibing Chang, Bo Deng, Haizhen Ren, Feng Fu. The Matching Energy of Random Multipartite Graphs. Am J Math Comput Model. 2019;4(4):94-98. doi: 10.11648/j.ajmcm.20190404.12

    Copy | Download

  • @article{10.11648/j.ajmcm.20190404.12,
      author = {Caibing Chang and Bo Deng and Haizhen Ren and Feng Fu},
      title = {The Matching Energy of Random Multipartite Graphs},
      journal = {American Journal of Mathematical and Computer Modelling},
      volume = {4},
      number = {4},
      pages = {94-98},
      doi = {10.11648/j.ajmcm.20190404.12},
      url = {https://doi.org/10.11648/j.ajmcm.20190404.12},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20190404.12},
      abstract = {Let Gn be a simple graph with n vertices. Gutman and Wagner founded the theory of random graphs, they introduced the matching energy of the graph Gn, which was defined as the sum of the absolute values of the eigenvalues of the matching polynomial of the graph Gn. For the Erdös-Rényi type random graph Gn,p of order n with a fixed probability p, where p is a real number greater than zero and less than 1, that is, the graph G on n vertices by connecting two vertices with probability p(e), and each edge is independent of other one. Chen, Li and Lian solved a conjecture proposed by Gutman and Wagner, that is, the expectation of the matching energy of Gn,p converges to a certain number associated with n and p almost surely. But they only did the result for random bipartite graphs. In this paper, we give some lower bounds for the matching energy of random bipartite graphs. And then we will use Chen et al’s method to generalize this conclusion to any random multipartite graphs.},
     year = {2019}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - The Matching Energy of Random Multipartite Graphs
    AU  - Caibing Chang
    AU  - Bo Deng
    AU  - Haizhen Ren
    AU  - Feng Fu
    Y1  - 2019/12/07
    PY  - 2019
    N1  - https://doi.org/10.11648/j.ajmcm.20190404.12
    DO  - 10.11648/j.ajmcm.20190404.12
    T2  - American Journal of Mathematical and Computer Modelling
    JF  - American Journal of Mathematical and Computer Modelling
    JO  - American Journal of Mathematical and Computer Modelling
    SP  - 94
    EP  - 98
    PB  - Science Publishing Group
    SN  - 2578-8280
    UR  - https://doi.org/10.11648/j.ajmcm.20190404.12
    AB  - Let Gn be a simple graph with n vertices. Gutman and Wagner founded the theory of random graphs, they introduced the matching energy of the graph Gn, which was defined as the sum of the absolute values of the eigenvalues of the matching polynomial of the graph Gn. For the Erdös-Rényi type random graph Gn,p of order n with a fixed probability p, where p is a real number greater than zero and less than 1, that is, the graph G on n vertices by connecting two vertices with probability p(e), and each edge is independent of other one. Chen, Li and Lian solved a conjecture proposed by Gutman and Wagner, that is, the expectation of the matching energy of Gn,p converges to a certain number associated with n and p almost surely. But they only did the result for random bipartite graphs. In this paper, we give some lower bounds for the matching energy of random bipartite graphs. And then we will use Chen et al’s method to generalize this conclusion to any random multipartite graphs.
    VL  - 4
    IS  - 4
    ER  - 

    Copy | Download

Author Information
  • School of Mathematics and Statistics, Qinghai Normal University, Xining, China

  • School of Mathematics and Statistics, Qinghai Normal University, Xining, China

  • School of Mathematics and Statistics, Qinghai Normal University, Xining, China

  • School of Mathematics and Statistics, Qinghai Normal University, Xining, China

  • Sections