Archive
Special Issues

Volume 4, Issue 4, December 2019, Page: 94-98
The Matching Energy of Random Multipartite Graphs
Caibing Chang, School of Mathematics and Statistics, Qinghai Normal University, Xining, China
Bo Deng, School of Mathematics and Statistics, Qinghai Normal University, Xining, China; Key Laboratory of Tibetan Information Processing and Machine Translation, Xining, China; College of Science, Guangdong University of Petrochemical Technology, Maoming, China
Haizhen Ren, School of Mathematics and Statistics, Qinghai Normal University, Xining, China
Feng Fu, School of Mathematics and Statistics, Qinghai Normal University, Xining, China
Received: Sep. 22, 2019;       Accepted: Dec. 2, 2019;       Published: Dec. 7, 2019
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.
Keywords
Random Graphs, Matching Energy, Multipartite Graphs
Caibing Chang, Bo Deng, Haizhen Ren, Feng Fu, The Matching Energy of Random Multipartite Graphs, American Journal of Mathematical and Computer Modelling. Vol. 4, No. 4, 2019, pp. 94-98. doi: 10.11648/j.ajmcm.20190404.12
Reference
[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.