Abstract
We show that there exists a matching with \(\frac{4m}{5k+3}\) edges in a graph of degree k and m edges.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Biedl, T., Demaine, E., Duncan, C., Fleischer, R., Kobourov, S.: Tight bounds on the maximal and maximum matchings. Discrete Math. 285(1-3), 7–15 (2004)
Feng, W., Qu, W., Wang, H.: Lower bounds on the cardinality of maximum matchings in graphs with bounded degrees. In: Proc. 2007 Int. Conf. on Foundations of Computer Science, Las Vegas, pp. 110–113 (2007)
König, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77, 453–456 (1916)
Nishizeki, T., Baybars, I.: Lower bounds on the cardinality of the maximum matchings of planar graphs. Discrete Math. 28(3), 255–267 (1979)
Petersen, J.: Die Theorie der regulären graphs (The theory of regular graphs). Acta Math. 15, 193–220 (1891)
Tutte, W.T.: The factorization of linear graphs. J. London Math. Soc. 22, 107–111 (1947)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Han, Y. (2008). Matching for Graphs of Bounded Degree. In: Preparata, F.P., Wu, X., Yin, J. (eds) Frontiers in Algorithmics. FAW 2008. Lecture Notes in Computer Science, vol 5059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69311-6_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-69311-6_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69310-9
Online ISBN: 978-3-540-69311-6
eBook Packages: Computer ScienceComputer Science (R0)