Szczegóły publikacji
Opis bibliograficzny
Minimum k-critical-bipartite graphs: the irregular case / Sylwia CICHACZ, Agnieszka GÖRLICH, Karol SUCHAN // Opuscula Mathematica ; ISSN 1232-9274 . — Tytuł poprz.: Scientific Bulletins of Stanisław Staszic Academy of Mining and Metallurgy. Opuscula Mathematica. — 2026 — vol. 46 no. 2, s. 201–218. — Bibliogr. s. 216–217, Abstr. — Publikacja dostępna online od: 2026-04-10. — K. Suchnan - dod. afiliacja: Universidad Diego Portales Facultad de Ingeniería y Ciencias, Santiago, Chile
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 167099 |
|---|---|
| Data dodania do BaDAP | 2026-05-28 |
| Tekst źródłowy | URL |
| DOI | 10.7494/OpMath.202602181 |
| Rok publikacji | 2026 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Opuscula Mathematica : rocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica |
Abstract
We study the problem of finding a minimum k-critical-bipartite graph of order (n,m): a bipartite graph G=(U,V;E), with |U|=n, |V|=m, and n>m>1, which is k-critical-bipartite, and the tuple (|E|,ΔU,ΔV), where ΔU and ΔV denote the maximum degree in U and V, respectively, is lexicographically minimum over all such graphs. G is k-critical-bipartite if deleting any set of at most k=n−m vertices from U yields G′ that has a complete matching, i.e., a matching of size m. Cichacz and Suchan solved the problem for biregular bipartite graphs. Here, we extend their results to bipartite graphs that are not biregular. We prove tight lower bounds on the connectivity of k-critical-bipartite graphs, and we show that k-critical-bipartite graphs are expander graphs.
