Abstract
In this paper, we consider the average size of independent edge sets, also called matchings, in a graph. We characterize the extremal graphs for the average size of matchings in general graphs and trees. In addition, we obtain inequalities between the average size of matchings and the number of matchings as well as the matching energy, which is defined as the sum of the absolute values of the zeros of the matching polynomial.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andriantiana, E.O.D., Razanajatovo Misanantenaina, V., Wagner, S.: The average size of independent sets in a graph. Eur. J. Math. (2019). https://doi.org/10.1007/s40879-019-00333-8
Davies, E., Jenssen, M., Perkins, W., Roberts, B.: Independent sets, matchings, and occupancy fractions. J. Lond. Math. Soc. 96(1), 47–66 (2017)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Gutman, I., Wagner, S.: The matching energy of a graph. Discrete Appl. Math. 160(15), 2177–2187 (2012)
Haslegrave, J.: Extremal results on average subtree density of series-reduced trees. J. Comb. Theory Ser. B 107, 26–41 (2014)
Jamison, R.E.: On the average number of nodes in a subtree of a tree. J. Comb. Theory Ser. B 35(3), 207–223 (1983)
Jamison, R.E.: Monotonicity of the mean order of subtrees. J. Comb. Theory Ser. B 37(1), 70–78 (1984)
Li, X., Shi, Y., Gutman, I.: Graph Energy. Springer Science & Business Media, Berlin (2012)
Lovász, L., Plummer, M.D.: Matching Theory, volume 121 of North-Holland Mathematics Studies. Annals of Discrete Mathematics, vol. 29. North-Holland Publishing Co., Amsterdam (1986)
Mol, L., Oellermann, O.: Maximizing the mean subtree order. J. Graph Theory (To appear)
Razanajatovo Misanantenaina, V.: Properties of graph polynomials and related parameters. Ph.D. thesis, Stellenbosch University (2017)
Vince, A., Wang, H.: The average order of a subtree of a tree. J. Comb. Theory Ser. B 100(2), 161–170 (2010)
Wagner, S.: Upper and lower bounds for Merrifield–Simmons index and Hosoya index. In: Gutman, I., Furtula, B., Das, K.C., Milovanović, E., Milovanović, I. (eds.) Bounds in Chemical Graph Theory—basics, volume 19 of Mathematical Chemistry Monographs, pp. 155–187. University of Kragujevac and Faculty of Science, Kragujevac (2017)
Wagner, S., Wang, H.: On the local and global means of subtree orders. J. Graph Theory 81(2), 154–166 (2016)
Acknowledgements
We would like to thank the referee for carefully reading the paper and making many useful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by the National Research Foundation of South Africa (Grants 96236 and 96310).
Rights and permissions
About this article
Cite this article
Andriantiana, E.O.D., Razanajatovo Misanantenaina, V. & Wagner, S. The Average Size of Matchings in Graphs. Graphs and Combinatorics 36, 539–560 (2020). https://doi.org/10.1007/s00373-020-02136-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-020-02136-1