New Results on Graph Matching from Degree-Preserving Growth

Péter L. Erdős (), Shubha R. Kharel, Tamás Róbert Mezei and Zoltán Toroczkai
Additional contact information
Péter L. Erdős: Department of Combinatorics and Applications, Alfréd Rényi Institute of Mathematics (HUN-REN), Reáltanoda utca 13–15, H-1053 Budapest, Hungary
Shubha R. Kharel: Department of Physics, University of Notre Dame, 225 Nieuwland Science Hall, Notre Dame, IN 46556, USA
Tamás Róbert Mezei: Department of Combinatorics and Applications, Alfréd Rényi Institute of Mathematics (HUN-REN), Reáltanoda utca 13–15, H-1053 Budapest, Hungary
Zoltán Toroczkai: Department of Physics, University of Notre Dame, 225 Nieuwland Science Hall, Notre Dame, IN 46556, USA

Mathematics, 2024, vol. 12, issue 22, 1-14

Abstract: The recently introduced model in S. R. Kharel et al.’s study [Degree-preserving network growth. Nature Physics 2022 , 18 , 100–106] uses matchings to insert new vertices of prescribed degrees into the current graph of an ever-growing graph sequence. The process depends both on the size of the largest available matching, which is the focus of this paper, as well as on the actual choice of the matching. Here, we first show that the question of whether a graphic degree sequence, extended with a new degree 2 δ , remains graphic is equivalent to the existence of a realization of the original degree sequence with a matching of size δ . Secondly, we present lower bounds for the size of the maximum matchings in any realization of the degree sequence. We then study the bounds on the size of maximal matchings in some realizations of the sequence, known as the potential matching number. We also estimate the minimum size of both maximal and maximum matchings, as determined by the degree sequence, independently of graphical realizations. Along this line we answer a question raised by T. Biedl et al.: Tight bounds on maximal and maximum matchings. Discrete Mathematics 2004 , 285 , 7–15.

Keywords: degree sequence extension; matching number; degree-preserving growth (DPG); lower bound on the matching number (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/22/3518/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/22/3518/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:22:p:3518-:d:1518629

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().