Erdős, Péter and Kharel, Shubha R. and Mezei, Tamás Róbert and Toroczkai, Zoltán (2024) New Results on Graph Matching from Degree-Preserving Growth. MATHEMATICS, 12 (22). No. 3518. ISSN 2227-7390
|
Text
mathematics-12-03518-v4.pdf - Published Version Available under License Creative Commons Attribution. Download (299kB) | Preview |
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 and 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.
| Item Type: | Article |
|---|---|
| Additional Information: | Department of Combinatorics and Applications, Alfréd Rényi Institute of Mathematics (HUN-REN), Reáltanoda utca 13–15, Budapest, H-1053, Hungary Department of Physics, University of Notre Dame, 225 Nieuwland Science Hall, Notre DameIN 46556, United States Export Date: 20 February 2025 Correspondence Address: Erdős, P.L.; Department of Combinatorics and Applications, Reáltanoda utca 13–15, Hungary; email: erdos.peter@renyi.hun-ren.hu Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, SNN 135643, K 132696 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH Funding details: National Science Foundation, NSF, IIS-1724297 Funding details: National Science Foundation, NSF Funding text 1: P.L.E. and T.R.M. were supported in part by the National Research, Development and Innovation Office\\u2014NKFIH grant SNN 135643, K 132696. SRK and ZT were supported by the NSF grant IIS-1724297. |
| Uncontrolled Keywords: | degree sequence extension; matching number; degree-preserving growth (DPG); lower bound on the matching number |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 17 Mar 2025 11:40 |
| Last Modified: | 17 Mar 2025 11:40 |
| URI: | https://real.mtak.hu/id/eprint/216901 |
Actions (login required)
 |
Edit Item |
