Szczegóły publikacji
Opis bibliograficzny
Minimum $k$-critical bipartite graphs / Sylwia CICHACZ, Karol SUCHAN // Discrete Applied Mathematics ; ISSN 0166-218X. — 2021 — vol. 302, s. 54-66. — Bibliogr. s. 66, Abstr. — K. Suchan - dod. afiliacja: Universidad Diego Portales, Chile
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 134837 |
|---|---|
| Data dodania do BaDAP | 2021-09-28 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2021.06.005 |
| Rok publikacji | 2021 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied Mathematics |
Abstract
We study the problem of Minimum -Critical Bipartite Graph of order - MCBG-: to find a bipartite , with , , and , which is -critical bipartite, and the tuple , where and denote the maximum degree in and , respectively, is lexicographically minimum over all such graphs. is -critical bipartite if deleting at most vertices from creates that has a complete matching, i.e., a matching of size . We show that, if is an integer, then a solution of the MCBG- problem can be found efficiently among -regular bipartite graphs of order , with , and . If , then all -regular bipartite graphs of order are -critical bipartite. For , it is not the case. We characterize the values of , , , and that admit an -regular bipartite graph of order , with , and give a simple construction that creates such a -critical bipartite graph whenever possible. Our techniques are based on Hall’s marriage theorem, elementary number theory, linear Diophantine equations, properties of integer functions and congruences, and equations involving them.
